## Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing
Wood, David R.
(2002)
Full text not available from this repository. ## AbstractA 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.
Repository Staff Only: item control page References |