Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer
<|reference_start|>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 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 $\frac{22n-40}{15}$. 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 $\frac{3n-6}{2}$ 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 $\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 a by-product, we obtain a much simpler proof for a corollary of Wagner's Theorem on realizers, due to Bonichon, Sa\"{e}c, and Mosbah.<|reference_end|>
@article{lin2002improved,
    title={Improved Compact Visibility Representation of Planar Graph via
  Schnyder's Realizer},
    author={Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun},
    journal={SIAM Journal on Discrete Math, 18(1):19-29, 2004},
    year={2002},
    doi={10.1137/S0895480103420744},
    archivePrefix={arXiv},
    eprint={cs/0212054},
    primaryClass={cs.DS cs.CG}
}