**Next:** Problem 47: Hinged Dissections

**Previous:** Problem 45: Smallest Universal Set of Points for Planar Graphs

- 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_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].- 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.

- [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.