| x (2007) | |||||||||||||
Abstract | |||||||||||||
| Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit board layout have stimulated research on visibility representations where the sets belong to R 2. Here, motivated by the emerging research area of graph drawing, we study a 3-dimensional visibility representation. In this representation, each vertex of the graph maps to a closed rectangle in R 3 such that the rectangles are disjoint, the planes determined by the rectangles are perpendicular to the z-axis, and the sides of the rectangles are parallel to the x or y axes. Edges are expressed by the following visibility relation. 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. If a graph can be represented in this way, we say that the graph is VRR-representable. Our main results are as follows. All planar graphs are VRR-representable, as are many non-planar graphs. In particular, Kn is VRR-representable for values of n 20. However, Kn is not VRR-representable for n 103. The complete bipartite graph K m;n is VRR-representable for all m and n. We provide bounds on the representability of complete bipartite graphs minus a perfect matching. We also provide bounds on the representability of tripartite graphs. Furthermore, we show that the family of VRRrepresentable graphs is not closed under graph minors. Finally, we consider variant VRR-representations, where the rectangles are replaced by squares and discs, and provide bounds on the complete graphs and complete bipartite graphs that admit such representations. 1 | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||