Visibility representation of plane graphs with simultaneous bound for both width and height

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 (formula presented). For upper bounds, it is known that every plane graph has a VR with grid size at most (formula presented), and a VR with grid size at most (formula presented). 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 at most (formula presented) and width at most (formula presented). 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.