3D Minimum-Bend Orthogonal Graph Drawings

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph with maximum degree at most six. A three-dimensional orthogonal point drawing assigns each vertex a distinct point of $\mathbb Z^3$. Each edge is represented by a polygonal path joining its assigned endpoints, with all links parallel to coordinate axes and all bends at lattice points.

Paths for different edges may intersect only at their common graph endpoints. An edge may not pass through a nonincident vertex or overlap another edge along an interval. A bend is a change between two perpendicular coordinate directions, after redundant collinear links have been removed.

Does every such $G$ have an orthogonal point drawing in which each edge has at most two bends, hence at most three links? The bound is imposed separately on every edge, not merely on the average number of bends. The lattice box may be chosen as large as needed; no prescribed volume bound is part of this existence question.

The degree restriction reflects the six available axis directions at a lattice point. Allowing vertices to occupy boxes with many attachment ports, permitting crossings, or replacing the bound by three bends gives different drawing problems.

Short English statement

Can every graph of maximum degree six be drawn without crossings on the three-dimensional cubic lattice using at most two right-angle bends per edge?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500046 (AMR-054-0046), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 46. Original source indexed by AMR-054-0046. https://topp.openproblem.net/p46.