New Theoretical Bounds of Visibility Representation of Plane Graphs

Zhang, Huaming and He, Xin (2004) New Theoretical Bounds of Visibility Representation of Plane Graphs. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 425-430 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_43).

Full text not available from this repository.

Abstract

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_43
Classifications:Z Theory > Z.500 Representations
P Styles > P.900 Visibility
ID Code:613

Repository Staff Only: item control page

References

H. de Fraysseix, J. Pach and R. Pollack, How to draw a planar graph on a grid. Combinatorica 10 (1990), 41-51.

G. Kant, A more compact visibility representation. International Journal of Computational Geometry and Applications 7 (1997), 197-210.

G. Kant and X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science 172 (1997), 175-193.

A. Lempel, S. Even and I. Cederbaum, An algorithm for planarity testing of graphs, in Theory of Graphs, pp. 215-232, Rome, 1967.

C.-C. Lin, H.-I. Lu and I-F. Sun, Improved compact visibility representation of planar graph via Schnyder's realizer, in: Proc. STACS'03, LNCS, Vol. 2607, (Springer-Verlag, Berlin, 2003) 14-25.

P. Rosenstiehl and R. E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1 (1986), 343-353.

R. Tamassia and I.G. Tollis, An unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1 (1986), 321-341.

H. Zhang and X. He, Compact Visibility representation and Straight-Line Grid Embedding of Plane Graphs, in: Proc. WADS'03, LNCS, Vol. 2748, (Springer-Verlag Heidelberg, 2003) 493-504.

H. Zhang and X. He, On Visibility Representation of Plane Graphs, in: Proc. STACS'04, LNCS, Vol. 2996, (Springer-Verlag Heidelberg, 2004) 477-488.