Book embedding

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 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.

This is defined analogously to cutwidth as the maximum number of edges that can be crossed by a ray perpendicular to the spine within a single page.

(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.)

However, a detailed proof of this claim, announced in a subsequent journal paper,[5] was not known until 2020, when Bekos et al.[24] presented planar graphs with treewidth 4 that require four pages in any book embedding.

[25] Despite the existence of examples such as this one, Blankenship & Oporowski (1999) conjectured that a subdivision's book thickness cannot be too much smaller than that of the original graph.

[37] The edges within a single page of a book embedding behave in some ways like a stack data structure.

By analogy, researchers have defined a queue embedding of a graph to be an embedding in a topological book such that each vertex lies on the spine, each edge lies in a single page, and each two edges in the same page either cross or cover disjoint intervals on the spine.

[7] Unger (1992) claimed that finding three-page embeddings with a fixed spine ordering can also be performed in polynomial time although his writeup of this result omits many details.

A coloring of the circle graph represents a partition of the edges of G into subsets that can be drawn without crossing on a single page.

[44] If the spine ordering is unknown but a partition of the edges into two pages is given, then it is possible to find a 2-page embedding (if it exists) in linear time by an algorithm based on SPQR trees.

[48][49] For the same reason, the problem of testing whether a graph of bounded book thickness obeys a given formula of first order logic is fixed-parameter tractable.

They state that their system is capable of finding an optimal embedding for 400-vertex maximal planar graphs in approximately 20 minutes.

[35] One of the main motivations for studying book embedding cited by Chung, Leighton & Rosenberg (1987) involves an application in VLSI design, to the organization of fault-tolerant multiprocessors.

The network topologies that can be implemented by this system are exactly the ones that have book thickness at most equal to the number of bundles that have been made available.

[41] Book embedding may also be used to model the placement of wires connecting VLSI components into the layers of a circuit.

An influential result of Donald Knuth (1968) showed that a system that processes a data stream by pushing incoming elements onto a stack and then, at appropriately chosen times, popping them from the stack onto an output stream can sort the data if and only if its initial order is described by a permutation that avoids the permutation pattern 231.

[52] Since then, there has been much work on similar problems of sorting data streams by more general systems of stacks and queues.

In the system considered by Chung, Leighton & Rosenberg (1987), each element from an input data stream must be pushed onto one of several stacks.

Then, once all of the data has been pushed in this way, the items are popped from these stacks (in an appropriate order) onto an output stream.

Thus, a book embedding of this graph describes a partition of the paths into non-interfering subsets, and the book thickness of this graph (with its fixed embedding on the spine) gives the minimum number of distinct phases needed for a signalling schedule that includes all possible traffic paths through the junction.

[58][59] Planar graphs that do not have two-page book embeddings may also be drawn in a similar way, by allowing their edges to be represented by multiple semicircles above and below the line.

[64][65] Heuristic methods for reducing the crossing complexity have also been devised, based e.g. on a careful vertex insertion order and on local optimization.

[55] Two-page book embeddings with a fixed partition of the edges into pages can be interpreted as a form of clustered planarity, in which the given graph must be drawn in such a way that parts of the graph (the two subsets of edges) are placed in the drawing in a way that reflects their clustering.

Advantages of this formulation include the facts that it excludes structures that are actually knotted in space, and that it matches most known RNA pseudoknots.

[7] Because the spine ordering is known in advance for this application, testing for the existence of a bi-secondary structure for a given basepairing is straightforward.

[7] This characterization allows bi-secondary structures to be recognized in linear time as an instance of planarity testing.

[67] Pavan, Tewari & Vinodchandran (2012) used book embedding to study the computational complexity theory of the reachability problem in directed graphs.

However, reachability for three-page directed graphs requires the full power of nondeterministic logarithmic space.

A three-page book embedding of the complete graph K 5 . Because it is not a planar graph , it is not possible to embed this graph without crossings on fewer pages, so its book thickness is three.
The utility graph K 3,3 has no 2-page book embedding, but it can be drawn as shown in a 2-page book with only one crossing. Therefore, its 2-page book crossing number is 1.
This 1-page embedding of the diamond graph has pagewidth 3, because the yellow ray crosses three edges.
The Goldner–Harary graph , a planar graph with book thickness three
The book thickness of the diamond graph increases after edge subdivision
A circle graph , the intersection graph of chords of a circle. For book embeddings with a fixed vertex order, finding the book thickness is equivalent to coloring a derived circle graph.
A traffic intersection. The four incoming and four outgoing pairs of through lanes, two turn pockets, and four crosswalk corners can be represented as a set of 14 vertices on the spine of a book embedding, with edges representing connections between these points.
An arc diagram of the Goldner–Harary graph . In order to create a planar diagram, two triangles of the graph have been subdivided into four by the dashed red line, causing one of the graph edges to extend both above and below the line.
Circular layout of the Chvátal graph
A fragment of human telomerase showing a pseudoknot . If the fragment is stretched straight along the spine of a book embedding, the blue base pairs can be drawn in two non-crossing subsets above and below the spine, showing that this pseudoknot forms a bi-secondary structure.