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

Authors

  • Stefan Felsner
  • Giuseppe Liotta
  • Stephen Wismath

DOI:

https://doi.org/10.7155/jgaa.00075

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.

Downloads

Download data is not yet available.

Downloads

Published

2003-01-01

How to Cite

Felsner, S., Liotta, G., & Wismath, S. (2003). Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions. Journal of Graph Algorithms and Applications, 7(4), 363–398. https://doi.org/10.7155/jgaa.00075