Degree constrained book embeddings

Research output: Contribution to journalArticleResearchpeer-review

11 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 → N 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| · maxv ⌈deg(v)/f(v)⌉) pages, such that at most f(v) edges incident to a vertex v are on a single page. This result generalises that of Malitz [J. Algorithms 17 (1) (1994) 71-84].

Original languageEnglish
Pages (from-to)144-154
Number of pages11
JournalNumerical Algorithms
Volume45
Issue number2
DOIs
Publication statusPublished - Nov 2002
Externally publishedYes

Keywords

  • Book embedding
  • Book thickness
  • Graph
  • Las Vegas algorithm
  • Multilayer VLSI
  • Page degree
  • Page number
  • Pushdown graph

Cite this