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⌋.#R##N##R##N#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 chn×cwn 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.
['Xin He', 'Jiun-Jie Wang', 'Huaming Zhang']
Compact visibility representation of 4-connected plane graphs