TY - GEN
T1 - Compact visibility representation of 4-connected plane graphs
AU - He, Xin
AU - Wang, Jiun Jie
AU - Zhang, Huaming
PY - 2010
Y1 - 2010
N2 - The visibility representation (VR for short) is a classical representation of plane graphs. The VR has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. It is known that there exists a plane graph G with n vertices where any VR of G requires a size at least ⌊2n/3⌋ × (⌊4n/3⌋ - 3). For upper bounds, it is known that every plane graph has a VR with size at most ⌊2/3n⌋ × (2n - 5), and a VR with size at most (n - 1) × ⌊4/3n⌋. It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely of size ch n × cw n with ch < 1 and cw < 2). In this paper, we provide the first VR construction for a non-trivial graph class that simultaneously bounds both the height and the width. We prove that every 4-connected plane graph has a VR with height ≤ 3n/4 + 2⌈√n⌉ + 4 and width ≤ ⌈3n/2⌉. Our VR algorithm is based on an st-orientation of 4-connected plane graphs with special properties. Since the st-orientation is a very useful concept in other applications, this result may be of independent interests.
AB - The visibility representation (VR for short) is a classical representation of plane graphs. The VR has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. It is known that there exists a plane graph G with n vertices where any VR of G requires a size at least ⌊2n/3⌋ × (⌊4n/3⌋ - 3). For upper bounds, it is known that every plane graph has a VR with size at most ⌊2/3n⌋ × (2n - 5), and a VR with size at most (n - 1) × ⌊4/3n⌋. It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely of size ch n × cw n with ch < 1 and cw < 2). In this paper, we provide the first VR construction for a non-trivial graph class that simultaneously bounds both the height and the width. We prove that every 4-connected plane graph has a VR with height ≤ 3n/4 + 2⌈√n⌉ + 4 and width ≤ ⌈3n/2⌉. Our VR algorithm is based on an st-orientation of 4-connected plane graphs with special properties. Since the st-orientation is a very useful concept in other applications, this result may be of independent interests.
UR - https://www.scopus.com/pages/publications/78650816378
U2 - 10.1007/978-3-642-17458-2_28
DO - 10.1007/978-3-642-17458-2_28
M3 - Conference contribution
AN - SCOPUS:78650816378
SN - 3642174574
SN - 9783642174575
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 339
EP - 353
BT - Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings
T2 - 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010
Y2 - 18 December 2010 through 20 December 2010
ER -