Computer Science – Data Structures and Algorithms
Scientific paper
2002-12-29
SIAM Journal on Discrete Math, 18(1):19-29, 2004
Computer Science
Data Structures and Algorithms
11 pages, 6 figures, the preliminary version of this paper is to appear in Proceedings of the 20th Annual Symposium on Theoret
Scientific paper
10.1137/S0895480103420744
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.
Lin Ching-Chi
Lu Hsueh-I
Sun I-Fan
No associations
LandOfFree
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-593680