TY - GEN
T1 - Width-optimal visibility representations of plane graphs
AU - Fan, Jia Hao
AU - Lin, Chun-Cheng
AU - Lu, Hsueh I.
AU - Yen, Hsu Chun
PY - 2007/12
Y1 - 2007/12
N2 - Given an n-node plane graph G, the visibility representation of G is concerned with drawing each node of G using a horizontal line segment such that the line segments associated with any two adjacent nodes of G are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of G no wider than [4n/3] - 2. Our result improves upon the previously known upper bound 4n/3 + 2[√n], providing a positive answer to a conjecture suggested in the literature about whether an upper bound 4n/3 + O(1) on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower bound [4n/3] - 3 only by one unit.
AB - Given an n-node plane graph G, the visibility representation of G is concerned with drawing each node of G using a horizontal line segment such that the line segments associated with any two adjacent nodes of G are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of G no wider than [4n/3] - 2. Our result improves upon the previously known upper bound 4n/3 + 2[√n], providing a positive answer to a conjecture suggested in the literature about whether an upper bound 4n/3 + O(1) on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower bound [4n/3] - 3 only by one unit.
UR - http://www.scopus.com/inward/record.url?scp=38149076400&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-77120-3_16
DO - 10.1007/978-3-540-77120-3_16
M3 - Conference contribution
AN - SCOPUS:38149076400
SN - 9783540771180
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 160
EP - 171
BT - Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
T2 - 18th International Symposium on Algorithms and Computation, ISAAC 2007
Y2 - 17 December 2007 through 19 December 2007
ER -