Two-bend 3D orthogonal point-drawings of graphs of maximum degree six
A 3D orthogonal point-drawing of a graph places its vertices at distinct points of the cubic lattice $\mathbb{Z}^3$ and draws each edge as a path along lattice lines between its endpoints, two paths meeting only at a common endpoint. A path with at most two bends consists of at most three axis-parallel segments.
Two bends per edge would be optimal, since every such drawing of $K_5$ has an edge with at least two bends. Wood showed that two bends per edge suffice for maximum degree at most $5$, and that graphs of maximum degree at most $6$ have drawings with at most $2 + \tfrac{2}{7}$ bends per edge on average; his thesis gives two-bend drawings of $K_7$, $K_{2,2,2,2}$, $K_{3,3,3}$ and $K_{6,6}$. Three bends per edge always suffice, even for multigraphs (Eades, Symvonis and Whitesides; Papakostas and Tollis; Wood).
Problem. Let $G$ be a simple graph whose vertices all have degree at most $6$. Must $G$ admit a 3D orthogonal point-drawing in which no edge is bent more than twice?
Source: Origin uncertain; likely Eades, Symvonis and Whitesides (2000); posed by Wood at the CCCG 2002 open-problem session; Problem 46 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- 3D orthogonal graph drawing, bends, The Open Problems Project
References
@article{eades2000,
author = {Eades, P. and Symvonis, A. and Whitesides, S.},
title = {Three dimensional orthogonal graph drawing algorithms},
journal = {Discrete Applied Math.},
volume = {103},
year = {2000},
pages = {55--87}
}
@article{wood2003,
author = {Wood, David R.},
title = {Optimal three-dimensional orthogonal graph drawing in the general position model},
journal = {Theoret. Comput. Sci.},
volume = {299},
number = {1--3},
year = {2003},
pages = {151--178},
doi = {10.1016/S0304-3975(02)00044-0}
}
@phdthesis{wood2000thesis,
author = {Wood, David R.},
title = {Three-Dimensional Orthogonal Graph Drawing},
school = {School of Computer Science and Software Engineering, Monash University},
address = {Melbourne, Australia},
year = {2000}
}
@article{papakostas1999,
author = {Papakostas, Achilleas and Tollis, Ioannis G.},
title = {Algorithms for incremental orthogonal graph drawing in three dimensions},
journal = {J. Graph Algorithms Appl.},
volume = {3},
number = {4},
year = {1999},
pages = {81--115}
}
@techreport{wood2001,
author = {Wood, David R.},
title = {Minimising the number of bends and volume in three-dimensional orthogonal graph drawings with a diagonal vertex layout},
institution = {University of Sydney},
number = {CS-AAG-2001-03},
year = {2001}
}
@inproceedings{demaine2003cccg2002,
author = {Demaine, Erik D. and O'Rourke, Joseph},
title = {Open Problems from {CCCG} 2002},
booktitle = {Proceedings of the 15th Canadian Conference on Computational Geometry},
address = {Halifax, Canada},
year = {2003},
pages = {178--181},
url = {https://erikdemaine.org/papers/CCCG2002Open/}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01092, "Two-bend 3D orthogonal point-drawings of graphs of maximum degree six", clopen.solutions.