A Layout Algorithm for Bar-Visibility Graphs on the Möbius Band

Dean, Alice M. (2001) A Layout Algorithm for Bar-Visibility Graphs on the Möbius Band. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 350-359 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_33).

Full text not available from this repository.

Abstract

We characterize two types of bar-visibility graphs on the Möbius band (abbreviated "BVGMs"), in which vertices correspond to intervals that are parallel or orthogonal to the axis of the band, depending on type, and in which adjacency corresponds to orthogonal visibility of intervals. BVGMs with intervals orthogonal to the axis are shown to be equivalent to the "polar visibility graphs" studied by Hutchinson [7]. BVGMs with intervals parallel to the axis are characterized as those graphs G which satisfy the following conditions: G is embedded on the Möbius band; the block-cutpoint tree of G is a caterpillar in which all but at most one block is planar; and the non-planar block, if it exists, is at the "head" of the caterpillar.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_33
Classifications:M Methods > M.999 Others
Z Theory > Z.999 Others
G Algorithms and Complexity > G.490 Embeddings
Z Theory > Z.750 Topology
G Algorithms and Complexity > G.999 Others
ID Code:413

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the visualization of graphs. Prentice Hall, Upper Saddle River, NJ, 1999.

A. M. Dean. Bar-visibility graphs on the Möbius band. Manuscript, 1999.

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

A. M. Dean and J. P. Hutchinson. Rectangle-visibility of unions and products of trees. J. Graph Algorithms and Applications, 2:1-21, 1998.

A. M. Dean and J. P. Hutchinson. Rectangle-visibility graphs on surfaces. Manuscript, 1999.

S. Even and R. E. Tarjan. Computing an st-numbering. Theoret. Comput. Sci., 2:339-344, 1976.

J. P. Hutchinson. On polar visibility representations of graphs. In: Proc. Graph Drawing 2000, J. Marks, ed., to appear.

J. P. Hutchinson, T. Shermer, and A. Vince. On representations of some thickness-two graphs (extended abstract). In: Lecture Notes in Computer Science #1027, F. Brandenburg, ed., Springer, Berlin, 159-166, 1995.

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

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

R. Tamassia and I. G. Tollis. Tessellation representations of planar graphs. In: Proc. 27th Annual Allerton Conf., University of Illinois at Urbana-Champaign, 48-57, 1989.

R. Tamassia and I. G. Tollis Representations of graphs on a cylinder. SIAM J. Disc. Math., 4:139-149, 1991.

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

S. K. Wismath. Characterization bar line-of-sight graphs. In: Proc. 1st ACM Symp. Comput. Geom., 147-152, 1985.