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

Source abstract

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 line segments representing any two adjacent nodes of G are vertically visible to each other. In the present paper we give the best known compact visibility representation of G. Given a canonical ordering of the triangulated G, our algorithm draws the graph incrementally in a greedy manner. We show that one of three canonical orderings obtained from Schnyder's realizer for the triangulated G yields a visibility representation of G no wider than $\left\lfloor{\frac{22n-40}{15}}\right\rfloor$. Our easy-to-implement O(n)-time algorithm bypasses the complicated subroutines for four-connected components and four-block trees required by the best previously known algorithm of Kant. Our result provides a negative answer to Kant's open question about whether $\left\lfloor{\frac{3n-6}{2}}\right\rfloor$ is a worst-case lower bound on the required width. Also, if G has no degree-three (respectively, degree-five) internal node, then our visibility representation for G is no wider than $\left\lfloor{\frac{4n-9}{3}}\right\rfloor$ (respectively, $\left\lfloor{\frac{4n-7}{3}}\right\rfloor$). 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 a by-product, we give a much simpler proof for a corollary of Wagner's theorem on realizers due to Bonichon, Le Saëc, and Mosbah.