Fully Dynamic 3-Dimensional Orthogonal Graph Drawing

Abstract

In a 3-dimensional orthogonal drawing of a graph, vertices are mapped to grid points on a 3-dimensional rectangular integer lattice and edges are routed along integer grid lines. In this paper, we present a technique that produces a 3D orthogonal drawing of any graph with $n$ vertices of degree 6 or less, using at most 6 bends per edge route and in a volume bounded by $O(n^2)$. The advantage of our strategy over previous drawing methods is that our method is fully dynamic, allowing both insertion and deletion of vertices and edges, while maintaining the volume and bend bounds. The drawing can be obtained in $O(n)$ time and insertions/deletions are performed in $O(1)$ time. Multiple edges and self loops are permitted. Three related constructions are also presented: a more elaborate construction that uses only 5 bends per edge, a simpler, more balanced drawing that requires at most 7 bends per edge, and a technique for displaying directed graphs.