Bounded degree book embeddings and three-dimensional orthogonal graph drawing

Research output: Chapter in Book/Report/Conference proceedingChapter (Report)Researchpeer-review

12 Citations (Scopus)

Abstract

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 → ℕ 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 3-D orthogonal drawings with one bend per edge and O(|V| 3/ 2|E|) 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(|V||E|) volume but with cross-cuts. These results establish improved bounds for the volume of 3-D orthogonal graph drawings.

Original languageEnglish
Title of host publicationGraph Drawing - 9th International Symposium, GD 2001, Revised Papers
PublisherSpringer
Pages312-327
Number of pages16
Volume2265 LNCS
ISBN (Print)3540433090, 9783540433095
DOIs
Publication statusPublished - 2002
Externally publishedYes
EventGraph Drawing 2001 - Vienna, Austria
Duration: 23 Sep 200126 Sep 2001
Conference number: 9th
https://link.springer.com/book/10.1007/3-540-45848-4 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2265 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceGraph Drawing 2001
Abbreviated titleGD 2001
CountryAustria
CityVienna
Period23/09/0126/09/01
Internet address

Cite this

Wood, D. R. (2002). Bounded degree book embeddings and three-dimensional orthogonal graph drawing. In Graph Drawing - 9th International Symposium, GD 2001, Revised Papers (Vol. 2265 LNCS, pp. 312-327). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2265 LNCS). Springer. https://doi.org/10.1007/3-540-45848-4_25