Problem 46: 3D Minimum-Bend Orthogonal Graph Drawings

Statement

Does every simple graph with maximum vertex degree $\Delta$ $\leq$ 6 have a 3D orthogonal point-drawing with no more than two bends per edge? A 3D orthogonal point-drawing of a graph maps each vertex to a unique point of the 3D cubic lattice, and maps each edge to a lattice path between the endpoints; these paths can only intersect at common endpoints. In this problem, each path must have at most two bends, that is, consist of at most three orthogonal line segments (links).

Origin

Likely [ESW00].

Status/Conjectures

Open.

Partial and Related Results

Two bends would be best possible, because any drawing of K₅ uses at least two bends on at least one edge. If $\Delta$ $\leq$ 5, two bends per edge suffice [Woo03]. Two bends also suffice for the complete multipartite 6-regular graphs K₇, K_{2, 2, 2, 2}, K_{3, 3, 3}, and K_{6, 6} [Woo00]. In general, there is a drawing with an average number of bends per edge of at most 2 + ${\frac{{2}}{{7}}}$ [Woo03]. Additionally, three bends per edge always suffice, even for multigraphs [ESW00,PT99,Woo01].

Two-dimensional versions of this problem have also been studied. A 2D orthogonal point-drawing of a graph maps each vertex to a unique point of the 2D square lattice, and maps each edge to a lattice path between the endpoints; the paths are allowed to intersect at common endpoints and at proper crossings (points at which two paths meet but do not bend), but must be edge-disjoint. Every graph with maximum vertex degree $\Delta$ $\leq$ 4 has a 2D orthogonal point-drawing with at most two bends per edge, and furthermore within a 2n×2n rectangle of the grid [Sch95]. On the other hand, as in 3D, any drawing of K₅ uses at least two bends on at least one edge [Sch95], so two bends is again best possible. For planar graphs, we can ask for 2D orthogonal point-drawings that have no (proper) crossings. In this case, again there are drawings with at most two bends per edge, unless the graph has a connected component isomorphic to the icosohedron, in which case three bends per edge is the best possible [BK98,LMS98].

Appearances

[ESW00]. Posed by David Wood at the CCCG 2002 open-problem session [DO03b].

Categories

graph drawing

Entry Revision History

E. Demaine, 21 Dec. 2002; 17 July 2005.

Bibliography

BK98

Therese Biedl and G. Kant.
A better heuristic for orthogonal graph drawings.
Comput. Geom. Theory Appl., 9:159-180, 1998.

DO03b

Erik D. Demaine and Joseph O'Rourke.
Open problems from CCCG 2002.
In Proceedings of the 15th Canadian Conference on Computational Geometry, August 2003.
To appear; http://arXiv.org/archive/cs/0212050.

ESW00

P. Eades, A. Symvonis, and S. Whitesides.
Three dimensional orthogonal graph drawing algorithms.
Discrete Applied Math., 103:55-87, 2000.

LMS98

Yanpei Liu, Aurora Morgana, and Bruno Simeone.
A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid.
Discrete Applied Math., 81(1-3):69-91, January 1998.

PT99

Achilleas Papakostas and Ioannis G. Tollis.
Algorithms for incremental orthogonal graph drawing in three dimensions.
J. Graph Algorithms Appl., 3(4):81-115, 1999.

Sch95

M. Schäffter.
Drawing graphs on rectangular grids.
Discrete Appl. Math., 63:75-89, 1995.

Woo00

David R. Wood.
Three-Dimensional Orthogonal Graph Drawing.
PhD thesis, School of Computer Science and Software Engineering, Monash University, Melbourne, Australia, 2000.

Woo03

David R. Wood.
Optimal three-dimensional orthogonal graph drawing in the general position model.
Theoret. Comput. Sci., 2003.
To appear.

Woo01

David R. Wood.
Minimising the number of bends and volume in three-dimensional orthogonal graph drawings with a diagonal vertex layout.
Technical Report CS-AAG-2001-03, University of Sydney, 2001.