Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00260
Visibility Representation of Plane Graphs with Simultaneous Bound for Both Width and Height
JiunJie Wang and
Xin He
Vol. 16, no. 2, pp. 317334, 2012. Regular paper.
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 storientation 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 storientation and a good dual s^{*}t^{*}orientation
at the same time, which is far more challenging. Our VR algorithm is
based on an storientation of plane graphs with special properties. Since
storientations are a very useful concept in other applications,
this result may be of independent interests.

Submitted: May 2011.
Reviewed: November 2011.
Revised: February 2012.
Accepted: April 2012.
Final: May 2012.
Published: May 2012.
Communicated by
Antonios Symvonis

Journal Supporters
