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.