Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing

Wood, David R. (2002) Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , pp. 312-327(Official URL:

Full text not available from this repository.


A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so that edges assigned to the same page can be drawn on that page without crossings. Given a graph G=(V,E), let f:V\rightarrow\mathbb {N} be a function such that 1\leq f(v)\leq\deg(v). We present a Las Vegas algorithm which produces a book embedding of G with O{\sqrt{\vert E\vert\cdot\max_v\lceil{\deg(v)/f(v)}\rceil}} pages, such that at most f(v) edges incident to a vertex v are on a single page. This algorithm generalises existing results for book embeddings. We apply this algorithm to produce 3-D orthogonal drawings with one bend per edge and O{\vert V\vert^{3/2}\vert E\vert} volume, and single-row drawings with two bends per edge and the same volume. In the produced drawings each edge is entirely contained in some Z-plane; such drawings are without so-called cross-cuts, and are particularly appropriate for applications in multilayer VLSI. Using a different approach, we achieve two bends per edge with O{\vert V\vert\vert E\vert} volume but with cross-cuts. These results establish improved bounds for the volume of 3-D orthogonal graph drawings.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_25
Classifications: G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D

Actions (login required)

View Item View Item