book thickness

aka: stacknumber, pagenumber, fixed outerthickness

tags: topology

equivalent to: book thickness

providers: ISGCI

Relations

Results

• 2007 Graph Treewidth and Geometric Thickness Parameters by Dujmovic, Wood
  • page 7 : book thickness – A geometric drawing in which the vertices are in convex position is called a book embedding. The book thickness of a graph $G$, …, is the minimum $k \in \mathbb N$ such that there is book embedding of $G$ with thickness $k$.
  • page 8 : treewidth upper bounds book thickness by a linear function – The maximum book thickness … of a graph $\mathcal T_k$ (ed: $k$-tree) satisfy … $=k$ for $k \le 2$, $=k+1$ for $k \ge 3$.
• 2004 Track Layouts of Graphs by Dujmović, Pór, Wood
  • page 14 : book thickness upper bounds acyclic chromatic number by an exponential function – Theorem 5. Acyclic chromatic number is bounded by stack-number (ed: a.k.a. book-thickness). In particular, every $k$-stack graph $G$ has acyclich chromatic number $\chi_a(G) \le 80^{k(2k-1)}$.
• 1994 Genus g Graphs Have Pagenumber O(√g) by Malitz
  • page 24 : genus upper bounds book thickness by a linear function – Theorem 5.1. Genus $g$ graphs have pagenumber $O(\sqrt{g})$.
• https://en.wikipedia.org/wiki/Book_embedding
  • book thickness – … a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph.
• unknown source
  • treewidth upper bounds book thickness by a computable function
  • book thickness upper bounds acyclic chromatic number by a computable function