next up previous
Next: Problem 47: Hinged Dissections Up: The Open Problems Project Previous: Problem 45: Smallest Universal


Problem 46: 3D Minimum-Bend Orthogonal Graph Drawings

Statement
Does every simple graph with maximum vertex degree Δ≤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 K5 uses at least two bends on at least one edge. If Δ≤5, two bends per edge suffice [Woo03]. Two bends also suffice for the complete multipartite 6-regular graphs K7, K2, 2, 2, 2, K3, 3, 3, and K6, 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 Δ≤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 K5 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.


next up previous
Next: Problem 47: Hinged Dissections Up: The Open Problems Project Previous: Problem 45: Smallest Universal
The Open Problems Project - December 04, 2015