Home  Issues  Aims and Scope  Instructions for Authors 
Advances in Graph Drawing. Special Issue on Selected Papers from
the Ninth International Symposium on Graph Drawing, GD 2001
DOI: 10.7155/jgaa.00075
StraightLine Drawings on Restricted Integer Grids in Two and Three Dimensions
Vol. 7, no. 4, pp. 363398, 2003. Regular paper.
Abstract This paper investigates the following question: Given a grid ϕ,
where ϕ is a proper subset of the integer 2D or 3D grid, which
graphs admit straightline crossingfree drawings with vertices
located at (integral) grid points of ϕ? We characterize the
trees that can be drawn on a strip, i.e., on a twodimensional n×2 grid.
For arbitrary graphs we prove lower bounds for the
height k of an n×k grid required for a drawing of the graph.
Motivated by the results on the plane we investigate
restrictions of the integer grid in 3D 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. We also show that there exist
planar graphs that cannot be drawn on the prism and that extension to
an n ×2 ×2 integer grid, called a box, does not admit the
entire class of planar graphs.
