# zbMATH — the first resource for mathematics

Straight-line drawings on restricted integer grids in two and three dimensions. (English) Zbl 1068.68103
Summary: This paper investigates the following question: Given a grid $$\phi$$, where $$\phi$$ 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 $$\phi$$? We characterize the trees that can be drawn on a strip, i.e., on a two-dimensional $$n\times 2$$ grid. For arbitrary graphs we prove lower bounds for the height $$k$$ of an $$n\times 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\times 2\times 2$$ integer grid, called a box, does not admit the entire class of planar graphs.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C62 Graph representations (geometric and intersection representations, etc.) 68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
##### Keywords:
planar graphs; box
Full Text: