Book Thickness

In graph theory, 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. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

Every graph with vertices has book thickness at most $\lceil n/2\rceil$, and this formula gives the exact book thickness for complete graphs. The graphs with book thickness one are the outerplanar graphs. The graphs with book thickness at most two are the subhamiltonian graphs, which are always planar; more generally, every planar graph has book thickness at most four. All minor-closed graph families, and in particular the graphs with bounded treewidth or bounded genus, also have bounded book thickness. It is NP-hard to determine the exact book thickness of a given graph, with or without knowing a fixed vertex ordering along the spine of the book. Testing the existence of a three-page book embedding of a graph, given a fixed ordering of the vertices along the spine of the embedding, has unknown computational complexity: it is neither known to be solvable in polynomial time nor known to be NP-hard.

One of the original motivations for studying book embeddings involved applications in VLSI design, in which the vertices of a book embedding represent components of a circuit and the wires represent connections between them. Book embedding also has applications in graph drawing, where two of the standard visualization styles for graphs, arc diagrams and circular layouts, can be constructed using book embeddings.

In transportation planning, the different sources and destinations of foot and vehicle traffic that meet and interact at a traffic light can be modeled mathematically as the vertices of a graph, with edges connecting different source-destination pairs. A book embedding of this graph can be used to design a schedule that lets all the traffic move across the intersection with as few signal phases as possible. In bioinformatics problems involving the folding structure of RNA, single-page book embeddings represent classical forms of nucleic acid secondary structure, and two-page book embeddings represent pseudoknots. Other applications of book embeddings include abstract algebra and knot theory.

History

The notion of a book, as a topological space, was defined by C. A. Persinger and Gail Atneosen in the 1960s.. See also . As part of this work, Atneosen already considered embeddings of graphs in books. The embeddings he studied used the same definition as embeddings of graphs into any other topological space: vertices are represented by distinct points, edges are represented by curves, and the only way that two edges can intersect is for them to meet at a common endpoint.

In the early 1970s, Paul C. Kainen and L. Taylor Ollmann developed a more restricted type of embedding that came to be used in most subsequent research. In their formulation, the graph's vertices must be placed along the spine of the book, and each edge must lie in a single page.
Important milestones in the later development of book embeddings include the proof by Mihalis Yannakakis have book thickness at most four, and the discovery in the late 1990s of close connections between book embeddings and bioinformatics.

Definitions

A book is a particular kind of topological space, also called a fan of half-planes... It consists of a single line , called the spine or back of the book, together with a collection of one or more half-planes, called the pages or leaves of the book, each having the spine as its boundary. Books with a finite number of pages can be embedded into three-dimensional space, for instance by choosing to be the -axis of a Cartesian coordinate system and choosing the pages to be the half-planes whose dihedral angle with respect to the -plane is an integer multiple of .

A book drawing of a finite graph onto a book is a drawing of on such that every vertex of is drawn as a point on the spine of , and every edge of is drawn as a curve that lies within a single page of . The -page book crossing number of is the minimum number of crossings in a -page book drawing..

A book embedding of onto is a book drawing that forms a graph embedding of into . That is, it is a book drawing of on that does not have any edge crossings.
Every finite graph has a book embedding onto a book with a large enough number of pages. For instance, it is always possible to embed each edge of the graph on its own separate page.
The book thickness, pagenumber, or stack number of is the minimum number of pages required for a book embedding of .
Another parameter that measures the quality of a book embedding, beyond its number of pages, is its pagewidth. This is the maximum number of edges that can be crossed by a ray perpendicular to the spine within a single page. Equivalently (for book embeddings in which each edge is drawn as a monotonic curve), it is the maximum size of a subset of edges within a single page such that the intervals defined on the spine by pairs of endpoints of the edges all intersect each other.

It is crucial for these definitions that edges are only allowed to stay within a single page of the book. As Atneosen already observed, if edges may instead pass from one page to another across the spine of the book, then every graph may be embedded into a three-page book. For such a three-page topological book embedding in which spine crossings are allowed, every graph can be embedded with at most a logarithmic number of spine crossings per edge,. and some graphs need this many spine crossings.

Specific graphs

As shown in the first figure, the book thickness of the complete graph is three: as a non-planar graph its book thickness is greater than two, but a book embedding with three pages exists. More generally, the book thickness of every complete graph with vertices is exactly $\lceil n/2\rceil$. This result also gives an upper bound on the maximum possible book thickness of any -vertex graph.

The two-page crossing number of the complete graph is
:$\frac \biggl\lfloor\frac\biggr\rfloor\biggl\lfloor\frac\biggr\rfloor\biggl\lfloor\frac\biggr\rfloor\biggl\lfloor\frac\biggr\rfloor,$
matching a still-unproven conjecture of Anthony Hill on what the unrestricted crossing number of this graph should be. That is, if Hill's conjecture is correct, then the drawing of this graph that minimizes the number of crossings is a two-page drawing.

The book thickness of the complete bipartite graph is at most . To construct a drawing with this book thickness, for each vertex on the smaller side of the bipartition, one can place the edges incident with that vertex on their own page. This bound is not always tight; for instance, has book thickness three, not four. However, when the two sides of the graph are very unbalanced, with , the book thickness of is exactly .

For the Turán graph (a complete multipartite graph formed from independent sets of vertices per independent set, with an edge between every two vertices from different independent sets) the book thickness is sandwiched between
:$\left\lceil \frac\right\rceil \le t \le \left\lceil \frac \right\rceil$
and when is odd the upper bound can be improved to
:$t\le (r-1)\left\lceil\frac\right\rceil + \left\lceil \frac \right\rceil.$

The book thickness of binary de Bruijn graphs, shuffle-exchange graphs, and cube-connected cycles (when these graphs are large enough to be nonplanar) is exactly three.

Properties

Planarity and outerplanarity

The book thickness of a given graph is at most one if and only if is an outerplanar graph. An outerplanar graph is a graph that has a planar embedding in which all vertices belong to the outer face of the embedding. For such a graph, placing the vertices in the same order along the spine as they appear in the outer face provides a one-page book embedding of the given graph. (An articulation point of the graph will necessarily appear more than once in the cyclic ordering of vertices around the outer face, but only one of those copies should be included in the book embedding.) Conversely, a one-page book embedding is automatically an outerplanar embedding. For, if a graph is embedded on a single page, and another half-plane is attached to the spine to extend its page to a complete plane, then the outer face of the embedding includes the entire added half-plane, and all vertices lie on this outer face.

Every two-page book embedding is a special case of a planar embedding, because the union of two pages of a book is a space topologically equivalent to the whole plane. Therefore, every graph with book thickness two is automatically a planar graph. More precisely, the book thickness of a graph is at most two if and only if is a subgraph of a planar graph that has a Hamiltonian cycle.. If a graph is given a two-page embedding, it can be augmented to a planar Hamiltonian graph by adding (into any page) extra edges between any two consecutive vertices along the spine that are not already adjacent, and between the first and last spine vertices. The Goldner–Harary graph provides an example of a planar graph that does not have book thickness two: it is a maximal planar graph, so it is not possible to add any edges to it while preserving planarity, and it does not have a Hamiltonian cycle. Because of this characterization by Hamiltonian cycles, graphs that have two-page book embeddings are also known as subhamiltonian graphs..

All planar graphs whose maximum degree is at most four have book thickness at most two.. Planar 3-trees have book thickness at most three.. More generally, all planar graphs have book thickness four. It has been claimed by Mihalis Yannakakis

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases