Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions

This paper investigates the following question: Given an integer grid ϕ, where ϕ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit straight-line crossingfree drawings with vertices located at the grid points of ϕ? We characterize the trees that can be drawn on a two dimensional c · n × к grid, where к and c are given integer constants, and on a two dimensional grid consisting of к 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 × 2 × 2 integer grid, called a box, does not admit the entire class of planar graphs.