Book embedding

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 n vertices has book thickness at most ⌈ n / 2 ⌉ {displaystyle lceil n/2 ceil } , 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. 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. There are several open problems concerning book thickness. It is unknown whether the book thickness of an arbitrary graph can be bounded by a function of the book thickness of its subdivisions. 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. And, although every planar graph has book thickness at most four, it is unknown whether there exists a planar graph whose book thickness is exactly four. The notion of a book, as a topological space, was defined by C. A. Persinger and Gail Atneosen in the 1960s. 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 in the late 1980s that planar graphs have book thickness at most four, and the discovery in the late 1990s of close connections between book embeddings and bioinformatics. 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 z-axis of a Cartesian coordinate system and choosing the pages to be the k half-planes whose dihedral angle with respect to the xz-plane is an integer multiple of 2π/k.