StraightLine Drawings on Restricted Integer Grids in Two and Three Dimensions (Extended Abstract)Felsner, Stefan and Liotta, Giuseppe and Wismath, Stephen (2002) StraightLine Drawings on Restricted Integer Grids in Two and Three Dimensions (Extended Abstract). In: Graph Drawing 9th International Symposium, GD 2001, September 2326, 2001 , pp. 328342(Official URL: http://dx.doi.org/10.1007/3540458484_26). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540458484_26
AbstractThis 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 straightline crossingfree 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 crossingfree 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 crossingfree straight line 3d drawings in linear volume for a nontrivial 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.
Actions (login required)
