Abstract
A 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 → ℕ be a function such that 1 ≤ f(v) ≤ deg(v). We present a Las Vegas algorithm which produces a book embedding of G with O(√E · max _{v}[deg(v)/f(v)]) 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(V ^{3}/ ^{2}E) 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(VE) volume but with crosscuts. These results establish improved bounds for the volume of 3D orthogonal graph drawings.
Original language  English 

Title of host publication  Graph Drawing  9th International Symposium, GD 2001, Revised Papers 
Publisher  Springer 
Pages  312327 
Number of pages  16 
Volume  2265 LNCS 
ISBN (Print)  3540433090, 9783540433095 
DOIs  
Publication status  Published  2002 
Externally published  Yes 
Event  Graph Drawing 2001  Vienna, Austria Duration: 23 Sep 2001 → 26 Sep 2001 Conference number: 9th https://link.springer.com/book/10.1007/3540458484 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Volume  2265 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  Graph Drawing 2001 

Abbreviated title  GD 2001 
Country/Territory  Austria 
City  Vienna 
Period  23/09/01 → 26/09/01 
Internet address 
