Directed VR-Representable Graphs Have Unbounded Dimension

Romanik, Kathleen (1995) Directed VR-Representable Graphs Have Unbounded Dimension. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 177-181 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_369).

Full text not available from this repository.

Abstract

Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. A three-dimensional visibility representation that has been studied is one in which each vertex of the graph maps to a closed rectangle in \mathbb{R}^3 and edges are expressed by vertical visibility between rectangles. The rectangles representing vertices are disjoint, contained in planes perpendicular to the z-axis, and have sides parallel to the x or y axes. Two rectangles R_{i} and R_{j} are considered visible provided that there exists a closed cylinder C of non-zero length and radius such that the ends of C are contained in R_{i} and R_{j}, the axis of C is parallel to the z-axis, and C does not intersect any other rectangle. A graph that can be represented in this way is called VR-representable. A VR-representation of a graph can be directed by directing all edges towards the positive z direction. A directed acyclic graph G has dimension d if d is the minimum integer such that the vertices of G can be ordered by d linear orderings, <_{1}...,<_{d}, and for vertices u und v there is a directed path from u to v if and only if u <_{i} v for all 1 \leq i \leq d. In this note we show that the dimension of the class of directed VR-representable graphs is unbounded.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_369
Classifications:Z Theory > Z.500 Representations
P Styles > P.900 Visibility
P Styles > P.060 3D
ID Code:146

Repository Staff Only: item control page

References

Prosenjit Bose, Hazel Everett, Sandor Fekete, Anna Lubiw, Henk Meijer, Kathleen Romanik, Tom Shermer, and Sue Whitesides. On a Visibility Representation for Graphs in Three Dimensions. In Davis Avis and Prosenjit Bose, editors, Snapshots in Computational and Discrete Geometry, Volume III. McGill University, July 1994. Technical Report AOCS-94.50.

Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Algorithms for Automatic Graph Drawing: An Annotated Bibliography. Technical report, Department of Computer Science, Brown University, 1993.

Giuseppe Di Battista and Roberto Tamassia. Algorithms for Plane Representations of Acyclic Digraphs. Theoretical Computer Science, 61:175-198, 1988.

Ivan Rival and Jorge Urrutia. Representing Orders by Translating Convex Figures in the Plane. Order 4, pages 319, 1988.

Ivan Rival and Jorge Urrutia. Representing Orders by Moving Figures in Space. Discrete Mathematics, 109:255-263, 1992.

William T. Trotter. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD, 1992.

Roberto Tamassia and Ioannis G. Tollis. A Unified Approach to Visibility Representations of Planar Graphs. Discrete Computational Geometry, 1:321-341, 1986.

Stephen K. Wismath. Characterizing Bar Line-of-Sight Graphs. In Proceedings of the First Annual Symposium on Computational Geometry, pages 147-152, Baltimore, MD, June 5-7 1985. ACM Press.