New Theoretical Bounds of Visibility Representation of Plane GraphsZhang, Huaming and He, Xin (2004) New Theoretical Bounds of Visibility Representation of Plane Graphs. In: Graph Drawing 12th International Symposium, GD 2004, September 29October 2, 2004 , pp. 425430(Official URL: http://dx.doi.org/10.1007/9783540318439_43). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540318439_43
AbstractIn 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 2connected 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} \rfloor3)$. 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 CCR0309953.
Actions (login required)
