Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (Extended Abstract)
Felsner, Stefan and Liotta, Giuseppe and Wismath, Stephen (2002) Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (Extended Abstract). In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 328-342 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_26).
Full text not available from this repository.
This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit straight-line crossing-free drawings with vertices located at the grid points of $\phi$? We characterize the trees that can be drawn on a two dimensional $c \cdot n \times k$ grid, where $k$ and $c$ are given integer constants, and on a two dimensional grid consisting of $k$ parallel horizontal lines of infinite length. Motivated by the results on the plane we investigate restrictions of the integer grid in 3 dimensions and show that every outerplanar graph with $n$ vertices can be drawn crossing-free with straight lines in linear volume on a grid called a prism. This prism consists of $3n$ integer grid points and is universal - it supports all outerplanar graphs of $n$ vertices. This is the first algorithm that computes crossing-free straight line 3d drawings in linear volume for a non-trivial family of planar graphs. We also show that there exist planar graphs that cannot be drawn on the prism and that the extension to a $n \times 2 \times 2$ integer grid, called a box, does not admit the entire class of planar graphs.
Repository Staff Only: item control page