Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Optimal 3D Angular Resolution for Low-Degree Graphs
Vol. 17, no. 3, pp. 173-200, 2013. Regular paper.
Abstract We show that every graph of maximum degree three can be drawn without crossings in three dimensions with at most two bends per edge, and with 120° angles between all pairs of edge segments that meet at a vertex or a bend. We show that every graph of maximum degree four can be drawn in three dimensions with at most three bends per edge, and with 109.5° angles, i. e., the angular resolution of the diamond lattice, between all pairs of edge segments that meet at a vertex or a bend. The angles in these drawings are the best possible given the degrees of the vertices.
Submitted: July 2011.
Reviewed: May 2012.
Revised: January 2013.
Accepted: February 2013.
Final: February 2013.
Published: March 2013.
Communicated by Henk Meijer