Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer

Let $G$ be an $n$-node planar graph. In a visibility representation of $G$,each node of $G$ is represented by a horizontal line segment such that the linesegments representing any two adjacent nodes of $G$ are vertically visible toeach other. In the present paper we give the best known compact visibilityrepresentation of $G$. Given a canonical ordering of the triangulated $G$, ouralgorithm draws the graph incrementally in a greedy manner. We show that one ofthree canonical orderings obtained from Schnyder's realizer for thetriangulated $G$ yields a visibility representation of $G$ no wider than$\frac{22n-40}{15}$. Our easy-to-implement O(n)-time algorithm bypasses thecomplicated subroutines for four-connected components and four-block treesrequired by the best previously known algorithm of Kant. Our result provides anegative answer to Kant's open question about whether $\frac{3n-6}{2}$ is aworst-case lower bound on the required width. Also, if $G$ has no degree-three(respectively, degree-five) internal node, then our visibility representationfor $G$ is no wider than $\frac{4n-9}{3}$ (respectively, $\frac{4n-7}{3}$).Moreover, if $G$ is four-connected, then our visibility representation for $G$is no wider than $n-1$, matching the best known result of Kant and He. As aby-product, we obtain a much simpler proof for a corollary of Wagner's Theoremon realizers, due to Bonichon, Sa\"{e}c, and Mosbah.Comment: 11 pages, 6 figures, the preliminary version of this paper is to appear in Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Berlin, Germany, 200