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

Simple item page
dc.creatorLin, Ching-Chi
dc.creatorLu, Hsueh-I
dc.creatorSun, I-Fan
dc.date2002-12-29
dc.date.accessioned2026-07-07T03:19:19Z
dc.date.available2026-07-07T03:19:19Z
dc.descriptionLet $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ëc, and Mosbah.
dc.description11 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, 2003
dc.identifierhttps://arxiv.org/abs/cs/0212054
dc.identifierhttp://arxiv.org/abs/cs/0212054
dc.identifierSIAM Journal on Discrete Math, 18(1):19-29, 2004
dc.identifierdoi:10.1137/S0895480103420744
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31412
dc.subjectData Structures and Algorithms
dc.subjectComputational Geometry
dc.subjectF.2.2; B.7.2; E.1; G.2.2; I.3.6
dc.titleImproved Compact Visibility Representation of Planar Graph via Schnyder's Realizer
dc.typetext

Files

Collections

arXiv