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.

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)
planar graphs; box