Book embedding - Knowledge

1851:

order around the junction. The paths through the intersection taken by traffic to get from an incoming lane to an outgoing lane may be represented as the edges of an undirected graph. For instance, this graph might have an edge from an incoming to an outgoing lane of traffic that both belong to the same segment of road, representing a U-turn from that segment back to that segment, only if U-turns are allowed at the junction. For a given subset of these edges, the subset represents a collection of paths that can all be traversed without interference from each other if and only if the subset does not include any pair of edges that would cross if the two edges were placed in a single page of a book embedding. 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.

1777:: connecting one of the processors to the start of a new communications link pushes all the previous links upward in the bundle, and connecting another processor to the end of a communication link connects it to the one at the bottom of the bundle and pops all the other ones down. Because of this stack behavior, a single bundle can handle a set of communications links that form the edges of a single page in a book embedding. By organizing the links in this way, a wide variety of different network topologies can be implemented, regardless of which processors have become faulty, as long as enough non-faulty processors remain to implement the network. 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. Book embedding may also be used to model the placement of wires connecting VLSI components into the layers of a circuit. 1596:, 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 1609: 1825:, 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. As Chung et al. observe, a given permutation can be sorted by this system if and only if a certain graph, derived from the permutation, has a book embedding with the vertices in a certain fixed order along the spine and with a number of pages that is at most equal to the number of stacks. 275: 1860: 1114: 1834: 293: 1900: 1207: 1983: 33: 768: 1914:, 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. 1580:. 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 1886:

or linear embedding places vertices of a graph along a line, and draws the edges of the graph as semicircles either above or below this line, sometimes also allowing edges to be drawn on segments of the line. This drawing style corresponds to a book embedding with either one page (if all semicircles

2019:

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

253:

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

1850:

at a controlled intersection. At an intersection, the incoming and outgoing lanes of traffic (including the ends of pedestrian crosswalks and bicycle lanes as well as lanes for motor vehicles) may be represented as the vertices of a graph, placed on the spine of a book embedding in their clockwise

1221:

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

623: 245:

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:

181:

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

1687:

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

1141:

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

529:

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

1137:. 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 2010:

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.

1699:. 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. 1891:

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

2023:

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

212:

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

1371:

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

1166:. 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 1837:

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

993: 1083: 1651:

although his writeup of this result omits many details. 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

2020:

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.

1706:

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

1193:

in 1986 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

1145:

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

2066:

of certain problems in RNA secondary structure comparison. 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.

1174:, 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 763:{\displaystyle {\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-2}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-3}{2}}{\biggr \rfloor },} 488:

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

1994:. 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. 1959:, 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. Two-page book embedding has also been used to find 810:. 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, 4690:

Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Rutter, Ignaz (2012), "Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph",

1879:, arc diagrams and circular layouts, can be viewed as book embeddings, and book embedding has also been applied in the construction of clustered layouts, simultaneous embeddings, and three-dimensional graph drawings. 1142:

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.

521:

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

4784: 2147:, 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. 1632:. 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. 1688:

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.

777:

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.

2219: 1871:. 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. 1683:. 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 3876: 1917:

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

554:

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

914: 1008: 534:

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.

593: 147: 1769:

of a multiprocessor system are arranged into a logical sequence corresponding to the spine of a book (although this sequence may not necessarily be placed along a line in the

5113:

Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers

3243:

Bekos, Michael A.; Kaufmann, Micheal; Klute, Fabian; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), "Four Pages Are Indeed Necessary for Planar Graphs",

189:

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

1567: 1479: 1439: 1267: 2842:

Enomoto, Hikoe; Miyauchi, Miki Shimabara; Ota, Katsuhiro (1999), "Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph",

1963:

of graphs, in which two graphs are given on the same vertex set and one must find a placement for the vertices in which both graphs are drawn planarly with straight edges.

2006:

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

246:

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.

1236:

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

1509:, 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 4913:

Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), "Computing upward topological book embeddings of upward planar digraphs",

1821:

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

4914: 1276:

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

4322: 4183: 3159: 1691:

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

2528:

The "spine" and "pages" terminology is more standard in modern graph-theoretic approaches to the subject. For the "back" and "leaves" terminology, see

2302:

Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973)

288:

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.

1948:

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

2430:

Haslinger, Christian; Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties",

1620:

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.

1573:

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.

1773:

of this system). Communication links connecting these processors are grouped into "bundles" which correspond to the pages of a book and act like

1217:

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

4278: 4122: 2642: 4355:

Angelini, Patrizio; Di Bartolomeo, Marco; Di Battista, Giuseppe (2013), "Implementing a partitioned 2-page book embedding testing algorithm",

5110:

Blin, Guillaume; Fertin, Guillaume; Rusu, Irena; Sinoquet, Christine (2007), "Extending the hardness of RNA secondary structure comparison",

1635:

If an ordering of the vertices of a graph along the spine of an embedding is fixed, then a two-page embedding (if it exists) can be found in

4503:

Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986)

3206: 2316:

Ollmann, L. Taylor (1973), "On the book thicknesses of various graphs", in Hoffman, Frederick; Levow, Roy B.; Thomas, Robert S. D. (eds.),

1733:

and applying a SAT solver to the resulting problem. They state that their system is capable of finding an optimal embedding for 400-vertex

2881:Ábrego, Bernardo M.; Aichholzer, Oswin; Fernández-Merchant, Silvia; Ramos, Pedro; Salazar, Gelasio (2012), "The 2-page crossing number of 1809:

by pushing incoming elements onto a stack and then, at appropriately chosen times, popping them from the stack onto an output stream can

4655:

Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers

4224:

Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs",

3880: 3662:

Bekos, Michael A.; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), "1-Planar graphs have constant book thickness",

1588:, the resulting graph will automatically have a one-page embedding. For this reason, the page number of a graph has also been called its 2044:

of the input (a graph formed by connecting the bases into a cycle in their sequence order and adding the given basepairs as edges) is a

4967:

Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings

2613: 2090:. As they have observed, reachability for two-page directed graphs may be solved in unambiguous logarithmic space (the analogue, for 1715:

to the larger graph. For the same reason, the problem of testing whether a graph of bounded book thickness obeys a given formula of

5003: 4735: 4356: 5263: 2342: 1675:

with a fixed spine ordering for its vertices, drawing these vertices in the same order around a circle and drawing the edges of

3791: 3300: 2036:

whose vertices are the basepairs and whose edges describe crossings between basepairs. Alternatively and more efficiently, as

1966:

Book embeddings with more than two pages have also been used to construct three-dimensional drawings of graphs. In particular,

1887:

are above the line) or two pages (if both sides of the line are used), and was originally introduced as a way of studying the

5132: 5086: 5031: 4982: 4932: 4755: 4671: 4384: 4166: 3679: 3618: 1896:. For every planar graph, it is always possible to find such an embedding in which each edge crosses the spine at most once. 92:

of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called

4330:, Technical report (2009-004 ed.), Dept. of Applied Mathematics and Physics, University of Kyoto, Japan, archived from 4151:

STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings

3715: 3123: 2777: 1974:

of each vertex within each page low, as part of a method for embedding graphs into a three-dimensional grid of low volume.

3698:

Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective",

2098:

of unambiguous polynomial-time problems). However, reachability for three-page directed graphs requires the full power of

904:

vertices per independent set, with an edge between every two vertices from different independent sets) the book thickness

4951:

Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15–19, 2004

4575:

Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989)

3724: 3388: 2482: 3158:

Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), "Two-page book embeddings of 4-planar graphs",

262:

have book thickness at most four, and the discovery in the late 1990s of close connections between book embeddings and

5005:

Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23–25, 2013, Revised Selected Papers

4916:

Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007, Proceedings

4358:

Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers

1327:

have unbounded book thickness, but subdividing their edges into six-edge paths reduces their book thickness to three.

1189:

have book thickness at most three. More generally, all planar graphs have book thickness four. It has been claimed by

5412: 4965:

Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers",

4619: 4538: 4433: 4201: 3838: 3224: 3189: 2397: 1875:

Book embedding has also been frequently applied in the visualization of network data. Two of the standard layouts in

5261:(1989), "On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines", 4269: 2598:

Shahrokhi, Farhad; Székely, László A.; Sýkora, Ondrej; Vrťo, Imrich (1996), "The book crossing number of a graph",

2432: 2379: 2110: 2003: 222: 5154: 4528: 2961:

de Klerk, Etienne; Pasechnik, Dmitrii V.; Salazar, Gelasio (2014), "Book drawings of complete bipartite graphs",

2932: 2561: 2079: 4331: 4226: 3018: 2718: 2178: 2109:

with constant page number is the key step in proving that there is no subquadratic-time simulation of two-tape

1888: 1730: 1643:

for a graph formed by augmenting the given graph with a cycle connecting the vertices in their spine ordering.

988:{\displaystyle \left\lceil {\frac {k(r-1)}{2}}\right\rceil \leq t\leq \left\lceil {\frac {kr}{2}}\right\rceil } 897: 446: 17: 5417: 5364:

Dynnikov, I. A. (2001), "A new way to represent links, one-dimensional formalism and untangling technology",

2930:

Enomoto, Hikoe; Nakamigawa, Tomoki; Ota, Katsuhiro (1997), "On the pagenumber of complete bipartite graphs",

2102:. Thus, book embeddings seem intimately connected with the distinction between these two complexity classes. 1482: 1159: 166: 3055:

Hasunuma, Toru; Shibata, Yukio (1997), "Embedding de Bruijn, Kautz and shuffle-exchange networks in books",

84:

as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the

4737:

Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers

3450: 3057: 2963: 2844: 1373: 1214: 1078:{\displaystyle t\leq (r-1)\left\lceil {\frac {k}{2}}\right\rceil +\left\lceil {\frac {k}{4}}\right\rceil .} 69: 4086:(Technical Report #298), Department of EECS, Princeton University – via Institute for Advanced Study 1729:

describe a system for finding optimal book embeddings by transforming the problem into an instance of the

1489:, which are not closed under minors, have also bounded book thickness, but some 1-planar graphs including 52:, it is not possible to embed this graph without crossings on fewer pages, so its book thickness is three. 4847:

Nicholson, T. A. J. (1968), "Permutation procedure for minimising the number of crossings in a network",

2679: 1949: 1316: 875: 360: 4431:; Ossona de Mendez, Patrice (2008), "Grad and classes with bounded expansion. II. Algorithmic aspects", 1955:

Two-page book embeddings with a fixed partition of the edges into pages can be interpreted as a form of

5294: 5197:

Pavan, A.; Tewari, Raghunath; Vinodchandran, N. V. (2012), "On the power of unambiguity in log-space",

4731: 4047: 3768: 3719: 3383: 3327: 1794: 1774: 1593: 1577: 819:

has book thickness three, not four. However, when the two sides of the graph are very unbalanced, with

564: 118: 509:. Another parameter that measures the quality of a book embedding, beyond its number of pages, is its 5002:; Simons, Joseph A. (2013), "Fixed parameter tractability of crossing minimization of almost-trees", 4008: 2229: 1937: 2677:

Stöhr, Elena (1988), "A trade-off between page number and page width of book embeddings of graphs",

2136:

by making a vertex for each zero divisor and an edge for each pair of values whose product is zero.

1539: 1528:: they have separators, subsets of vertices whose removal splits the graph into pieces with at most 1451: 1411: 1355:

colors, in such a way that edges of the same color as each other do not cross. Analogously, a graph

1239: 3598: 2827: 1868: 1720: 1525: 1336: 1167: 1118: 781: 5111: 5059:(2014), "Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth", 2600: 2256: 1592:. In the same way, one may consider an arbitrary sequence of enqueue and dequeue operations of a 208:, the different sources and destinations of foot and vehicle traffic that meet and interact at a 205: 4114: 1647:

claimed that finding three-page embeddings with a fixed spine ordering can also be performed in

1521:, a much stronger requirement than having bounded expansion, can have unbounded book thickness. 4428: 4273: 3796:, improving an earlier result showing the existence of expanders with constant pagenumber from 3594: 2822: 2760:

Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), "Embedding graphs into a three page book with

2477: 2062:

used the connection between secondary structures and book embeddings as part of a proof of the

1960: 1093: 523: 5149: 3802: 3164:, Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 137–148, 1971: 1518: 1182: 1097: 774: 5385: 5342: 5307: 5228: 5096: 4887: 4868: 4815: 4793: 4765: 4714: 4653: 4599: 4582: 4548: 4510: 4464: 4394: 4299: 4247: 4063: 4029: 3992: 3949: 3901: 3826: 3747: 3628: 3573: 3523: 3473: 3144: 3107: 3080: 3041: 2994: 2955: 2907: 2867: 2798: 2741: 2702: 2663: 2621: 2584: 2515: 2279: 2237: 2201: 1734: 1703: 1175: 1171: 182:

complexity: it is neither known to be solvable in polynomial time nor known to be NP-hard.

158: 8: 4740:, Lecture Notes in Computer Science, vol. 2265, Springer, Berlin, pp. 312–327, 4734:(2002), "Bounded degree book embeddings and three-dimensional orthogonal graph drawing", 4570: 4498: 4110: 4106: 3969: 3785: 3294: 3121:

Obrenić, Bojana (1993), "Embedding de Bruijn and shuffle-exchange graphs in five pages",

2556: 2293: 1956: 1818: 1628:. This follows from the fact that finding Hamiltonian cycles in maximal planar graphs is 1442: 1320: 250: 174: 5321:

Dynnikov, I. A. (1999), "Three-page approach to knot theory. Coding and local motions",

5063:, Lecture Notes in Computer Science, vol. 8871, Springer-Verlag, pp. 210–221, 4891: 4797: 4153:, Lecture Notes in Computer Science, vol. 577, Berlin: Springer, pp. 389–400, 3086:

Tanaka, Yuuki; Shibata, Yukio (2010), "On the pagenumber of the cube-connected cycles",

5389: 5346: 5232: 5206: 5179: 5064: 5037: 5009: 4884:

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

4625: 4468: 4442: 4398: 4362: 4185:

Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS '88)

3953: 3905: 3772: 3700:

Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015)

3415: 3397: 3359: 3341: 3281: 3252: 3165: 3111: 2998: 2972: 2911: 2454: 2403: 2375: 2337: 2144: 2140: 1712: 1660: 1617: 1190: 1186: 1138: 255: 5258: 4824: 3923: 3464: 3071: 2858: 2244: 185:

One of the original motivations for studying book embeddings involved applications in

5393: 5350: 5277: 5171: 5128: 5082: 5027: 4978: 4928: 4829: 4751: 4667: 4615: 4552: 4534: 4380: 4197: 4188:, Lecture Notes in Computer Science, vol. 294, Springer-Verlag, pp. 61–72, 4162: 3909: 3675: 3614: 3363: 3220: 3185: 2732: 2693: 2575: 2459: 2393: 2356: 2053: 1941: 1810: 1716: 1640: 1514: 1324: 1170:

provides an example of a planar graph that does not have book thickness two: it is a

1163: 1134: 309: 154: 5041: 4402: 3957: 3115: 3002: 1339:, the number of planar graphs needed to cover the edges of the given graph. A graph 5373: 5330: 5272: 5254: 5236: 5216: 5183: 5163: 5120: 5074: 5019: 4970: 4920: 4895: 4856: 4819: 4801: 4741: 4700: 4659: 4607: 4472: 4452: 4372: 4287: 4265: 4235: 4189: 4154: 4131: 4017: 3978: 3937: 3919: 3889: 3814: 3733: 3667: 3606: 3561: 3511: 3459: 3419: 3407: 3351: 3212: 3175: 3132: 3095: 3066: 3027: 2982: 2941: 2915: 2895: 2853: 2786: 2727: 2688: 2651: 2609: 2570: 2501: 2491: 2449: 2441: 2407: 2385: 2351: 2265: 2187: 2139:

In a multi-paper sequence, Dynnikov has studied the topological book embeddings of

2125: 2025: 1708: 1664: 1367:, with its vertices on the boundary of the half plane, with its edges colored with 230: 4899: 4629: 4043: 4006:

Heath, Lenwood S.; Rosenberg, Arnold L. (1992), "Laying out graphs using queues",

3764: 3379: 3315: 3180: 2821:, Technical Report 1999-4, Department of Mathematics, Louisiana State University, 1936:

is the number of vertices. Minimizing the one-page or two-page crossing number is

1904: 526:

defined on the spine by pairs of endpoints of the edges all intersect each other.

5381: 5338: 5303: 5224: 5124: 5092: 5078: 5023: 4924: 4919:, Lecture Notes in Computer Science, vol. 4835, Springer, pp. 172–183, 4864: 4811: 4779: 4761: 4710: 4663: 4658:, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, 4578: 4544: 4506: 4460: 4390: 4295: 4243: 4059: 4025: 3988: 3945: 3897: 3822: 3743: 3671: 3666:, Lecture Notes in Computer Science, vol. 9294, Springer, pp. 130–141, 3624: 3569: 3519: 3469: 3140: 3103: 3076: 3037: 2990: 2951: 2903: 2863: 2794: 2737: 2698: 2659: 2617: 2580: 2511: 2275: 2233: 2197: 2099: 2095: 2029: 1911: 1770: 1759: 1648: 1089: 469: 317: 313: 198: 105: 81: 5292:

McKenzie, Thomas; Overbay, Shannon (2010), "Book embeddings and zero divisors",

4969:, Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, 4611: 4376: 1608: 5148:

Clote, Peter; Dobrev, Stefan; Dotu, Ivan; Kranakis, Evangelos; Krizanc, Danny;

5056: 4999: 4785:

Proceedings of the National Academy of Sciences of the United States of America

4361:, Lecture Notes in Computer Science, vol. 7704, Springer, pp. 79–89, 3818: 3319: 3277: 3032: 2928:

For additional results on the book thickness of complete bipartite graphs, see

2106: 2091: 2087: 1847: 1762: 1653: 1486: 1377: 1223: 543: 518: 368: 263: 214: 150: 37: 5377: 5220: 5167: 4705: 4456: 4158: 4115:"Embedding graphs in books: A layout problem with applications to VLSI design" 3983: 3893: 3610: 3411: 3355: 3099: 3016:

Sperfeld, Konrad (2013), "On the page number of complete odd-partite graphs",

2986: 2790: 2318:

Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing

1833: 1576:

The edges within a single page of a book embedding behave in some ways like a

857: 5406: 4974: 4746: 4652:(2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), 4649: 4556: 4318: 4261: 4077: 3964: 3928: 3832: 3798: 3332: 3216: 2296:(1974), "Some recent results in topological graph theory", in Bari, Ruth A.; 1876: 1502: 1348: 1218: 402: 297: 279: 259: 209: 190: 3722:(2006), "Bounded-degree graphs have arbitrarily large geometric thickness", 3161:

Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science

2899: 2192: 5175: 5152:(2012), "On the page number of RNA secondary structures with pseudoknots", 4860: 4833: 4524: 4083:

The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs

3565: 3515: 3208:

Proceedings of the 25th Annual Symposium on Foundations of Computer Science

2946: 2892:

Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12)

2463: 2445: 2297: 2129: 2083: 2048:. This characterization allows bi-secondary structures to be recognized in 2045: 2033: 1798: 1656: 1613: 1597: 1506: 1147: 162: 65: 57: 49: 4806: 3605:, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, 2270: 165:; more generally, every planar graph has book thickness at most four. All 4882:

Miyauchi, Miki (2006), "Topological book embedding of bipartite graphs",

4604:

Proceedings of IEEE Symposium on Information Visualization (INFOVIS 2002)

2640:

Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books",

2506: 2049: 1918: 1883: 1864: 1814: 1806: 1790: 1692: 1636: 1629: 596: 274: 234: 194: 4081: 3286: 2614:

10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5

2389: 1859: 1210:

The book thickness of the diamond graph increases after edge subdivision

5334: 5119:, Lecture Notes in Computer Science, vol. 4614, pp. 140–151, 5008:, Lecture Notes in Computer Science, vol. 8242, pp. 340–351, 4949: 4948:

He, Hongmei; Sykora, Ondrej (2004), "New circular drawing algorithms",

4193: 3941: 2880: 2819:

Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books

2496: 2381:

Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86)

2133: 2016: 1991: 1987: 1944:

of the given graph, or by a combination of the crossing number and the

1364: 1273: 1113: 1100:(when these graphs are large enough to be nonplanar) is exactly three. 344: 332: 226: 77: 1524:

Because graphs of book thickness two are planar graphs, they obey the

5250: 4447: 4239: 4102: 3915: 3646:, Ph.D. thesis, Department of Mathematics, Louisiana State University 3402: 3323: 2378:(1986), "Four pages are necessary and sufficient for planar graphs", 1945: 1696: 1384: 1195: 505:

is the minimum number of pages required for a book embedding of

348: 170: 88:, and the edges are required to stay within a single half-plane. The 4291: 4135: 4021: 3136: 2655: 1846:

described, a book embedding may be used to describe the phases of a

1380:) that have unbounded book thickness, despite having thickness two. 292: 4149:

Unger, Walter (1992), "The complexity of colouring circle graphs",

3777: 3661: 3346: 3257: 2015:

have proposed a so-called "bi-secondary structure" for certain RNA

2007: 1899: 514: 5211: 5069: 5014: 4782:(1964), "The minimum number of intersections in complete graphs", 4689: 4367: 3738: 3314: 3170: 2977: 4223: 2716:

Stöhr, Elena (1991), "The pagewidth of trivalent planar graphs",

2063: 1750:

One of the main motivations for studying book embedding cited by

1625: 343:

of the book, each having the spine as its boundary. Books with a

300:

has pagewidth 3, because the yellow ray crosses three edges.

178: 4912: 4354: 3433:

Ganley, Joseph L.; Heath, Lenwood S. (2001), "The pagenumber of

1206: 4964: 4276:(1980), "The complexity of coloring circular arcs and chords", 4260: 3205:

Heath, Lenny (1984), "Embedding planar graphs In seven pages",

1668: 3967:(2010), "Monotone expanders: constructions and applications", 3386:(2007), "Graph treewidth and geometric thickness parameters", 3330:(August 2021), "Stack-number is not bounded by queue-number", 3280:(2001), "Separating geometric thickness from book thickness", 2304:, Lecture Notes in Mathematics, vol. 406, pp. 76–108 1679:

as line segments produces a collection of chords representing

104:. Book embeddings have also been used to define several other 4182:

Unger, Walter (1988), "On the k-colouring of circle-graphs",

2002:

molecules fold to form their structure, the standard form of

1982: 426: 193:, where two of the standard visualization styles for graphs, 4533:, Boston: Addison-Wesley, Section 2.2.1, Exercises 4 and 5, 1813:

the data if and only if its initial order is described by a

1315:. Their conjecture turned out to be false: graphs formed by 1755: 1584:

from the stack, to the previous push operation that pushed

221:, single-page book embeddings represent classical forms of 186: 32: 4602:(2002), "Arc diagrams: visualizing structure in strings", 4577:, Congressus Numerantium, vol. 71, pp. 127–132, 4505:, Congressus Numerantium, vol. 54, pp. 217–224, 2597: 3242: 3157: 2040:

show, a bi-secondary structure exists if and only if the

1999: 1921:, but may be approximated with an approximation ratio of 1766: 1765:. In the DIOGENES system developed by these authors, the 218: 5196: 4485: 4427: 4415: 3763: 3649: 3593: 2960: 2075: 1510: 542:

As shown in the first figure, the book thickness of the

517:

as the maximum number of edges that can be crossed by a

5147: 4997: 4501:(1986), "Book embeddings and wafer-scale integration", 4052:

Discrete Mathematics & Theoretical Computer Science

351:

into three-dimensional space, for instance by choosing

331:

of the book, together with a collection of one or more

5109: 4849:

Proceedings of the Institution of Electrical Engineers

4101: 3926:(1989), "On 3-pushdown graphs with large separators", 2059: 1970:

used a construction for book embeddings that keep the

1822: 1786: 1751: 1269:. Despite the existence of examples such as this one, 149:, and this formula gives the exact book thickness for 4324:

Two-page book embedding and clustered graph planarity

3841: 2320:, Congressus Numerantium, vol. VIII, p. 459 1542: 1454: 1414: 1330: 1242: 1011: 917: 626: 567: 157:. The graphs with book thickness at most two are the 121: 5249: 3914: 2929: 2816: 1270: 3697: 1726: 1485:has bounded book thickness. On the other hand, the 606:The two-page crossing number of the complete graph 3870: 3831: 2841: 2070: 1561: 1473: 1433: 1261: 1077: 987: 762: 587: 141: 108:including the pagewidth and book crossing number. 5054: 3713: 2340:(1989), "Embedding planar graphs in four pages", 1745: 1198:4 that require four pages in any book embedding. 1185:is at most four have book thickness at most two. 752: 727: 720: 695: 688: 663: 656: 639: 229:. Other applications of book embeddings include 5404: 2429: 2037: 2012: 1150:. More precisely, the book thickness of a graph 5291: 3871:{\displaystyle \mathrm {SL} _{2}(\mathbb {R} )} 3054: 2759: 2121: 2113:by one-tape non-deterministic Turing machines. 1347:if it can be drawn in the plane, and its edges 1108: 4279:SIAM Journal on Algebraic and Discrete Methods 4123:SIAM Journal on Algebraic and Discrete Methods 4005: 2817:Blankenship, Robin; Oporowski, Bogdan (1999), 2643:SIAM Journal on Algebraic and Discrete Methods 2554: 1201: 599:on the maximum possible book thickness of any 5061:Proc. 22nd Int. Symp. Graph Drawing (GD 2014) 4573:(1990), "The book thickness of a graph. II", 4317: 3962: 3085: 2116: 1292:by a two-edge path, if the book thickness of 153:. The graphs with book thickness one are the 4042: 3603:Sparsity: Graphs, Structures, and Algorithms 3378: 1513:, the graphs of bounded book thickness have 582: 568: 217:problems involving the folding structure of 201:, can be constructed using book embeddings. 169:, and in particular the graphs with bounded 136: 122: 4647: 3641: 3432: 2161: 2159: 1702:As a consequence of bounded expansion, the 1603: 4598: 4142: 3238: 3236: 2374: 2336: 2225:-books: intrinsic and extrinsic properties 1505:of a graph of bounded book thickness is a 1121:, a planar graph with book thickness three 1002:is odd the upper bound can be improved to 177:, also have bounded book thickness. It is 5276: 5210: 5068: 5013: 4846: 4823: 4805: 4745: 4726: 4724: 4704: 4497: 4446: 4366: 4076: 3982: 3861: 3835:; Yehudayoff, Amir (2013), "Expansion in 3776: 3737: 3463: 3401: 3345: 3285: 3256: 3179: 3169: 3070: 3031: 2976: 2945: 2857: 2826: 2731: 2692: 2574: 2559:(1979), "The book thickness of a graph", 2529: 2505: 2495: 2453: 2355: 2269: 2191: 2165: 1711:of the larger graph, or whether it has a 1624:Finding the book thickness of a graph is 225:, and two-page book embeddings represent 5363: 5320: 4947: 4881: 4685: 4683: 3797: 3759: 3757: 3693: 3691: 3276: 3015: 2242: 2217: 2156: 2124:study applications of book thickness in 2076:Pavan, Tewari & Vinodchandran (2012) 1981: 1898: 1858: 1832: 1805:) showed that a system that processes a 1607: 1205: 1112: 773:matching a still-unproven conjecture of 316:of half-planes. It consists of a single 291: 273: 31: 5264:Journal of Computer and System Sciences 4313: 4311: 4309: 4219: 4217: 4215: 4213: 4050:(2004), "On linear layouts of graphs", 3589: 3587: 3585: 3583: 3374: 3372: 3233: 3120: 2812: 2810: 2808: 2755: 2753: 2751: 2370: 2368: 2366: 2343:Journal of Computer and System Sciences 2332: 2330: 2328: 2315: 14: 5405: 4721: 4594: 4592: 4569: 4563: 4530:The Art Of Computer Programming Vol. 1 4486:Nešetřil & Ossona de Mendez (2012) 4416:Nešetřil & Ossona de Mendez (2012) 4097: 4095: 4093: 3650:Nešetřil & Ossona de Mendez (2012) 3536: 3486: 3272: 3270: 3268: 2635: 2633: 2631: 2425: 2423: 2421: 2419: 2417: 2292: 1843: 1823:Chung, Leighton & Rosenberg (1987) 1787:Chung, Leighton & Rosenberg (1987) 1752:Chung, Leighton & Rosenberg (1987) 1517:. However, even the graphs of bounded 1511:Nešetřil & Ossona de Mendez (2012) 5357: 5314: 4778: 4680: 4643: 4641: 4639: 4523: 4181: 4148: 3803:"Expanders and dimensional expansion" 3754: 3688: 3487:Malitz, Seth M. (1994), "Graphs with 3204: 3198: 3151: 2715: 2676: 2639: 2550: 2548: 2546: 2544: 2542: 2540: 2538: 2476: 2213: 2211: 2166:Persinger, C. A. (1966), "Subsets of 1802: 1644: 5285: 4730: 4306: 4210: 3580: 3369: 3124:SIAM Journal on Discrete Mathematics 2805: 2778:SIAM Journal on Discrete Mathematics 2775:crossings of edges over the spine", 2748: 2591: 2470: 2363: 2325: 2221:On the embeddability of compacta in 1967: 1125:The book thickness of a given graph 417:is drawn as a point on the spine of 115:vertices has book thickness at most 27:Graph layout on multiple half-planes 4589: 4175: 4090: 3725:Electronic Journal of Combinatorics 3389:Discrete and Computational Geometry 3265: 2894:, ACM, New York, pp. 397–403, 2628: 2483:Discrete and Computational Geometry 2414: 1727:Bekos, Kaufmann & Zielke (2015) 1498:have book thickness at least four. 480:. That is, it is a book drawing of 36:A three-page book embedding of the 24: 4636: 3847: 3844: 3790:: CS1 maint: overridden setting ( 3299:: CS1 maint: overridden setting ( 2535: 2208: 2100:nondeterministic logarithmic space 1828: 1331:Relation to other graph invariants 1288:formed by replacing every edge in 1271:Blankenship & Oporowski (1999) 537: 429:that lies within a single page of 25: 5429: 4434:European Journal of Combinatorics 3881:Geometric and Functional Analysis 3245:Journal of Computational Geomerty 2111:non-deterministic Turing machines 2078:used book embedding to study the 2028:, or as a problem of testing the 1569:vertices in the separator. Here, 588:{\displaystyle \lceil n/2\rceil } 513:. This is defined analogously to 375:-plane is an integer multiple of 363:and choosing the pages to be the 142:{\displaystyle \lceil n/2\rceil } 3771:(2015), "3-Monotone Expanders", 2433:Bulletin of Mathematical Biology 2128:, using graphs defined from the 2004:nucleic acid secondary structure 1854: 1780: 254:embeddings include the proof by 223:nucleic acid secondary structure 5243: 5190: 5155:Journal of Mathematical Biology 5141: 5103: 5048: 4991: 4958: 4941: 4906: 4875: 4840: 4772: 4517: 4491: 4479: 4421: 4409: 4348: 4254: 4070: 4036: 3999: 3707: 3655: 3635: 3537:Malitz, Seth M. (1994), "Genus 3530: 3480: 3426: 3308: 3088:Mathematics in Computer Science 3048: 3009: 2933:Journal of Combinatorial Theory 2922: 2874: 2835: 2709: 2670: 2562:Journal of Combinatorial Theory 2480:(1997), "Sphere packings. II", 2080:computational complexity theory 2071:Computational complexity theory 1758:design, to the organization of 1740: 1088:The book thickness of binary 468:is a book drawing that forms a 4693:Journal of Discrete Algorithms 4418:, Corollary 18.1, p. 401. 4227:IEEE Transactions on Computers 3865: 3857: 2522: 2309: 2286: 2179:Pacific Journal of Mathematics 2038:Haslinger & Stadler (1999) 2013:Haslinger & Stadler (1999) 1977: 1910:In another drawing style, the 1746:Fault-tolerant multiprocessing 1731:Boolean satisfiability problem 1562:{\displaystyle O({\sqrt {n}})} 1556: 1546: 1474:{\displaystyle O({\sqrt {g}})} 1468: 1458: 1434:{\displaystyle O({\sqrt {m}})} 1428: 1418: 1262:{\displaystyle O({\sqrt {n}})} 1256: 1246: 1154:is at most two if and only if 1129:is at most one if and only if 1030: 1018: 940: 928: 269: 13: 1: 5366:Acta Applicandae Mathematicae 4321:; Nagamochi, Hiroshi (2009), 3465:10.1016/S0166-218X(00)00178-5 3181:10.4230/LIPIcs.STACS.2014.137 3072:10.1016/S0166-218X(97)00009-7 2859:10.1016/S0166-218X(99)00044-X 2218:Atneosen, Gail Adele (1968), 2150: 2122:McKenzie & Overbay (2010) 1785:Another application cited by 1737:in approximately 20 minutes. 1397:and this bound is tight for 1335:Book thickness is related to 1162:of a planar graph that has a 1103: 296:This 1-page embedding of the 5278:10.1016/0022-0000(89)90036-6 5125:10.1007/978-3-540-74450-4_13 5079:10.1007/978-3-662-45803-7_18 5024:10.1007/978-3-319-03841-4_30 4925:10.1007/978-3-540-77120-3_17 4664:10.1007/978-3-540-30559-0_28 4488:, Theorem 18.7, p. 405. 3767:; Sidiropoulos, Anastasios; 3672:10.1007/978-3-662-48350-3_12 3451:Discrete Applied Mathematics 3058:Discrete Applied Mathematics 2964:Discrete Applied Mathematics 2845:Discrete Applied Mathematics 2733:10.1016/0012-365X(91)90398-L 2694:10.1016/0890-5401(88)90036-3 2576:10.1016/0095-8956(79)90021-2 2357:10.1016/0022-0000(89)90032-9 2092:logarithmic space complexity 1390:have book thickness at most 1109:Planarity and outerplanarity 595:. This result also gives an 7: 4900:10.1093/ietfec/e89-a.5.1223 4612:10.1109/INFVIS.2002.1173155 4377:10.1007/978-3-642-36763-2_8 3807:Comptes Rendus Mathématique 2680:Information and Computation 1797:. An influential result of 1754:involves an application in 1300:then the book thickness of 1280:such that, for every graph 1202:Behavior under subdivisions 876:complete multipartite graph 361:Cartesian coordinate system 167:minor-closed graph families 10: 5434: 5323:Rossiĭskaya Akademiya Nauk 3819:10.1016/j.crma.2009.02.009 3033:10.1016/j.disc.2013.04.028 2243:Atneosen, Gail H. (1972), 2117:Other areas of mathematics 1940:when parameterized by the 1894:topological book embedding 1408:edges have book thickness 780:The book thickness of the 532:topological book embedding 413:such that every vertex of 240: 5221:10.1007/s00037-012-0047-3 5168:10.1007/s00285-011-0493-6 4706:10.1016/j.jda.2011.12.015 4457:10.1016/j.ejc.2006.07.014 4159:10.1007/3-540-55210-3_199 4009:SIAM Journal on Computing 3984:10.4086/toc.2010.v006a012 3894:10.1007/s00039-012-0200-9 3878:and monotone expanders", 3644:Book Embeddings of Graphs 3611:10.1007/978-3-642-27875-4 3599:Ossona de Mendez, Patrice 3412:10.1007/s00454-007-1318-7 3356:10.1007/s00493-021-4585-7 3322:; Hickingbotham, Robert; 3100:10.1007/s11786-009-0012-y 2987:10.1016/j.dam.2013.11.001 2791:10.1137/S0895480195280319 2230:Michigan State University 1938:fixed-parameter tractable 1721:fixed-parameter tractable 1695:by an algorithm based on 1536:vertices each, with only 1483:minor-closed graph family 5413:Topological graph theory 5199:Computational Complexity 4975:10.1007/3-540-59071-4_53 4886:, E89-A (5): 1223–1226, 4747:10.1007/3-540-45848-4_25 4107:Leighton, Frank Thompson 3642:Blankenship, R. (2003), 3217:10.1109/SFCS.1984.715903 1604:Computational complexity 1526:planar separator theorem 1481:. More generally, every 1363:if it can be drawn in a 1181:All planar graphs whose 834:, the book thickness of 782:complete bipartite graph 308:is a particular kind of 5378:10.1023/A:1014299416618 5055:Bannister, Michael J.; 4998:Bannister, Michael J.; 3541:graphs have pagenumber 2900:10.1145/2261250.2261310 2601:Journal of Graph Theory 2257:Fundamenta Mathematicae 2193:10.2140/pjm.1966.18.169 1961:simultaneous embeddings 1903:Circular layout of the 1094:shuffle-exchange graphs 258:in the late 1980s that 206:transportation planning 64:is a generalization of 4861:10.1049/piee.1968.0004 3872: 3566:10.1006/jagm.1994.1028 3516:10.1006/jagm.1994.1027 3491:edges have pagenumber 2947:10.1006/jctb.1997.1773 2890:(extended abstract)", 2446:10.1006/bulm.1998.0085 1995: 1907: 1872: 1839: 1621: 1563: 1475: 1435: 1263: 1211: 1122: 1079: 989: 908:is sandwiched between 764: 589: 301: 289: 143: 53: 48:. Because it is not a 4807:10.1073/pnas.52.3.688 3873: 3664:Algorithms – ESA 2015 3554:Journal of Algorithms 3504:Journal of Algorithms 2271:10.4064/fm-74-1-43-45 1985: 1902: 1862: 1836: 1735:maximal planar graphs 1611: 1564: 1476: 1436: 1264: 1209: 1176:subhamiltonian graphs 1116: 1098:cube-connected cycles 1080: 990: 765: 590: 295: 277: 249:In the early 1970s, 159:subhamiltonian graphs 144: 35: 5418:NP-complete problems 4606:, pp. 110–116, 4499:Rosenberg, Arnold L. 4274:Papadimitriou, C. H. 4111:Rosenberg, Arnold L. 3839: 3019:Discrete Mathematics 2719:Discrete Mathematics 2555:Bernhart, Frank R.; 2384:, pp. 104–108, 1998:In the study of how 1986:A fragment of human 1869:Goldner–Harary graph 1704:subgraph isomorphism 1639:, as an instance of 1594:queue data structure 1578:stack data structure 1540: 1452: 1448:have book thickness 1412: 1240: 1172:maximal planar graph 1168:Goldner–Harary graph 1119:Goldner–Harary graph 1009: 915: 624: 565: 561:vertices is exactly 453:-page book drawing. 439:book crossing number 421:, and every edge of 371:with respect to the 119: 102:fixed outerthickness 80:all having the same 4892:2006IEITF..89.1223M 4798:1964PNAS...52..688S 3970:Theory of Computing 2390:10.1145/12130.12141 2376:Yannakakis, Mihalis 2338:Yannakakis, Mihalis 1957:clustered planarity 1819:permutation pattern 1661:intersection graphs 1359:has book thickness 447:number of crossings 161:, which are always 72:to embeddings in a 5335:10.1007/BF02467109 5162:(6–7): 1337–1357, 4429:Nešetřil, Jaroslav 4194:10.1007/BFb0035832 3942:10.1007/BF02122679 3868: 3702:, pp. 113–125 3595:Nešetřil, Jaroslav 3211:, pp. 74–83, 2497:10.1007/PL00009312 2060:Blin et al. (2007) 2052:as an instance of 1996: 1950:local optimization 1908: 1873: 1840: 1713:graph homomorphism 1622: 1618:intersection graph 1559: 1471: 1431: 1325:triangular tilings 1317:Cartesian products 1284:and for the graph 1259: 1212: 1191:Mihalis Yannakakis 1139:articulation point 1123: 1075: 985: 760: 585: 393:of a finite graph 367:half-planes whose 302: 290: 256:Mihalis Yannakakis 155:outerplanar graphs 139: 76:, a collection of 54: 5134:978-3-540-74449-8 5088:978-3-319-12567-1 5033:978-3-319-03840-7 4984:978-3-540-59071-2 4934:978-3-540-77118-0 4757:978-3-540-43309-5 4673:978-3-540-24132-4 4386:978-3-642-36762-5 4168:978-3-540-55210-9 4080:(February 1982), 3681:978-3-662-48349-7 3620:978-3-642-27874-7 3026:(17): 1689–1696, 2249:-leaved continua" 2245:"One-dimensional 2105:The existence of 2054:planarity testing 1942:cyclomatic number 1789:concerns sorting 1717:first order logic 1641:planarity testing 1554: 1515:bounded expansion 1466: 1426: 1254: 1164:Hamiltonian cycle 1135:outerplanar graph 1066: 1045: 979: 947: 748: 716: 684: 652: 635: 310:topological space 111:Every graph with 16:(Redirected from 5425: 5398: 5396: 5361: 5355: 5353: 5329:(4): 25–37, 96, 5318: 5312: 5310: 5295:Ars Combinatoria 5289: 5283: 5281: 5280: 5259:Szemerédi, Endre 5247: 5241: 5239: 5214: 5194: 5188: 5186: 5145: 5139: 5137: 5118: 5107: 5101: 5099: 5072: 5052: 5046: 5044: 5017: 4995: 4989: 4987: 4962: 4956: 4954: 4945: 4939: 4937: 4910: 4904: 4902: 4879: 4873: 4871: 4844: 4838: 4836: 4827: 4809: 4780:Saaty, Thomas L. 4776: 4770: 4768: 4749: 4728: 4719: 4717: 4708: 4687: 4678: 4676: 4645: 4634: 4632: 4596: 4587: 4585: 4567: 4561: 4559: 4525:Knuth, Donald E. 4521: 4515: 4513: 4495: 4489: 4483: 4477: 4475: 4450: 4425: 4419: 4413: 4407: 4405: 4370: 4352: 4346: 4344: 4343: 4342: 4336: 4329: 4315: 4304: 4302: 4258: 4252: 4250: 4240:10.1109/12.46286 4221: 4208: 4206: 4179: 4173: 4171: 4146: 4140: 4138: 4119: 4103:Chung, Fan R. K. 4099: 4088: 4087: 4074: 4068: 4066: 4040: 4034: 4032: 4003: 3997: 3995: 3986: 3960: 3924:Szemerédi, Endre 3912: 3877: 3875: 3874: 3869: 3864: 3856: 3855: 3850: 3829: 3813:(7–8): 357–362, 3795: 3789: 3781: 3780: 3761: 3752: 3750: 3741: 3711: 3705: 3703: 3695: 3686: 3684: 3659: 3653: 3647: 3639: 3633: 3631: 3591: 3578: 3576: 3551: 3540: 3534: 3528: 3526: 3501: 3490: 3484: 3478: 3476: 3467: 3447: 3436: 3430: 3424: 3422: 3405: 3376: 3367: 3366: 3349: 3312: 3306: 3304: 3298: 3290: 3289: 3274: 3263: 3261: 3260: 3240: 3231: 3229: 3202: 3196: 3194: 3183: 3173: 3155: 3149: 3147: 3118: 3083: 3074: 3065:(1–3): 103–116, 3052: 3046: 3044: 3035: 3013: 3007: 3005: 2980: 2958: 2949: 2926: 2920: 2918: 2889: 2878: 2872: 2870: 2861: 2852:(2–3): 149–155, 2839: 2833: 2831: 2830: 2814: 2803: 2801: 2774: 2757: 2746: 2744: 2735: 2713: 2707: 2705: 2696: 2674: 2668: 2666: 2637: 2626: 2624: 2595: 2589: 2587: 2578: 2552: 2533: 2530:Persinger (1966) 2526: 2520: 2518: 2509: 2499: 2474: 2468: 2466: 2457: 2427: 2412: 2410: 2372: 2361: 2360: 2359: 2334: 2323: 2321: 2313: 2307: 2305: 2290: 2284: 2282: 2273: 2253: 2240: 2228:, Ph.D. thesis, 2224: 2215: 2206: 2204: 2195: 2175: 2169: 2163: 2126:abstract algebra 2026:2-satisfiability 1935: 1931: 1889:crossing numbers 1817:that avoids the 1799:Donald Knuth 1709:induced subgraph 1686: 1682: 1678: 1674: 1671:. Given a graph 1587: 1583: 1572: 1568: 1566: 1565: 1560: 1555: 1550: 1535: 1497: 1480: 1478: 1477: 1472: 1467: 1462: 1447: 1441:, and graphs of 1440: 1438: 1437: 1432: 1427: 1422: 1407: 1403: 1396: 1389: 1370: 1362: 1358: 1354: 1346: 1342: 1314: 1303: 1299: 1295: 1291: 1287: 1283: 1279: 1268: 1266: 1265: 1260: 1255: 1250: 1235: 1157: 1153: 1132: 1128: 1090:de Bruijn graphs 1084: 1082: 1081: 1076: 1071: 1067: 1059: 1050: 1046: 1038: 1001: 994: 992: 991: 986: 984: 980: 975: 967: 952: 948: 943: 923: 907: 903: 898:independent sets 896: 892: 873: 852: 848: 833: 818: 809: 797: 769: 767: 766: 761: 756: 755: 749: 744: 733: 731: 730: 724: 723: 717: 712: 701: 699: 698: 692: 691: 685: 680: 669: 667: 666: 660: 659: 653: 645: 643: 642: 636: 628: 616: 602: 594: 592: 591: 586: 578: 560: 553: 508: 504: 487: 483: 479: 475: 467: 463: 452: 444: 436: 432: 424: 420: 416: 412: 408: 400: 396: 385: 380: 374: 366: 358: 354: 347:of pages can be 322: 312:, also called a 231:abstract algebra 199:circular layouts 148: 146: 145: 140: 132: 114: 106:graph invariants 66:planar embedding 47: 21: 5433: 5432: 5428: 5427: 5426: 5424: 5423: 5422: 5403: 5402: 5401: 5362: 5358: 5319: 5315: 5290: 5286: 5248: 5244: 5195: 5191: 5146: 5142: 5135: 5116: 5108: 5104: 5089: 5057:Eppstein, David 5053: 5049: 5034: 5000:Eppstein, David 4996: 4992: 4985: 4963: 4959: 4946: 4942: 4935: 4911: 4907: 4880: 4876: 4845: 4841: 4777: 4773: 4758: 4729: 4722: 4688: 4681: 4674: 4648:Baur, Michael; 4646: 4637: 4622: 4597: 4590: 4571:Kainen, Paul C. 4568: 4564: 4541: 4522: 4518: 4496: 4492: 4484: 4480: 4426: 4422: 4414: 4410: 4387: 4353: 4349: 4340: 4338: 4334: 4327: 4316: 4307: 4292:10.1137/0601025 4259: 4255: 4222: 4211: 4204: 4180: 4176: 4169: 4147: 4143: 4136:10.1137/0608002 4117: 4100: 4091: 4075: 4071: 4041: 4037: 4022:10.1137/0221055 4004: 4000: 3860: 3851: 3843: 3842: 3840: 3837: 3836: 3783: 3782: 3762: 3755: 3712: 3708: 3696: 3689: 3682: 3660: 3656: 3640: 3636: 3621: 3592: 3581: 3542: 3538: 3535: 3531: 3492: 3488: 3485: 3481: 3438: 3434: 3431: 3427: 3377: 3370: 3320:Eppstein, David 3313: 3309: 3292: 3291: 3287:math.CO/0109195 3278:Eppstein, David 3275: 3266: 3251:(11): 332–353, 3241: 3234: 3227: 3203: 3199: 3192: 3156: 3152: 3137:10.1137/0406049 3053: 3049: 3014: 3010: 2927: 2923: 2887: 2882: 2879: 2875: 2840: 2836: 2815: 2806: 2761: 2758: 2749: 2714: 2710: 2675: 2671: 2656:10.1137/0608018 2638: 2629: 2596: 2592: 2557:Kainen, Paul C. 2553: 2536: 2527: 2523: 2475: 2471: 2428: 2415: 2400: 2373: 2364: 2335: 2326: 2314: 2310: 2294:Kainen, Paul C. 2291: 2287: 2251: 2222: 2216: 2209: 2171: 2167: 2164: 2157: 2153: 2119: 2107:expander graphs 2094:, of the class 2088:directed graphs 2073: 1980: 1933: 1922: 1912:circular layout 1857: 1831: 1829:Traffic control 1783: 1771:physical layout 1763:multiprocessors 1748: 1743: 1684: 1680: 1676: 1672: 1649:polynomial time 1606: 1585: 1581: 1570: 1549: 1541: 1538: 1537: 1529: 1496: 1490: 1487:1-planar graphs 1461: 1453: 1450: 1449: 1445: 1421: 1413: 1410: 1409: 1405: 1404:. Graphs with 1398: 1391: 1387: 1378:complete graphs 1368: 1360: 1356: 1352: 1344: 1340: 1333: 1305: 1301: 1297: 1293: 1289: 1285: 1281: 1277: 1249: 1241: 1238: 1237: 1234: 1226: 1204: 1155: 1151: 1130: 1126: 1111: 1106: 1058: 1054: 1037: 1033: 1010: 1007: 1006: 999: 968: 966: 962: 924: 922: 918: 916: 913: 912: 905: 901: 894: 891: 878: 860: 850: 847: 835: 820: 817: 811: 799: 796: 784: 751: 750: 734: 732: 726: 725: 719: 718: 702: 700: 694: 693: 687: 686: 670: 668: 662: 661: 655: 654: 644: 638: 637: 627: 625: 622: 621: 615: 607: 603:-vertex graph. 600: 574: 566: 563: 562: 555: 552: 546: 540: 538:Specific graphs 506: 502: 485: 481: 477: 473: 470:graph embedding 465: 461: 450: 445:is the minimum 442: 434: 430: 422: 418: 414: 410: 406: 398: 394: 378: 376: 372: 364: 356: 352: 320: 287: 272: 243: 151:complete graphs 128: 120: 117: 116: 112: 46: 40: 28: 23: 22: 15: 12: 11: 5: 5431: 5421: 5420: 5415: 5400: 5399: 5372:(3): 243–283, 5356: 5313: 5284: 5271:(1): 134–149, 5242: 5205:(4): 643–670, 5189: 5150:Urrutia, Jorge 5140: 5133: 5102: 5087: 5047: 5032: 4990: 4983: 4957: 4940: 4933: 4905: 4874: 4839: 4792:(3): 688–690, 4771: 4756: 4732:Wood, David R. 4720: 4679: 4672: 4650:Brandes, Ulrik 4635: 4620: 4600:Wattenberg, M. 4588: 4562: 4539: 4516: 4490: 4478: 4441:(3): 777–791, 4420: 4408: 4385: 4347: 4319:Hong, Seok-Hee 4305: 4286:(2): 216–227, 4266:Johnson, D. S. 4253: 4234:(1): 124–127, 4209: 4202: 4174: 4167: 4141: 4089: 4078:Wigderson, Avi 4069: 4058:(2): 339–357, 4048:Wood, David R. 4044:Dujmović, Vida 4035: 4016:(5): 927–958, 3998: 3965:Wigderson, Avi 3867: 3863: 3859: 3854: 3849: 3846: 3833:Bourgain, Jean 3799:Bourgain, Jean 3769:Wood, David R. 3765:Dujmović, Vida 3753: 3720:Wood, David R. 3716:Matoušek, Jiří 3714:Barát, János; 3706: 3687: 3680: 3654: 3648:. As cited by 3634: 3619: 3579: 3529: 3479: 3458:(3): 215–221, 3425: 3396:(4): 641–670, 3384:Wood, David R. 3380:Dujmović, Vida 3368: 3340:(2): 151–164, 3328:Wood, David R. 3316:Dujmović, Vida 3307: 3264: 3232: 3225: 3197: 3190: 3150: 3131:(4): 642–654, 3094:(1): 109–117, 3047: 3008: 2940:(1): 111–120, 2921: 2885: 2873: 2834: 2828:10.1.1.36.4358 2804: 2785:(3): 337–341, 2747: 2708: 2687:(2): 155–162, 2669: 2650:(2): 198–218, 2627: 2608:(4): 413–424, 2590: 2569:(3): 320–331, 2534: 2521: 2490:(2): 135–149, 2469: 2440:(3): 437–467, 2413: 2398: 2362: 2324: 2308: 2285: 2232:, p. 79, 2207: 2154: 2152: 2149: 2118: 2115: 2072: 2069: 1979: 1976: 1856: 1853: 1848:traffic signal 1830: 1827: 1782: 1779: 1760:fault-tolerant 1747: 1744: 1742: 1739: 1605: 1602: 1558: 1553: 1548: 1545: 1494: 1470: 1465: 1460: 1457: 1430: 1425: 1420: 1417: 1343:has thickness 1332: 1329: 1258: 1253: 1248: 1245: 1230: 1224:complete graph 1203: 1200: 1187:Planar 3-trees 1183:maximum degree 1110: 1107: 1105: 1102: 1086: 1085: 1074: 1070: 1065: 1062: 1057: 1053: 1049: 1044: 1041: 1036: 1032: 1029: 1026: 1023: 1020: 1017: 1014: 996: 995: 983: 978: 974: 971: 965: 961: 958: 955: 951: 946: 942: 939: 936: 933: 930: 927: 921: 882: 839: 815: 788: 771: 770: 759: 754: 747: 743: 740: 737: 729: 722: 715: 711: 708: 705: 697: 690: 683: 679: 676: 673: 665: 658: 651: 648: 641: 634: 631: 611: 584: 581: 577: 573: 570: 550: 544:complete graph 539: 536: 491:book thickness 458:book embedding 425:is drawn as a 369:dihedral angle 285: 271: 268: 264:bioinformatics 251:Paul C. Kainen 242: 239: 215:bioinformatics 138: 135: 131: 127: 124: 90:book thickness 62:book embedding 44: 38:complete graph 26: 18:Book thickness 9: 6: 4: 3: 2: 5430: 5419: 5416: 5414: 5411: 5410: 5408: 5395: 5391: 5387: 5383: 5379: 5375: 5371: 5367: 5360: 5352: 5348: 5344: 5340: 5336: 5332: 5328: 5324: 5317: 5309: 5305: 5301: 5297: 5296: 5288: 5279: 5274: 5270: 5266: 5265: 5260: 5256: 5252: 5246: 5238: 5234: 5230: 5226: 5222: 5218: 5213: 5208: 5204: 5200: 5193: 5185: 5181: 5177: 5173: 5169: 5165: 5161: 5157: 5156: 5151: 5144: 5136: 5130: 5126: 5122: 5115: 5114: 5106: 5098: 5094: 5090: 5084: 5080: 5076: 5071: 5066: 5062: 5058: 5051: 5043: 5039: 5035: 5029: 5025: 5021: 5016: 5011: 5007: 5006: 5001: 4994: 4986: 4980: 4976: 4972: 4968: 4961: 4953: 4952: 4944: 4936: 4930: 4926: 4922: 4918: 4917: 4909: 4901: 4897: 4893: 4889: 4885: 4878: 4870: 4866: 4862: 4858: 4854: 4850: 4843: 4835: 4831: 4826: 4821: 4817: 4813: 4808: 4803: 4799: 4795: 4791: 4787: 4786: 4781: 4775: 4767: 4763: 4759: 4753: 4748: 4743: 4739: 4738: 4733: 4727: 4725: 4716: 4712: 4707: 4702: 4698: 4694: 4686: 4684: 4675: 4669: 4665: 4661: 4657: 4656: 4651: 4644: 4642: 4640: 4631: 4627: 4623: 4621:0-7695-1751-X 4617: 4613: 4609: 4605: 4601: 4595: 4593: 4584: 4580: 4576: 4572: 4566: 4558: 4554: 4550: 4546: 4542: 4540:0-201-89683-4 4536: 4532: 4531: 4526: 4520: 4512: 4508: 4504: 4500: 4494: 4487: 4482: 4474: 4470: 4466: 4462: 4458: 4454: 4449: 4444: 4440: 4436: 4435: 4430: 4424: 4417: 4412: 4404: 4400: 4396: 4392: 4388: 4382: 4378: 4374: 4369: 4364: 4360: 4359: 4351: 4337:on 2020-09-24 4333: 4326: 4325: 4320: 4314: 4312: 4310: 4301: 4297: 4293: 4289: 4285: 4281: 4280: 4275: 4271: 4270:Miller, G. L. 4267: 4263: 4257: 4249: 4245: 4241: 4237: 4233: 4229: 4228: 4220: 4218: 4216: 4214: 4205: 4203:3-540-18834-7 4199: 4195: 4191: 4187: 4186: 4178: 4170: 4164: 4160: 4156: 4152: 4145: 4137: 4133: 4129: 4125: 4124: 4116: 4112: 4108: 4104: 4098: 4096: 4094: 4085: 4084: 4079: 4073: 4065: 4061: 4057: 4053: 4049: 4045: 4039: 4031: 4027: 4023: 4019: 4015: 4011: 4010: 4002: 3994: 3990: 3985: 3980: 3976: 3972: 3971: 3966: 3959: 3955: 3951: 3947: 3943: 3939: 3935: 3931: 3930: 3929:Combinatorica 3925: 3921: 3917: 3911: 3907: 3903: 3899: 3895: 3891: 3887: 3883: 3882: 3852: 3834: 3828: 3824: 3820: 3816: 3812: 3808: 3804: 3800: 3793: 3787: 3779: 3774: 3770: 3766: 3760: 3758: 3749: 3745: 3740: 3739:10.37236/1029 3735: 3731: 3727: 3726: 3721: 3717: 3710: 3701: 3694: 3692: 3683: 3677: 3673: 3669: 3665: 3658: 3651: 3645: 3638: 3630: 3626: 3622: 3616: 3612: 3608: 3604: 3600: 3596: 3590: 3588: 3586: 3584: 3575: 3571: 3567: 3563: 3560:(1): 85–109, 3559: 3555: 3549: 3545: 3533: 3525: 3521: 3517: 3513: 3509: 3505: 3499: 3495: 3483: 3475: 3471: 3466: 3461: 3457: 3453: 3452: 3445: 3441: 3429: 3421: 3417: 3413: 3409: 3404: 3399: 3395: 3391: 3390: 3385: 3381: 3375: 3373: 3365: 3361: 3357: 3353: 3348: 3343: 3339: 3335: 3334: 3333:Combinatorica 3329: 3325: 3321: 3317: 3311: 3302: 3296: 3288: 3283: 3279: 3273: 3271: 3269: 3259: 3254: 3250: 3246: 3239: 3237: 3228: 3226:0-8186-0591-X 3222: 3218: 3214: 3210: 3209: 3201: 3193: 3191:9783939897651 3187: 3182: 3177: 3172: 3167: 3163: 3162: 3154: 3146: 3142: 3138: 3134: 3130: 3126: 3125: 3117: 3113: 3109: 3105: 3101: 3097: 3093: 3089: 3082: 3078: 3073: 3068: 3064: 3060: 3059: 3051: 3043: 3039: 3034: 3029: 3025: 3021: 3020: 3012: 3004: 3000: 2996: 2992: 2988: 2984: 2979: 2974: 2970: 2966: 2965: 2957: 2953: 2948: 2943: 2939: 2935: 2934: 2925: 2917: 2913: 2909: 2905: 2901: 2897: 2893: 2888: 2877: 2869: 2865: 2860: 2855: 2851: 2847: 2846: 2838: 2829: 2824: 2820: 2813: 2811: 2809: 2800: 2796: 2792: 2788: 2784: 2780: 2779: 2772: 2768: 2764: 2756: 2754: 2752: 2743: 2739: 2734: 2729: 2725: 2721: 2720: 2712: 2704: 2700: 2695: 2690: 2686: 2682: 2681: 2673: 2665: 2661: 2657: 2653: 2649: 2645: 2644: 2636: 2634: 2632: 2623: 2619: 2615: 2611: 2607: 2603: 2602: 2594: 2586: 2582: 2577: 2572: 2568: 2564: 2563: 2558: 2551: 2549: 2547: 2545: 2543: 2541: 2539: 2531: 2525: 2517: 2513: 2508: 2507:2027.42/42419 2503: 2498: 2493: 2489: 2485: 2484: 2479: 2473: 2465: 2461: 2456: 2451: 2447: 2443: 2439: 2435: 2434: 2426: 2424: 2422: 2420: 2418: 2409: 2405: 2401: 2399:0-89791-193-8 2395: 2391: 2387: 2383: 2382: 2377: 2371: 2369: 2367: 2358: 2353: 2349: 2345: 2344: 2339: 2333: 2331: 2329: 2319: 2312: 2303: 2299: 2298:Harary, Frank 2295: 2289: 2281: 2277: 2272: 2267: 2263: 2259: 2258: 2250: 2248: 2239: 2235: 2231: 2227: 2226: 2214: 2212: 2203: 2199: 2194: 2189: 2185: 2181: 2180: 2174: 2162: 2160: 2155: 2148: 2146: 2142: 2137: 2135: 2131: 2130:zero divisors 2127: 2123: 2114: 2112: 2108: 2103: 2101: 2097: 2093: 2089: 2085: 2081: 2077: 2068: 2065: 2061: 2057: 2055: 2051: 2047: 2043: 2042:diagram graph 2039: 2035: 2031: 2030:bipartiteness 2027: 2021: 2018: 2014: 2009: 2005: 2001: 1993: 1989: 1984: 1975: 1973: 1969: 1964: 1962: 1958: 1953: 1951: 1947: 1943: 1939: 1929: 1925: 1920: 1915: 1913: 1906: 1905:Chvátal graph 1901: 1897: 1895: 1890: 1885: 1880: 1878: 1877:graph drawing 1870: 1866: 1861: 1855:Graph drawing 1852: 1849: 1845: 1844:Kainen (1990) 1835: 1826: 1824: 1820: 1816: 1812: 1808: 1804: 1800: 1796: 1792: 1788: 1781:Stack sorting 1778: 1776: 1772: 1768: 1764: 1761: 1757: 1753: 1738: 1736: 1732: 1728: 1724: 1722: 1718: 1714: 1710: 1705: 1700: 1698: 1694: 1689: 1670: 1666: 1662: 1658: 1657:circle graphs 1655: 1650: 1646: 1642: 1638: 1633: 1631: 1627: 1619: 1615: 1610: 1601: 1599: 1595: 1591: 1579: 1574: 1551: 1543: 1533: 1527: 1522: 1520: 1516: 1512: 1508: 1504: 1503:shallow minor 1499: 1493: 1488: 1484: 1463: 1455: 1444: 1423: 1415: 1401: 1394: 1386: 1381: 1379: 1375: 1366: 1350: 1338: 1328: 1326: 1322: 1318: 1312: 1308: 1275: 1272: 1251: 1243: 1233: 1229: 1225: 1220: 1219:diamond graph 1216: 1208: 1199: 1197: 1192: 1188: 1184: 1179: 1177: 1173: 1169: 1165: 1161: 1149: 1143: 1140: 1136: 1120: 1115: 1101: 1099: 1095: 1091: 1072: 1068: 1063: 1060: 1055: 1051: 1047: 1042: 1039: 1034: 1027: 1024: 1021: 1015: 1012: 1005: 1004: 1003: 981: 976: 972: 969: 963: 959: 956: 953: 949: 944: 937: 934: 931: 925: 919: 911: 910: 909: 899: 889: 885: 881: 877: 871: 867: 863: 859: 854: 846: 842: 838: 831: 827: 823: 814: 807: 803: 795: 791: 787: 783: 778: 776: 757: 745: 741: 738: 735: 713: 709: 706: 703: 681: 677: 674: 671: 649: 646: 632: 629: 620: 619: 618: 614: 610: 604: 598: 579: 575: 571: 558: 549: 545: 535: 533: 527: 525: 520: 516: 512: 500: 496: 492: 471: 459: 454: 448: 440: 428: 404: 392: 387: 384: 370: 362: 350: 346: 345:finite number 342: 338: 335:, called the 334: 330: 326: 323:, called the 319: 315: 311: 307: 299: 298:diamond graph 294: 284: 281: 280:utility graph 276: 267: 265: 261: 260:planar graphs 257: 252: 247: 238: 236: 232: 228: 224: 220: 216: 211: 210:traffic light 207: 202: 200: 196: 192: 191:graph drawing 188: 183: 180: 176: 172: 168: 164: 160: 156: 152: 133: 129: 125: 109: 107: 103: 99: 95: 91: 87: 83: 79: 75: 71: 67: 63: 59: 51: 43: 39: 34: 30: 19: 5369: 5365: 5359: 5326: 5322: 5316: 5299: 5293: 5287: 5268: 5262: 5255:Kannan, Ravi 5245: 5202: 5198: 5192: 5159: 5153: 5143: 5112: 5105: 5060: 5050: 5004: 4993: 4966: 4960: 4950: 4943: 4915: 4908: 4883: 4877: 4852: 4848: 4842: 4789: 4783: 4774: 4736: 4696: 4692: 4654: 4603: 4574: 4565: 4529: 4519: 4502: 4493: 4481: 4448:math/0508324 4438: 4432: 4423: 4411: 4357: 4350: 4339:, retrieved 4332:the original 4323: 4283: 4277: 4262:Garey, M. R. 4256: 4231: 4225: 4184: 4177: 4150: 4144: 4130:(1): 33–58, 4127: 4121: 4082: 4072: 4055: 4051: 4038: 4013: 4007: 4001: 3974: 3968: 3963:Dvir, Zeev; 3933: 3927: 3920:Kannan, Ravi 3885: 3879: 3810: 3806: 3729: 3723: 3709: 3699: 3663: 3657: 3643: 3637: 3602: 3557: 3553: 3547: 3543: 3532: 3510:(1): 71–84, 3507: 3503: 3497: 3493: 3482: 3455: 3449: 3443: 3439: 3428: 3403:math/0503553 3393: 3387: 3337: 3331: 3310: 3248: 3244: 3207: 3200: 3160: 3153: 3128: 3122: 3091: 3087: 3062: 3056: 3050: 3023: 3017: 3011: 2968: 2962: 2937: 2936:, Series B, 2931: 2924: 2891: 2883: 2876: 2849: 2843: 2837: 2818: 2782: 2776: 2770: 2766: 2762: 2726:(1): 43–49, 2723: 2717: 2711: 2684: 2678: 2672: 2647: 2641: 2605: 2599: 2593: 2566: 2565:, Series B, 2560: 2524: 2487: 2481: 2478:Hales, T. C. 2472: 2437: 2431: 2380: 2347: 2341: 2317: 2311: 2301: 2288: 2264:(1): 43–45, 2261: 2255: 2246: 2220: 2183: 2177: 2172: 2138: 2132:of a finite 2120: 2104: 2084:reachability 2074: 2058: 2046:planar graph 2041: 2034:circle graph 2022: 1997: 1965: 1954: 1927: 1923: 1916: 1909: 1893: 1881: 1874: 1841: 1791:permutations 1784: 1749: 1741:Applications 1725: 1701: 1690: 1645:Unger (1992) 1634: 1623: 1614:circle graph 1598:queue number 1590:stack number 1589: 1575: 1531: 1523: 1507:sparse graph 1500: 1491: 1399: 1392: 1382: 1374:subdivisions 1334: 1310: 1306: 1231: 1227: 1213: 1180: 1148:planar graph 1144: 1124: 1087: 997: 893:formed from 887: 883: 879: 869: 865: 861: 855: 844: 840: 836: 829: 825: 821: 812: 805: 801: 793: 789: 785: 779: 775:Anthony Hill 772: 612: 608: 605: 556: 547: 541: 531: 528: 510: 499:stack number 498: 494: 490: 457: 455: 438: 397:onto a book 391:book drawing 390: 388: 382: 340: 336: 328: 324: 305: 303: 282: 248: 244: 203: 195:arc diagrams 184: 110: 101: 97: 93: 89: 85: 73: 61: 58:graph theory 55: 50:planar graph 41: 29: 4699:: 150–172, 3977:: 291–308, 3936:(1): 9–19, 3913:. See also 3888:(1): 1–41, 3119:. See also 2241:. See also 2186:: 169–173, 2086:problem in 2064:NP-hardness 2050:linear time 2017:pseudoknots 1978:RNA folding 1968:Wood (2002) 1919:NP-complete 1884:arc diagram 1865:arc diagram 1815:permutation 1807:data stream 1693:linear time 1637:linear time 1630:NP-complete 1304:is at most 1274:conjectured 1215:Subdividing 858:Turán graph 849:is exactly 798:is at most 597:upper bound 359:-axis of a 333:half-planes 270:Definitions 235:knot theory 227:pseudoknots 173:or bounded 98:stacknumber 78:half-planes 5407:Categories 5251:Galil, Zvi 4341:2014-06-16 3916:Galil, Zvi 3786:cite arXiv 3778:1501.05020 3437:-trees is 3347:2011.04195 3324:Morin, Pat 3295:cite arXiv 3258:2004.07630 2170:-books in 2151:References 2134:local ring 1992:pseudoknot 1990:showing a 1988:telomerase 1926:(log 1697:SPQR trees 1383:Graphs of 1365:half plane 1104:Properties 832:− 1) 495:pagenumber 355:to be the 94:pagenumber 5394:116488382 5351:121089736 5302:: 55–63, 5212:1001.2034 5070:1408.6321 5015:1308.5741 4855:: 21–26, 4557:155842391 4368:1209.0598 3910:121554827 3732:(1): R3, 3364:226281691 3171:1401.0684 2978:1210.2918 2971:: 80–93, 2823:CiteSeerX 2350:: 36–67, 2008:basepairs 1946:treewidth 1385:treewidth 1337:thickness 1196:treewidth 1025:− 1016:≤ 998:and when 960:≤ 954:≤ 935:− 739:− 707:− 675:− 583:⌉ 569:⌈ 524:intervals 511:pagewidth 171:treewidth 137:⌉ 123:⌈ 5176:22159642 5042:10142319 4834:16591215 4527:(1968), 4403:15360191 4113:(1987), 3958:37506294 3801:(2009), 3601:(2012), 3116:11830437 3003:40920263 2464:17883226 2300:(eds.), 1654:coloring 1160:subgraph 1069:⌉ 1056:⌈ 1048:⌉ 1035:⌈ 982:⌉ 964:⌈ 950:⌉ 920:⌈ 856:For the 753:⌋ 728:⌊ 721:⌋ 696:⌊ 689:⌋ 664:⌊ 657:⌋ 640:⌊ 515:cutwidth 349:embedded 5386:1885279 5343:1746427 5308:2656248 5237:8666071 5229:2988774 5184:8700502 5097:3333228 4888:Bibcode 4869:0311416 4816:0166772 4794:Bibcode 4766:1962433 4715:2922068 4583:1041623 4549:0286317 4511:0885282 4473:1139740 4465:2397336 4395:3067219 4300:0578325 4248:1032144 4064:2081479 4030:1181408 3993:2770077 3950:1010295 3902:3037896 3827:2537230 3748:2200531 3629:2920058 3574:1279270 3524:1279269 3474:1818238 3420:9141367 3145:1241401 3108:2596254 3081:1475820 3042:3061004 2995:3166108 2956:1469870 2916:8344088 2908:3050657 2868:1697548 2799:1710241 2742:1108073 2703:0968104 2664:0881181 2622:1377615 2585:0554297 2516:1455511 2455:7197269 2408:5359519 2280:0293592 2238:2617705 2202:0195077 2082:of the 2032:of the 1867:of the 1838:points. 1801: ( 1626:NP-hard 1495:2,2,2,2 1349:colored 403:drawing 241:History 179:NP-hard 5392: 5384: 5349: 5341: 5306: 5235: 5227: 5182: 5174: 5131: 5095: 5085: 5040: 5030: 4981: 4931: 4867: 4832: 4825:300329 4822: 4814: 4764: 4754: 4713: 4670: 4630:881989 4628: 4618: 4581: 4555: 4547: 4537: 4509: 4471: 4463: 4401: 4393: 4383: 4298: 4246: 4200: 4165: 4062: 4028: 3991: 3956: 3948: 3908: 3900: 3825: 3746: 3678: 3627: 3617: 3572: 3522: 3472: 3418: 3362: 3223: 3188: 3143: 3114: 3106: 3079: 3040: 3001: 2993: 2954: 2914: 2906: 2866: 2825: 2797: 2740: 2701: 2662: 2620: 2583: 2514: 2462: 2452: 2406: 2396: 2278: 2236: 2200: 1972:degree 1932:where 1795:stacks 1793:using 1775:stacks 1669:circle 1665:chords 1659:, the 1616:, the 1519:degree 1501:Every 1402:> 2 1369:θ 1361:θ 1353:θ 1345:θ 1133:is an 1096:, and 437:-page 433:. The 341:leaves 163:planar 5390:S2CID 5347:S2CID 5233:S2CID 5207:arXiv 5180:S2CID 5117:(PDF) 5065:arXiv 5038:S2CID 5010:arXiv 4626:S2CID 4469:S2CID 4443:arXiv 4399:S2CID 4363:arXiv 4335:(PDF) 4328:(PDF) 4118:(PDF) 3954:S2CID 3906:S2CID 3773:arXiv 3416:S2CID 3398:arXiv 3360:S2CID 3342:arXiv 3282:arXiv 3253:arXiv 3166:arXiv 3112:S2CID 2999:S2CID 2973:arXiv 2912:S2CID 2404:S2CID 2252:(PDF) 2145:links 2141:knots 1667:of a 1443:genus 1351:with 1321:stars 1158:is a 824:> 497:, or 476:into 464:onto 449:in a 427:curve 401:is a 337:pages 325:spine 175:genus 86:spine 70:graph 68:of a 5172:PMID 5129:ISBN 5083:ISBN 5028:ISBN 4979:ISBN 4929:ISBN 4830:PMID 4752:ISBN 4668:ISBN 4616:ISBN 4553:OCLC 4535:ISBN 4381:ISBN 4198:ISBN 4163:ISBN 3792:link 3676:ISBN 3615:ISBN 3301:link 3221:ISBN 3186:ISBN 2769:log 2460:PMID 2394:ISBN 2143:and 1811:sort 1803:1968 1767:CPUs 1756:VLSI 1323:and 1117:The 890:,... 800:min( 329:back 318:line 306:book 278:The 233:and 197:and 187:VLSI 82:line 74:book 60:, a 5374:doi 5331:doi 5273:doi 5217:doi 5164:doi 5121:doi 5075:doi 5020:doi 4971:doi 4921:doi 4896:doi 4857:doi 4853:115 4820:PMC 4802:doi 4742:doi 4701:doi 4660:doi 4608:doi 4453:doi 4373:doi 4288:doi 4236:doi 4190:doi 4155:doi 4132:doi 4018:doi 3979:doi 3938:doi 3890:doi 3815:doi 3811:347 3734:doi 3668:doi 3607:doi 3562:doi 3552:", 3512:doi 3502:", 3460:doi 3456:109 3448:", 3408:doi 3352:doi 3213:doi 3176:doi 3133:doi 3096:doi 3067:doi 3028:doi 3024:313 2983:doi 2969:167 2942:doi 2896:doi 2854:doi 2787:doi 2728:doi 2689:doi 2652:doi 2610:doi 2571:doi 2502:hdl 2492:doi 2450:PMC 2442:doi 2386:doi 2352:doi 2266:doi 2188:doi 2176:", 2000:RNA 1882:An 1863:An 1842:As 1719:is 1663:of 1395:+ 1 1376:of 1319:of 1296:is 900:of 874:(a 816:4,4 617:is 559:≥ 4 519:ray 501:of 484:on 472:of 460:of 441:of 409:on 405:of 339:or 327:or 314:fan 286:3,3 219:RNA 204:In 100:or 56:In 5409:: 5388:, 5382:MR 5380:, 5370:69 5368:, 5345:, 5339:MR 5337:, 5327:33 5325:, 5304:MR 5300:95 5298:, 5269:38 5267:, 5257:; 5253:; 5231:, 5225:MR 5223:, 5215:, 5203:21 5201:, 5178:, 5170:, 5160:65 5158:, 5127:, 5093:MR 5091:, 5081:, 5073:, 5036:, 5026:, 5018:, 4977:, 4927:, 4894:, 4865:MR 4863:, 4851:, 4828:, 4818:, 4812:MR 4810:, 4800:, 4790:52 4788:, 4762:MR 4760:, 4750:, 4723:^ 4711:MR 4709:, 4697:14 4695:, 4682:^ 4666:, 4638:^ 4624:, 4614:, 4591:^ 4579:MR 4551:, 4545:MR 4543:, 4507:MR 4467:, 4461:MR 4459:, 4451:, 4439:29 4437:, 4397:, 4391:MR 4389:, 4379:, 4371:, 4308:^ 4296:MR 4294:, 4282:, 4272:; 4268:; 4264:; 4244:MR 4242:, 4232:39 4230:, 4212:^ 4196:, 4161:, 4126:, 4120:, 4109:; 4105:; 4092:^ 4060:MR 4054:, 4046:; 4026:MR 4024:, 4014:21 4012:, 3989:MR 3987:, 3973:, 3961:; 3952:, 3946:MR 3944:, 3932:, 3922:; 3918:; 3904:, 3898:MR 3896:, 3886:23 3884:, 3830:; 3823:MR 3821:, 3809:, 3805:, 3788:}} 3784:{{ 3756:^ 3744:MR 3742:, 3730:13 3728:, 3718:; 3690:^ 3674:, 3625:MR 3623:, 3613:, 3597:; 3582:^ 3570:MR 3568:, 3558:17 3556:, 3546:(√ 3520:MR 3518:, 3508:17 3506:, 3496:(√ 3470:MR 3468:, 3454:, 3414:, 3406:, 3394:37 3392:, 3382:; 3371:^ 3358:, 3350:, 3338:42 3336:, 3326:; 3318:; 3297:}} 3293:{{ 3267:^ 3247:, 3235:^ 3219:, 3184:, 3174:, 3141:MR 3139:, 3127:, 3110:, 3104:MR 3102:, 3090:, 3084:; 3077:MR 3075:, 3063:78 3061:, 3038:MR 3036:, 3022:, 2997:, 2991:MR 2989:, 2981:, 2967:, 2959:; 2952:MR 2950:, 2938:71 2910:, 2904:MR 2902:, 2864:MR 2862:, 2850:92 2848:, 2807:^ 2795:MR 2793:, 2783:12 2781:, 2750:^ 2738:MR 2736:, 2724:89 2722:, 2699:MR 2697:, 2685:79 2683:, 2660:MR 2658:, 2646:, 2630:^ 2618:MR 2616:, 2606:21 2604:, 2581:MR 2579:, 2567:27 2537:^ 2512:MR 2510:, 2500:, 2488:18 2486:, 2458:, 2448:, 2438:61 2436:, 2416:^ 2402:, 2392:, 2365:^ 2348:38 2346:, 2327:^ 2276:MR 2274:, 2262:74 2260:, 2254:, 2234:MR 2210:^ 2198:MR 2196:, 2184:18 2182:, 2158:^ 2096:UP 2056:. 1952:. 1723:. 1612:A 1600:. 1534:/3 1178:. 1092:, 866:kr 853:. 493:, 456:A 389:A 386:. 373:xz 304:A 266:. 237:. 96:, 5397:. 5376:: 5354:. 5333:: 5311:. 5282:. 5275:: 5240:. 5219:: 5209:: 5187:. 5166:: 5138:. 5123:: 5100:. 5077:: 5067:: 5045:. 5022:: 5012:: 4988:. 4973:: 4955:. 4938:. 4923:: 4903:. 4898:: 4890:: 4872:. 4859:: 4837:. 4804:: 4796:: 4769:. 4744:: 4718:. 4703:: 4677:. 4662:: 4633:. 4610:: 4586:. 4560:. 4514:. 4476:. 4455:: 4445:: 4406:. 4375:: 4365:: 4345:. 4303:. 4290:: 4284:1 4251:. 4238:: 4207:. 4192:: 4172:. 4157:: 4139:. 4134:: 4128:8 4067:. 4056:6 4033:. 4020:: 3996:. 3981:: 3975:6 3940:: 3934:9 3892:: 3866:) 3862:R 3858:( 3853:2 3848:L 3845:S 3817:: 3794:) 3775:: 3751:. 3736:: 3704:. 3685:. 3670:: 3652:. 3632:. 3609:: 3577:. 3564:: 3550:) 3548:g 3544:O 3539:g 3527:. 3514:: 3500:) 3498:E 3494:O 3489:E 3477:. 3462:: 3446:) 3444:k 3442:( 3440:O 3435:k 3423:. 3410:: 3400:: 3354:: 3344:: 3305:. 3303:) 3284:: 3262:. 3255:: 3249:1 3230:. 3215:: 3195:. 3178:: 3168:: 3148:. 3135:: 3129:6 3098:: 3092:3 3069:: 3045:. 3030:: 3006:. 2985:: 2975:: 2944:: 2919:. 2898:: 2886:n 2884:K 2871:. 2856:: 2832:. 2802:. 2789:: 2773:) 2771:N 2767:M 2765:( 2763:O 2745:. 2730:: 2706:. 2691:: 2667:. 2654:: 2648:8 2625:. 2612:: 2588:. 2573:: 2532:. 2519:. 2504:: 2494:: 2467:. 2444:: 2411:. 2388:: 2354:: 2322:. 2306:. 2283:. 2268:: 2247:n 2223:n 2205:. 2190:: 2173:E 2168:n 1934:n 1930:) 1928:n 1924:O 1685:G 1681:G 1677:G 1673:G 1586:x 1582:x 1571:n 1557:) 1552:n 1547:( 1544:O 1532:n 1530:2 1492:K 1469:) 1464:g 1459:( 1456:O 1446:g 1429:) 1424:m 1419:( 1416:O 1406:m 1400:k 1393:k 1388:k 1372:( 1357:G 1341:G 1313:) 1311:t 1309:( 1307:f 1302:G 1298:t 1294:H 1290:G 1286:H 1282:G 1278:f 1257:) 1252:n 1247:( 1244:O 1232:n 1228:K 1156:G 1152:G 1131:G 1127:G 1073:. 1064:4 1061:k 1052:+ 1043:2 1040:k 1031:) 1028:1 1022:r 1019:( 1013:t 1000:r 977:2 973:r 970:k 957:t 945:2 941:) 938:1 932:r 929:( 926:k 906:t 902:k 895:r 888:k 886:, 884:k 880:K 872:) 870:r 868:, 864:( 862:T 851:a 845:b 843:, 841:a 837:K 830:a 828:( 826:a 822:b 813:K 808:) 806:b 804:, 802:a 794:b 792:, 790:a 786:K 758:, 746:2 742:3 736:n 714:2 710:2 704:n 682:2 678:1 672:n 650:2 647:n 633:4 630:1 613:n 609:K 601:n 580:2 576:/ 572:n 557:n 551:5 548:K 507:G 503:G 486:B 482:G 478:B 474:G 466:B 462:G 451:k 443:G 435:k 431:B 423:G 419:B 415:G 411:B 407:G 399:B 395:G 383:k 381:/ 379:π 377:2 365:k 357:z 353:ℓ 321:ℓ 283:K 134:2 130:/ 126:n 113:n 45:5 42:K 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index