Logo

Login

On Polar Visibility Representations of Graphs

Hutchinson, Joan P. (2001) On Polar Visibility Representations of Graphs. [Conference Paper]

This is the latest version of this eprint.

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
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.900 Visibility
P Styles > P.999 Others
ID Code:305
Deposited By:Selbach, Anna
Deposited On:14 Apr 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1984&spage=63

Available Versions of this Item

Repository Staff Only: item control page

References

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

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

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

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

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

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

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

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

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

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

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

_____: Tesselation representations of planar graphs. In: Medanic, J. V., Kumar, P. R. (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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.