Directed VRRepresentable Graphs Have Unbounded DimensionRomanik, Kathleen (1995) Directed VRRepresentable Graphs Have Unbounded Dimension. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 177181(Official URL: http://dx.doi.org/10.1007/3540589503_369). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_369
AbstractVisibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. A threedimensional 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 zaxis, 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 nonzero 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 zaxis, and C does not intersect any other rectangle. A graph that can be represented in this way is called VRrepresentable. A VRrepresentation 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 VRrepresentable graphs is unbounded.
Actions (login required)
