Improved Outerplanarity Bounds for Planar Graphs
摘要
In this paper, we study the outerplanarity of planar graphs, i.e., the number of times that we must (in a planar embedding that we can initially freely choose) remove the outerface vertices until the graph is empty. It is well-known that there are n-vertex graphs with outerplanarity \(\tfrac{n}{6}+\varTheta (1)\) , and not difficult to show that the outerplanarity can never be bigger. We give here improved bounds of the form \(\tfrac{n}{2g}+2g+O(1)\) , where g is the fence-girth, i.e., the length of the shortest cycle with vertices on both sides. This parameter g is at least the connectivity of the graph, and often bigger; for example, our results imply that planar bipartite graphs have outerplanarity \(\tfrac{n}{8}+O(1)\) . We also show that the outerplanarity of a planar graph G is at most \(\tfrac{1}{2}\textrm{diam}(G)+O(\sqrt{n})\) , where \(\textrm{diam}(G)\) is the diameter of the graph. All our bounds are tight up to smaller-order terms, and a planar embedding that achieves the outerplanarity bound can be found in linear time.