Unit Bar-Visibility Layouts of Triangulated Polygons Extended Abstract

Dean, Alice M. and Gethner, Ellen and Hutchinson, Joan P. (2004) Unit Bar-Visibility Layouts of Triangulated Polygons Extended Abstract. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 111-121 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_13).

Full text not available from this repository.

Abstract

A triangulated polygon is a 2-connected maximal outerplanar graph. A unit bar-visibility graph (UBVG for short) is a graph whose vertices can be represented by disjoint, horizontal, unit-length bars in the plane so that two vertices are adjacent if and only if there is a non-degenerate, unobstructed, vertical band of visibility between the corresponding bars. We give combinatorial and geometric characterizations of the triangulated polygons that are UBVGs. To each triangulated polygon G we assign a character string with the property that G is a UBVG if and only if the string satisfies a certain regular expression. Given a string that satisfies this condition, we describe a linear-time algorithm that uses it to produce a UBV layout of G.

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

Repository Staff Only: item control page

References

Bose, P., Dean, A., Hutchinson, J., Shermer, T. On rectangle visibility graphs. In: Lecture Notes in Computer Science 1190: Graph Drawing 1996. S. North (ed.). Springer-Verlag, Berlin (1997), 25-44.

Chen, G. and Keating, K. Bar Visibility Graphs with Bounded Length. Preprint.

Dean, A., Evans, W., Gethner, E., Laison, J., Safari, M. and Trotter, T. Bar k-Visibility Graphs. In preparation (2004).

Dean, A., Gethner, E., Hutchinson, J. A Characterization of Triangulated Polygons that are Unit Bar-Visibility Graphs. In preparation (2004).

Dean, A., Hutchinson, J. Rectangle-visibility layouts of unions and products of trees. J. Graph Alg. and App. 2 (1998), 1-21.

Dean, A., Hutchinson, J. Rectangle-visibility representations of bipartite gr4aphs. Disc. App. Math. 75 (1997), 9-25.

Dean, A. Veytsel, N. Unit bar-visibility graphs. Congressus Numerantium 160 (2003), 161-175.

Hutchinson, J., Shermer, T., Vince, A. On representations of some thickness two graphs. Computational Geometry, Theory and Applications, 13 (1990) 161-171.

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

Shermer, T. On rectangle visibility graphs III, external visibility and complexity. Proc.8th Canadian Conf. on Computational Geometry (1996) 234-239.

Streinu, I. and Whitesides, W. Rectangle Visibility Graphs: Characterization Construction, and Compaction. Lecture Notes in Computer Science #2607. H. Alt and M. Habib (eds.). Springer-Verlag, 2003, 26-37.

Tamassia, R., Tollis, I. A Unified Approach to Visibility Representations of Planar Graphs. J. of Discrete and Computational Geometry. 1 (1986), 321-341.

Wismath, S. Characterizing Bar Line-of-Sight Graphs. Proc. 1st ACM Symp. Computational Geometry (1985). 147-152.