The Complexity of Drawing Graphs on Few Lines and Few Planes

Steven Chaplick, Krzysztof Fleszar, Fabian Lipp +3

It is well known that any graph admits a crossing-free straight-line drawing in ${\mathbb{R}}^3$ and that any planar graph admits the same even in ${\mathbb{R}}^2$. For a graph $G$ and…