Graph Analysis via Induced Subgraphs

Induced subgraphs constitute a central tool for understanding the structure of complex networks, as they retain original adjacency relations while highlighting relevant local and global properties. This thesis investigates induced subgraphs from complementary algorithmic and combinatorial viewpoints, aiming to characterize both their practical effectiveness in network analysis and their structural limitations in sparse graph classes. The first part of the thesis studies maximal cliques as fundamental dense induced subgraphs for graph analysis. Despite their worst-case intractability, maximal cliques can be efficiently enumerated in many sparse real-world graphs. Leveraging this property, we introduce clique-based representations for graph partitioning and community detection, in which vertices are embedded into a metric space according to their clique participation, enabling the use of standard clustering algorithms. This approach produces high-quality partitions and compares favorably with established community detection methods. To address the inherent redundancy and abundance of maximal cliques, we further introduce a unified framework for clique summarization. Within this framework, we formalize several principled summarization criteria and problem variants, and develop efficient algorithms for identifying isolated cliques, supported by pruning techniques that substantially reduce the enumeration search space. The second part of the thesis focuses on extremal questions concerning induced subgraphs in planar graphs. We derive bounds on the size of induced subgraphs with bounded maximum degree in planar and outerplanar graphs, obtaining tight results for specific parameter values. Additionally, we investigate the guaranteed existence of large outerplanar induced subgraphs in 2-outerplanar graphs, for which we establish a tight bound, and in planar 3-trees, where we derive both lower and upper bounds that extend and refine classical results in planar graph theory. Together, these contributions provide a coherent and unified perspective on induced subgraphs as a versatile tool for algorithmic network analysis and for the study of structural properties in sparse graphs.