TL;DR
This paper proves that every 2-outerplanar graph contains a large induced forest (at least half its vertices) and a large induced outerplanar subgraph (at least two-thirds its vertices). These results provide tighter bounds than previously known for general planar graphs, offering new insights into the structural properties of 2-outerplanar graphs and their implications for graph algorithms and drawing.
What Problem Does This Paper Address?
The paper tackles a fundamental question in graph theory: how large can induced subgraphs with specific properties be within a given graph class? Specifically, it focuses on planar graphs, which are graphs that can be drawn on a plane without edge crossings. Two key properties are of interest:
- Induced Forests: A forest is a graph with no cycles. An induced subgraph is formed by selecting a subset of vertices and all edges between them. The Albertson-Berman conjecture states that every planar graph has an induced forest on at least half its vertices. The best known general bound for planar graphs is two-fifths of the vertices.
- Induced Outerplanar Subgraphs: An outerplanar graph is a planar graph where all vertices lie on the boundary of the outer face. Finding large induced outerplanar subgraphs is relevant for graph drawing algorithms, where simpler subgraphs can serve as a starting point.
While significant progress has been made for general planar graphs, this paper aims to establish stronger results for a specific subclass: 2-outerplanar graphs. These graphs have a more restricted structure than general planar graphs, suggesting that larger induced subgraphs might exist. The paper seeks to close the gap between existing bounds and conjectured optimal bounds for this specific graph class.
Methods
The paper employs a combination of structural graph theory, proof by contradiction, and detailed case analysis.
- Proof by Contradiction and Minimal Counterexample: For proving the existence of large induced forests, the authors assume a minimal counterexample graph (one with the fewest vertices that violates the conjecture) and then derive contradictions by analyzing its structure. This is a standard technique for proving existence results in graph theory.
- Layered Structure of 2-Outerplanar Graphs: 2-outerplanar graphs have a natural partition of vertices into two layers, $L_1$ (outermost) and $L_2$ (inner). The proofs heavily rely on analyzing the relationships and properties within and between these layers.
- Graph Decomposition and Subgraph Analysis: The proofs involve decomposing the graph into smaller components (e.g., facial blocks, critical triangles) and analyzing the properties of these components. This allows for a systematic examination of the graph's structure.
- Combinatorial Arguments: Detailed combinatorial arguments are used to show that certain configurations are impossible or lead to contradictions, thereby establishing the desired bounds. For instance, when proving the existence of a large induced outerplanar subgraph, the authors construct a specific set of vertices by carefully deleting vertices from $L_1$ based on a matching found in $L_2$.
Datasets
Not discussed in the paper. The paper focuses on theoretical results about graph structures rather than empirical evaluation on datasets.
Key Insights and Ideas
- Tighter Bounds for 2-Outerplanar Graphs: The most significant insight is that the restricted structure of 2-outerplanar graphs allows for much stronger guarantees on the size of induced forests and outerplanar subgraphs compared to general planar graphs. This highlights the importance of studying specific graph classes.
- Vertex Arboricity of 2-Outerplanar Graphs: The paper proves that 2-outerplanar graphs have a vertex arboricity of at most 2. Vertex arboricity is the minimum number of sets into which a graph's vertices can be partitioned such that each set induces a forest. This directly implies the existence of an induced forest on at least half the vertices, confirming a specific case of the Albertson-Berman conjecture for this class.
- Constructive Approach for Outerplanar Subgraphs: The proof for the large induced outerplanar subgraph is constructive. It outlines an algorithm that, by carefully deleting vertices from the outer layer ($L_1$), guarantees the remaining vertices induce an outerplanar subgraph of a significant size (at least two-thirds).
- Importance of Layered Structure: The proofs consistently leverage the two-layered structure of 2-outerplanar graphs, showing how properties of $L_1$ and $L_2$ interact to yield these strong results.
Key Results
- Theorem 1: Every 2-outerplanar graph has a vertex arboricity of at most 2. This implies that every 2-outerplanar graph has an induced forest on at least half of its vertices.
- Theorem 15: Every 2-outerplanar graph, where each connected component of the inner layer ($L_2$) is two-connected, has an induced outerplanar subgraph on at least two-thirds of its vertices.
Limitations and Future Work
- Assumption on $L_2$ Connectivity: Theorem 15 has an assumption that each connected component of $G[L_2]$ is two-connected. While the authors note that this assumption can be removed (citing another work), it's a limitation in the presented proof.
- Conjectures for Higher Outerplanarity: The paper proposes conjectures for 3-outerplanar graphs and general planar graphs regarding the size of induced outerplanar subgraphs. These are open problems for future research.
- Generalizing Results: The authors suggest that their results might be extendable to graphs with higher outerplanarity or other graph classes.
- Algorithmic Implications: While the paper provides theoretical bounds, developing efficient algorithms to find these large induced subgraphs is a natural next step.
Summary updated