Next: Problem 47: Hinged Dissections
Previous: Problem 45: Smallest Universal Set of Points for Planar Graphs
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).
Likely [ESW00].
Open.
Two bends would be best possible, because any drawing of K_5 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_7, 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 2 n \times 2 n rectangle of the grid [Sch95]. On the other hand, as in 3D, any drawing of K_5 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].
[ESW00]. Posed by David Wood at the CCCG 2002 open-problem session [DO03b].
graph drawing
E. Demaine, 21 Dec. 2002; 17 July 2005.
Therese Biedl and G. Kant. A better heuristic for orthogonal graph drawings. Comput. Geom. Theory Appl., 9:159–180, 1998.
Erik D. Demaine and Joseph O’Rourke. . In Proceedings of the 15th Canadian Conference on Computational Geometry, pages 178–181, Halifax, Canada, August 2003.
P. Eades, A. Symvonis, and S. Whitesides. Three dimensional orthogonal graph drawing algorithms. Discrete Applied Math., 103:55–87, 2000.
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.
Achilleas Papakostas and Ioannis G. Tollis. Algorithms for incremental orthogonal graph drawing in three dimensions. J. Graph Algorithms Appl., 3(4):81–115, 1999.
M. Schäffter. Drawing graphs on rectangular grids. Discrete Appl. Math., 63:75–89, 1995.
David R. Wood. Three-Dimensional Orthogonal Graph Drawing. PhD thesis, School of Computer Science and Software Engineering, Monash University, Melbourne, Australia, 2000.
David R. Wood. Optimal three-dimensional orthogonal graph drawing in the general position model. Theoret. Comput. Sci., 299(1–3):151–178, 2003.
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.