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 , pp. 328-342(Official URL:

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_26
Classifications: P Styles > P.720 Straight-line
M Methods > M.600 Planar
G Algorithms and Complexity > G.420 Crossings
P Styles > P.060 3D

Actions (login required)

View Item View Item