On the 3-Tree Core of Plane Graphs

Plane 3-trees have been well studied in graph drawing literature. For many graph drawing styles, the aesthetic qualities that have been achieved for plane 3-trees are much better than the ones known for general plane graphs. This motivates us to investigate whether one can find a large plane 3-tree type structure in a general plane graph, and if so, whether it can be leveraged to obtain a better drawing for the graph. We thus introduce the concept of a 3-tree core H of a 3-connected plane graph G. Here, H is an edge-labeled plane 3-tree that represents G, and the distance d between H and G is the number of vertices of G that are missing in H. As an application of this concept, we consider the planar ortho-path visibility drawing, where each vertex is drawn as an orthogonal polygonal chain on an integer grid and each edge is drawn as an orthogonal line segment between the paths corresponding to its end vertices. We show that if H has a flat visibility drawing (i.e., each ortho-path is a horizontal line segment) with height k, then G has an ortho-path visibility drawing with height \(O(k2^d)\) . In particular, if G is a planar triangulation with \(d=O(1)\) , then G can be drawn with height \(4n/9+O(1)\) by choosing an appropriate planar embedding. This bound is significantly smaller than the \(2n/3+O(1)\) lower bound for the ortho-path visibility drawing when one must respect the input embedding.