Abstract
This note provides a formal proof that every planar graph with tree-width at most 3 (a planar partial 3-tree) is a spanning subgraph of a planar 3-tree. Furthermore, we show that any non-crossing planar drawing of such a graph can be extended to a drawing of the completed planar 3-tree without introducing new crossings.
Introduction
In graph theory, the relationship between planarity and tree-width is a subject of significant interest. A "partial planar 3-tree" is defined as a subgraph of a graph that is both planar and a 3-tree. Conversely, a "planar partial 3-tree" is a planar graph with tree-width at most 3. While it has long been suspected that these two classes are equivalent, a rigorous proof has been missing from the literature. This equivalence is important because planar 3-trees, also known as "stacked triangulations," possess inductive properties that simplify the analysis of complex network designs and graph drawing algorithms.
Structural Equivalence
The core of this work is resolving the "linguistic" ambiguity between the two terms. We demonstrate that for the properties of planarity and tree-width 3, the order of operations is commutative. This is a non-trivial result; for instance, while all forests are subgraphs of cliques, they are not necessarily subgraphs of acyclic cliques. The paper confirms that every planar graph with tree-width 3 is just a "hidden" planar 3-tree.
Methodology
The proof employs structural induction on the number of vertices $n$. The graph $G$ is analyzed based on its connectivity:
- Disconnected and 1-Connected Graphs: Components are handled by nesting them within the faces of other components or splitting at articulation points.
- 2-Connected Graphs: These are handled by identifying minimal cuts that separate the graph into smaller components.
- 3-Connected Graphs: These leverage the fact that 3-connected planar graphs have a unique embedding.
For each case, the authors demonstrate a way to add edges to $G$ to form a supergraph $\tilde{G}$ that is a full 3-tree. Crucially, these new edges can be drawn as non-crossing curves within the existing faces of the original planar drawing.
Main Results
The primary result is summarized in the following theorem:
Theorem 1. Every $n$-vertex planar partial 3-tree is a spanning subgraph of a planar $n$-vertex 3-tree.
Moreover, the paper establishes a geometric extension property: for any planar non-crossing drawing of the input graph $G$, the supergraph $\tilde{G}$ can be constructed such that its drawing extends the original one without crossings. This reinforces the view of planar 3-trees as stacked triangulations—graphs built by starting with a triangle and repeatedly placing a new vertex inside a triangular face and connecting it to the three corners.
Conclusion
This note fills a gap in the literature by providing a self-contained inductive proof for the completion of planar partial 3-trees. While the result is specific to $k=3$, it serves as a foundational building block for researchers working on graph drawing. Future work may explore the algorithmic complexity of this construction and the breakdown of this equivalence for higher values of $k$, where the relationship between tree-width and planarity becomes significantly more complex.
Summary updated