On Polar Visibility Representations of Graphs

Hutchinson, Joan P. (2002) On Polar Visibility Representations of Graphs. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 422-434 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_33).

WarningThere is a more recent version of this item available.

Full text not available from this repository.

Abstract

We introduce polar visibility graphs, graphs whose vertices can be represented by arcs of concentric circles with adjacency determined by radial visibility including visibility through the origin. These graphs are more general than the well-studied bar-visibility graphs and are characterized here, when arcs are proper subsets of circles, as the graphs that embed on the plane with all but at most one cut-vertex on a common face or on the projective plane with all cut-vertices on a common face. We also characterize the graphs representable using full circles and arcs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_33
Classifications:Z Theory > Z.500 Representations
P Styles > P.900 Visibility
ID Code:499

Available Versions of this Item

Repository Staff Only: item control page

References

P. Bose, A. Dean, J. Hutchinson, and T. Shermer. On rectangle visibility graphs. In S. North, editor, Symposium on Graph Drawing 96, vol. 1190 of LNCS. Springer-Verlag, 1997, pp. 25-44.

Y.-W. Chang, M.S. Jacobson, J. Lehel, and D.B. West. The visibility number of a graph. (preprint).

A. Dean and J. Hutchinson. Rectangle visibility representations of bipartite graphs. Discrete Appl. Math., 75 (1997) 9-25.

------. Rectangle visibility layouts of unions and products of trees. J. Graph Algorithms and Applications 2 (1998) 1-21.

A. Dean. Bar-visibility graphs on the Möbius Band. In: J. Marks (ed.): Proc. Graph Drawing 2000. (to appear)

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

B. Mohar. Projective planarity in linear time. J. Algorithms 15 (1993) 482-502.

B. Mohar, P. Rosenstiehl. Tesselation and visibility represetations of maps on the torus. Discrete Comput. Geom. 19 (1998) 249-263.

B. Mohar, C. Thomassen. Graphs on Surfaces. John Hopkins Press (to appear)

J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, Oxford (1987).

R. Tamassia, I. G. Tollis. A unified approach to visibility representations of planar graphs. Descrete and Computational Geometry 1 (1986) 321-341.

----- Tesselationa representations of planar graphs. In: J.V. Medanic, P.R. Kumar (eds.): Proc. 27th Annual Allerton Conf. on Communication, Control, and Computing. (1989)48-57.

----- Representations of graphs on a cylinder. SIAM J. Disc. Math 4 (1991) 139-149.

C. Thomassen. Planar representations of graphs. In: J.A. Bondy, U. S. R. Murty (eds.): Progress in Graph Theory. (1984) 43-69.

D. West. Introduction to Graph Theory. Prentice Hall, Upper Saddle River, NJ (1996).

A. White. Graphs, Groups and Surface.revised ed North-Holland, Amsterdam (1984).

S. Wismath.Characterizing bar line-of-sight graphs In: Proc. 1st Symp. Comp. Geom. ACM (1985) 147–152.