Book embedding

In graph theory, book embedding is a generalization of planar embedding to nonplanar surfaces in the form of a "book", a collection of "pages" (halfplanes) joined together at the "spine" of the book (the shared boundary of all the halfplanes). The vertices of the graph are embedded on the spine, and each edge must lie in one of the faces. Book embeddings and book thickness were first studied by L. Taylor Ollman in 1973, [citation|first=L. Taylor|last=Ollmann|contribution=On the book thicknesses of various graphs|editor1-first=Frederick|editor1-last=Hoffman|editor2-first=Roy B.|editor2-last=Levow|editor3-first=Robert S. D.|editor3-last=Thomas|title=Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing|volume=VIII|series=Congressus Numerantium|page=459|year=1973.] and have since been studied by many other researchers from the points of view of graph theory, VLSI, and graph drawing.

Definitions

a book "B" is a topological space consisting of a single line "l" called the spine of "B" and a collection of "k" half-planes, with $kge1$, called the pages of "B", each having "l" as its boundary.

A book drawing of a graph "G" onto a book "B" is a drawing of "G" on "B" such that:

*every vertex of "G" is mapped to the spine of "B"; and
*every edge of "G" is mapped to a single page of "B".

A book embedding of "G" onto "B" is a graph embedding of "G" into "B", i.e., the drawing of "G" on "B" without crossings.The book thickness or pagenumber of "G" is the minimum number of pages required for a book embedding of "G".

Relations to other graph properties

The book thickness of a graph is one if and only if it is outerplanar. The book thickness is two if and only if the graph is a subgraph of a planar graph with a Hamiltonian cycle; [citation|first1=Frank R.|last1=Bernhart|first2=Paul C.|last2=Kainen|title=The book thickness of a graph|journal=Journal of Combinatorial Theory, Series B|volume=27|issue=3|pages=320–331|year=1979.] since finding Hamiltonian cycles in maximal planar graphs is NP-complete, so is the problem of testing whether the book thickness is two. All planar graphs have book thickness at most four, and some planar graphs have book thickness exactly four. [citation|contribution=Four pages are necessary and sufficient for planar graphs|first=Mihalis|last=Yannakakis|authorlink=Mihalis Yannakakis|title=Proc. 18th ACM Symp. Theory of Computing (STOC)|year=1986|pages=104–108|doi=10.1145/12130.12141.] Graphs of treewidth "k" have book thickness at most "k" + 1. [citation|first1=Vida|last1=Dujmović|first2=David R.|last2=Wood|title=Graph treewidth and geometric thickness parameters|journal=Discrete & Computational Geometry|volume=37|issue=4|year=2007|pages=641–670|doi=10.1007/s00454-007-1318-7.]

Generalizations

A generalization of this concept is to allow the embedded edges to cross the spine. Some authors call this notion topological book embedding of graphs, and it is a topic of algorithmic research as well. [citation|first=Miki|last=Miyaguchi|title=Topological book embedding of bipartite graphs|journal=IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences|year=2006|volume=E89-A|issue=5|pages=1223–1226|doi=0.1093/ietfec/e89-a.5.1223.]

References