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 -