Book embedding
Encyclopedia
In graph theory
, book embedding is a generalization of planar embedding
to nonplanar surfaces in the form of a book, a collection of pages (half-planes) joined together at the spine of the book (the shared boundary of all the half-planes). The vertices of the graph are embedded on the spine, and each edge must lie in one of the pages. Book embeddings and book thickness were first studied by L. Taylor Ollman in 1973, and have since been studied by many other researchers from the points of view of graph theory, VLSI, and graph drawing
.
A book drawing of a graph G onto a book B is a drawing of G on B such that:
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.
. The book thickness is at most two if and only if the graph is a subgraph of a planar graph
with a Hamiltonian cycle; for instance, the Goldner–Harary graph
, a non-Hamiltonian maximal planar graph, provides an example of a planar graph that does not have book thickness two. 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. Graphs of treewidth k have book thickness at most k + 1. Graphs of genus
g have book thickness O(√g).
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, book embedding is a generalization of planar embedding
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
to nonplanar surfaces in the form of a book, a collection of pages (half-planes) joined together at the spine of the book (the shared boundary of all the half-planes). The vertices of the graph are embedded on the spine, and each edge must lie in one of the pages. Book embeddings and book thickness were first studied by L. Taylor Ollman in 1973, and have since been studied by many other researchers from the points of view of graph theory, VLSI, and graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
.
Definitions
A book B is a topological space consisting of a single line ℓ called the spine of B and a collection of k half-planes, with k ≥ 1, called the pages of B, each having ℓ 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
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
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 at most 1 if and only if it is outerplanarOuterplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
. The book thickness is at most two if and only if the graph is a subgraph of a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
with a Hamiltonian cycle; for instance, the Goldner–Harary graph
Goldner–Harary graph
In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal planar graph...
, a non-Hamiltonian maximal planar graph, provides an example of a planar graph that does not have book thickness two. Since finding Hamiltonian cycles in maximal planar graphs is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, 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. Graphs of treewidth k have book thickness at most k + 1. Graphs of genus
Genus (mathematics)
In mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It...
g have book thickness O(√g).