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 , 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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/413

Actions (login required)

View Item