Размещение графов на полуплоскостях и книжное вложение графов

Graph layout on multiple half planes

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in 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 , 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.

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, 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
A book embedding of G onto B is a book drawing that forms a graph embedding of G into B. That is, it is a book drawing of G on B 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 G is the minimum number of pages required for a book embedding of G.
Another parameter that measures the quality of a book embedding, beyond its number of pages, is its pagewidth. 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. 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. and some graphs need this many spine crossings.

The book thickness of a given graph G is at most one if and only if G 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. 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. 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. that there exist some planar graphs that have book thickness exactly four. However, a detailed proof of this claim, announced in a subsequent journal paper, was not known until 2020, when Bekos et al. presented planar graphs with treewidth 4 that require four pages in any book embedding.

Subdividing every edge of a graph into two edge paths, by adding new vertices within each edge, may sometimes increase its book thickness. For instance, the diamond graph has book thickness one (it is outerplanar) but its subdivision has book thickness two (it is planar and subhamiltonian but not outerplanar). However, this subdivision process can also sometimes significantly reduce the book thickness of the subdivided graph. For instance, the book thickness of the complete graph Kn is proportional to its number of vertices, but subdividing each of its edges into a two edge path produces a subdivision whose book thickness is much smaller, only Despite the existence of examples such as this one, conjectured that a subdivision's book thickness cannot be too much smaller than that of the original graph. Specifically, they conjectured that there exists a function f such that, for every graph G and for the graph H formed by replacing every edge in G by a two edge path, if the book thickness of H is t then the book thickness of G is at most f(t). Their conjecture turned out to be false: graphs formed by Cartesian products of stars and triangular tilings have unbounded book thickness, but subdividing their edges into six edge paths reduces their book thickness to three.

Book thickness is related to thickness, the number of planar graphs needed to cover the edges of the given graph. A graph G has thickness θ if it can be drawn in the plane, and its edges colored with θ colors, in such a way that edges of the same color as each other do not cross. Analogously, a graph G has book thickness θ if it can be drawn in a half plane, with its vertices on the boundary of the half plane, with its edges colored with θ colors with no crossing between two edges of the same color. In this formulation of book thickness, the colors of the edges correspond to the pages of the book embedding. However, thickness and book thickness can be very different from each other: there exist graphs (subdivisions of complete graphs) that have unbounded book thickness, and this bound is tight for
k > 2. and graphs of genus g have book thickness More generally, every minor closed graph family has bounded book thickness. On the other hand, the 1 planar graphs, which are not closed under minors, but some 1 planar graphs including K2,2,2,2 have book thickness at least four. Every shallow minor of a graph of bounded book thickness is a sparse graph, whose ratio of edges to vertices is bounded by a constant that depends only on the depth of the minor and on the book thickness. That is, in the terminology of , the graphs of bounded book thickness have bounded expansion. Because graphs of book thickness two are planar graphs, they obey the planar separator theorem: they have separators, subsets of vertices whose removal splits the graph into pieces with at most 2n/3 vertices each, with only vertices in the separator. Here, n refers to the number of vertices in the graph. However, there exist graphs of book thickness three that do not have separators of sublinear size. The edges within a single page of a book embedding behave in some ways like a stack data structure. This can be formalized by considering an arbitrary sequence of push and pop operations on a stack, and forming a graph in which the stack operations correspond to the vertices of the graph, placed in sequence order along the spine of a book embedding. Then, if one draws an edge from each pop operation that pops an object x from the stack, to the previous push operation that pushed x, the resulting graph will automatically have a one page embedding. For this reason, the page number of a graph has also been called its stack number. In the same way, one may consider an arbitrary sequence of enqueue and dequeue operations of a queue data structure, and form a graph that has these operations as its vertices, placed in order on the spine of a single page, with an edge between each enqueue operation and the corresponding dequeue. Then, in this graph, each two edges will either cross or cover disjoint intervals on the spine. 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. The minimum number of pages needed for a queue embedding of a graph is called its queue number.

Finding the book thickness of a graph is NP hard. This follows from the fact that finding Hamiltonian cycles in maximal planar graphs is NP complete. In a maximal planar graph, the book thickness is two if and only if a Hamiltonian cycle exists. Therefore, it is also NP complete to test whether the book thickness of a given maximal planar graph is two. However, for graphs that require four or more pages, the problem of finding an embedding with the minimum possible number of pages remains NP hard, via an equivalence to the NP hard problem of coloring circle graphs, the intersection graphs of chords of a circle. Given a graph G with a fixed spine ordering for its vertices, drawing these vertices in the same order around a circle and drawing the edges of G as line segments produces a collection of chords representing G. One can then form a circle graph that has the chords of this diagram as vertices and crossing pairs of chords as edges. 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. Therefore, an optimal coloring is equivalent to an optimal book embedding. Since circle graph coloring with four or more colors is NP hard, and since any circle graph can be formed in this way from some book embedding problem, it follows that optimal book embedding is also NP hard. For a fixed vertex ordering on the spine of a two page book drawing, it is also NP hard to minimize the number of crossings when this number is nonzero. However, it is NP complete to find a 2 page embedding when neither the spine ordering nor the edge partition is known. Finding the book crossing number of a graph is also NP hard, because of the NP completeness of the special case of testing whether the 2 page crossing number is zero. As a consequence of bounded expansion, the subgraph isomorphism problem, of finding whether a pattern graph of bounded size exists as a subgraph of a larger graph, can be solved in linear time when the larger graph has bounded book thickness. The same is true for detecting whether the pattern graph is an induced subgraph of the larger graph, or whether it has a graph homomorphism to the larger graph. 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. describe a system for finding optimal book embeddings by transforming the problem into an instance of the Boolean satisfiability problem and applying a SAT solver to the resulting problem. They state that their system is capable of finding an optimal embedding for 400 vertex maximal planar graphs in approximately 20 minutes. Book embedding may also be used to model the placement of wires connecting VLSI components into the layers of a circuit.

Book embedding has also been frequently applied in the visualization of network data. Two of the standard layouts in graph drawing, arc diagrams or linear embedding 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. Such a drawing is not a book embedding by the usual definition, but has been called a topological book embedding. For every planar graph, it is always possible to find such an embedding in which each edge crosses the spine at most once. In another drawing style, the circular layout, the vertices of a graph are placed on a circle and the edges are drawn either inside or outside the circle. Again, a placement of the edges within the circle (for instance as straight line segments) corresponds to a one page book drawing, while a placement both inside and outside the circle corresponds to a two page book drawing. For one page drawings of either style, it is important to keep the number of crossings small as a way of reducing the visual clutter of the drawing. Minimizing the number of crossings is NP complete, Minimizing the one page or two page crossing number is fixed parameter tractable when parameterized by the cyclomatic number of the given graph, or by a combination of the crossing number and the treewidth of the graph. Heuristic methods for reducing the crossing complexity have also been devised, based e. g. on a careful vertex insertion order and on local optimization. Book embeddings with more than two pages have also been used to construct three dimensional drawings of graphs. In particular, used a construction for book embeddings that keep the degree of each vertex within each page low, as part of a method for embedding graphs into a three dimensional grid of low volume.

In the study of how RNA molecules fold to form their structure, the standard form of nucleic acid secondary structure can be described diagrammatically as a chain of bases (the RNA sequence itself), drawn along a line, together with a collection of arcs above the line describing the basepairs of the structure. That is, although these structures actually have a complicated three dimensional shape, their connectivity (when a secondary structure exists) can be described by a more abstract structure, a one page book embedding. However, not all RNA folds behave in this simple way. have proposed a so called "bi secondary structure" for certain RNA pseudoknots that takes the form of a two page book embedding: the RNA sequence is again drawn along a line, but the basepairs are drawn as arcs both above and below this line. In order to form a bi secondary structure, a graph must have maximum degree at most three: each base can only participate in one arc of the diagram, in addition to the two links to its neighbors in the base sequence. 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. 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. The problem of assigning edges to the two pages in a compatible way can be formulated as either an instance of 2 satisfiability, or as a problem of testing the bipartiteness of the circle graph whose vertices are the basepairs and whose edges describe crossings between basepairs. And if an RNA structure is tertiary rather than bi secondary (that is, if it requires more than two pages in its diagram), then determining the page number is again NP hard.

study applications of book thickness in abstract algebra, using graphs defined from the zero divisors of a finite local ring by making a vertex for each zero divisor and an edge for each pair of values whose product is zero. In a multi paper sequence, Dynnikov has studied the topological book embeddings of knots and links, showing that these embeddings can be described by a combinatorial sequence of symbols and that the topological equivalence of two links can be demonstrated by a sequence of local changes to the embeddings.