Compact visibility representation of plane graphs

The visibility representation (VR for short) is a classical representation of plane graphs. It 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 grid of size at least 2/3n × (4/3n - 3) (width × height). For upper bounds, it is known that every plane graph has a VR with grid size at most 2/3n x (2n - 5), and a VR with grid 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 with size at most c_hn × c_wn with c_h < 1 and c_w < 2). In this paper, we provide the first VR construction with this property. We prove that every plane graph of n vertices has a VR with height ≤ max{23/24n + 2|√n] + 4, 11/12n + 13} and width ≤ 23/12n. The area (height × width) of our VR is larger than the area of some of previous results. However, bounding one dimension of the VR only requires finding a good st-orientation or a good dual s^*t^*-orientation of G. On the other hand, to bound both dimensions of VR simultaneously, one must find a good st-orientation and a good dual s^*t^*- orientation at the same time, and thus is far more challenging. Since st-orientation is a very useful concept in other applications, this result may be of independent interests.