Bounded Degree Book Embeddings and ThreeDimensional Orthogonal Graph DrawingWood, David R. (2002) Bounded Degree Book Embeddings and ThreeDimensional Orthogonal Graph Drawing. In: Graph Drawing 9th International Symposium, GD 2001, September 2326, 2001 , pp. 312327(Official URL: http://dx.doi.org/10.1007/3540458484_25). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540458484_25
AbstractA book embedding of a graph consists of a linear ordering of the vertices along a line in 3space (the spine), and an assignment of edges to halfplanes 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 3D orthogonal drawings with one bend per edge and O{\vert V\vert^{3/2}\vert E\vert} volume, and singlerow drawings with two bends per edge and the same volume. In the produced drawings each edge is entirely contained in some Zplane; such drawings are without socalled crosscuts, 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 crosscuts. These results establish improved bounds for the volume of 3D orthogonal graph drawings.
Actions (login required)
