Optimal 3D Angular Resolution for Low-Degree Graphs

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.