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
Jiun-Jie Wang and
Xin He
Vol. 16, no. 2, pp. 317-334, 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 ch n ×cw n
with ch < 1 and cw < 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.
|
Submitted: May 2011.
Reviewed: November 2011.
Revised: February 2012.
Accepted: April 2012.
Final: May 2012.
Published: May 2012.
Communicated by
Antonios Symvonis
|
Journal Supporters
|