New Theoretical Bounds of Visibility Representation of Plane Graphs

In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [6], Tamassia and Tollis [7] independently gave linear time VR algorithms for 2-connected plane graph. Afterwards, one of the main concerns for VR is the size of VR. In this paper, we prove that any plane graph G has a VR with height bounded by $\lfloor \frac{5n}{6} \rfloor$. This improves the previously known bound $\lceil \frac{15n}{16} \rceil$. We also construct a plane graph G with n vertices where any VR of G require a size of $(\lfloor \frac{2n}{3} \rfloor) \times (\lfloor \frac{4n}{3} \rfloor-3)$. Our result provides an answer to Kantrsquos open question about whether there exists a plane graph G such that all of its VR require width greater that cn, where c > 1. Research supported in part by NSF Grant CCR-0309953