Visibility Representation of Plane Graphs with Simultaneous Bound for Both Width and Height

Abstract

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. The trivial upper bound is (n−1) ×(2n−5) (height × width). 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/3]n ×([4/3]n −3). For upper bounds, it is known that every plane graph has a VR with grid size at most [2/3]n ×(2n−5), and a VR with grid size at most (n−1) ×[4/3]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 with size at most c_h n ×c_w n 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 at most [23/24]n+2⎡√n⎤+10 and width at most [23/12]n. The area of our VR is larger than the area of some of the 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, which is far more challenging. Our VR algorithm is based on an st-orientation of plane graphs with special properties. Since st-orientations are a very useful concept in other applications, this result may be of independent interests.