Home | Issues | About JGAA | 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
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
Vol. 7, no. 4, pp. 363-398, 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 straight-line crossing-free drawings with vertices
located at (integral) grid points of ϕ? We characterize the
trees that can be drawn on a strip, i.e., on a two-dimensional 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 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. 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.
|
Journal Supporters
|