Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Book embedding
open-in-new
<h2 id="history">History</h2> <p>The notion of a book, as a topological space, was defined by C. A. Persinger and Gail Atneosen in the 1960s.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> 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. </p><p>In the early 1970s, <a href="/facts/Paul_Chester_Kainen/ajToeKL6">Paul C. Kainen</a> 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.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Important milestones in the later development of book embeddings include the proof by <a href="/facts/Mihalis_Yannakakis/sEHPDT9v">Mihalis Yannakakis</a> in the late 1980s that <a href="/facts/Planar_graphs/plREagr9">planar graphs</a> have book thickness at most four,<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> and the discovery in the late 1990s of close connections between book embeddings and <a href="/facts/Bioinformatics/D5x2L8ee">bioinformatics</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h2 id="definitions">Definitions</h2> <p>A book is a particular kind of <a href="/facts/Topological_space/v2ut7CbK">topological space</a>, also called a <a href="/facts/Sheaf_of_planes/xdzrLuPT">fan</a> of half-planes.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> It consists of a single <a href="/facts/Line_(geometry)/gJqsr4Gj">line</a> ℓ, called the spine or back of the book, together with a collection of one or more <a href="/facts/Half-plane/AGknBgnw">half-planes</a>, called the pages or leaves of the book,<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> each having the spine as its boundary. Books with a <a href="/facts/Finite_set/za1newlP">finite number</a> of pages can be <a href="/facts/Embedding/HKeVKc42">embedded</a> into three-dimensional space, for instance by choosing ℓ to be the z-axis of a <a href="/facts/Cartesian_coordinate_system/lkTqvMmB">Cartesian coordinate system</a> and choosing the pages to be the k half-planes whose <a href="/facts/Dihedral_angle/C9WEJsuS">dihedral angle</a> with respect to the xz-plane is an integer multiple of 2π/<i>k</i>.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p><p>A book drawing of a finite graph G onto a book B is a <a href="/facts/Graph_drawing/uhh73BVo">drawing</a> of G on B such that every vertex of G is drawn as a point on the spine of B, and every edge of G is drawn as a <a href="/facts/Curve/xBQ0pTBW">curve</a> that lies within a single page of B. The k-page book crossing number of G is the minimum <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">number of crossings</a> in a k-page book drawing.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p><p>A book embedding of G onto B is a book drawing that forms a <a href="/facts/Graph_embedding/IyBA3ttM">graph embedding</a> 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 <a href="/facts/Cutwidth/Tov7sEyX">cutwidth</a> as the maximum number of edges that can be crossed by a <a href="/facts/Ray_(geometry)/gJqsr4Gj">ray</a> 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 <a href="/facts/Interval_(mathematics)/e9se3vTe">intervals</a> defined on the spine by pairs of endpoints of the edges all intersect each other.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a><a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a><a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p><p>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.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a><a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a><a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> For such a three-page topological book embedding in which spine crossings are allowed, every graph can be embedded with at most a logarithmic number of spine crossings per edge,<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> and some graphs need this many spine crossings.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> </p> <h2 id="specific-graphs">Specific graphs</h2> <p>As shown in the first figure, the book thickness of the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> <i>K</i>5 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 <i>n</i> ≥ 4 vertices is exactly ⌈ n / 2 ⌉ {\displaystyle \lceil n/2\rceil } . This result also gives an <a href="/facts/Upper_bound/YJje9oC2">upper bound</a> on the maximum possible book thickness of any n-vertex graph.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> </p><p>The two-page crossing number of the complete graph <i>K</i><i>n</i> is </p> 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ , {\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 },} <p>matching a still-unproven conjecture of <a href="/facts/Anthony_Hill_(artist)/yrdqjq4M">Anthony Hill</a> 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.<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> </p><p>The book thickness of the <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> <i>K</i><i>a</i>,<i>b</i> is at most min(<i>a</i>,<i>b</i>). 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, <i>K</i>4,4 has book thickness three, not four. However, when the two sides of the graph are very unbalanced, with <i>b</i> > <i>a</i>(<i>a</i> − 1), the book thickness of <i>K</i><i>a</i>,<i>b</i> is exactly a.<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a><a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p><p>For the <a href="/facts/Tur%25C3%25A1n_graph/y0hzJqQQ">Turán graph</a> <i>T</i>(<i>kr</i>,<i>r</i>) (a <a href="/facts/Complete_multipartite_graph/dkylvqYK">complete multipartite graph</a> <i>K</i><i>k</i>,<i>k</i>,... formed from r <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent sets</a> of k vertices per independent set, with an edge between every two vertices from different independent sets) the book thickness t is sandwiched between </p> ⌈ k ( r − 1 ) 2 ⌉ ≤ t ≤ ⌈ k r 2 ⌉ {\displaystyle \left\lceil {\frac {k(r-1)}{2}}\right\rceil \leq t\leq \left\lceil {\frac {kr}{2}}\right\rceil } <p>and when r is odd the upper bound can be improved to </p> t ≤ ( r − 1 ) ⌈ k 2 ⌉ + ⌈ k 4 ⌉ . {\displaystyle t\leq (r-1)\left\lceil {\frac {k}{2}}\right\rceil +\left\lceil {\frac {k}{4}}\right\rceil .} <a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a><a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a> <p>The book thickness of binary <a href="/facts/De_Bruijn_graph/QKFsDeEw">de Bruijn graphs</a>, <a href="/facts/Shuffle-exchange_graph/vcYyHlgo">shuffle-exchange graphs</a>, and <a href="/facts/Cube-connected_cycles/KBfIJYuu">cube-connected cycles</a> (when these graphs are large enough to be nonplanar) is exactly three.<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a> </p> <h2 id="properties">Properties</h2> <h3>Planarity and outerplanarity</h3> <p>The book thickness of a given graph G is at most one if and only if G is an <a href="/facts/Outerplanar_graph/FrAgUpcV">outerplanar graph</a>. 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 <a href="/facts/Articulation_point/Y4221AkA">articulation point</a> 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.<a class="footnote-ref" id="fnref:28" href="#fn:28"><sup>28</sup></a><a class="footnote-ref" id="fnref:29" href="#fn:29"><sup>29</sup></a> </p><p>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 <a href="/facts/Planar_graph/plREagr9">planar graph</a>. More precisely, the book thickness of a graph G is at most two if and only if G is a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> of a planar graph that has a <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycle</a>.<a class="footnote-ref" id="fnref:30" href="#fn:30"><sup>30</sup></a> 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 <a href="/facts/Goldner%25E2%2580%2593Harary_graph/f3ekGlqy">Goldner–Harary graph</a> provides an example of a planar graph that does not have book thickness two: it is a <a href="/facts/Maximal_planar_graph/plREagr9">maximal planar graph</a>, so it is not possible to add any edges to it while preserving planarity, and it does not have a Hamiltonian cycle.<a class="footnote-ref" id="fnref:31" href="#fn:31"><sup>31</sup></a> Because of this characterization by Hamiltonian cycles, graphs that have two-page book embeddings are also known as <a href="/facts/Subhamiltonian_graph/uTfTwC3F">subhamiltonian graphs</a>.<a class="footnote-ref" id="fnref:32" href="#fn:32"><sup>32</sup></a> </p><p>All planar graphs whose <a href="/facts/Degree_(graph_theory)/LnFFpI8v">maximum degree</a> is at most four have book thickness at most two.<a class="footnote-ref" id="fnref:33" href="#fn:33"><sup>33</sup></a> <a href="/facts/Apollonian_network/C9m4Gd3J">Planar 3-trees</a> have book thickness at most three.<a class="footnote-ref" id="fnref:34" href="#fn:34"><sup>34</sup></a> More generally, all planar graphs have book thickness four.<a class="footnote-ref" id="fnref:35" href="#fn:35"><sup>35</sup></a><a class="footnote-ref" id="fnref:36" href="#fn:36"><sup>36</sup></a><a class="footnote-ref" id="fnref:37" href="#fn:37"><sup>37</sup></a> It has been claimed by <a href="/facts/Mihalis_Yannakakis/sEHPDT9v">Mihalis Yannakakis</a> in 1986<a class="footnote-ref" id="fnref:38" href="#fn:38"><sup>38</sup></a> 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,<a class="footnote-ref" id="fnref:39" href="#fn:39"><sup>39</sup></a> was not known until 2020, when Bekos et al.<a class="footnote-ref" id="fnref:40" href="#fn:40"><sup>40</sup></a> presented planar graphs with <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> 4 that require four pages in any book embedding. </p> <h3>Behavior under subdivisions</h3> <p><a href="/facts/Homeomorphism_(graph_theory)/WbFo1mNW">Subdividing</a> 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 <a href="/facts/Diamond_graph/8awrY0xS">diamond graph</a> 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 <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> <i>K</i><i>n</i> 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 O ( n ) {\displaystyle O({\sqrt {n}})} .<a class="footnote-ref" id="fnref:41" href="#fn:41"><sup>41</sup></a> Despite the existence of examples such as this one, Blankenship & Oporowski (1999) <a href="/facts/Conjecture/oPWUb7SF">conjectured</a> 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 <i>f</i>(<i>t</i>).<a class="footnote-ref" id="fnref:42" href="#fn:42"><sup>42</sup></a> Their conjecture turned out to be false: graphs formed by <a href="/facts/Cartesian_product_of_graphs/wC4JJdyU">Cartesian products</a> of <a href="/facts/Star_(graph_theory)/PNW0H6eK">stars</a> and <a href="/facts/Triangular_tiling/Jx8f8Krh">triangular tilings</a> have unbounded book thickness, but subdividing their edges into six-edge paths reduces their book thickness to three.<a class="footnote-ref" id="fnref:43" href="#fn:43"><sup>43</sup></a> </p> <h3>Relation to other graph invariants</h3> <p>Book thickness is related to <a href="/facts/Thickness_(graph_theory)/o9lnEd1c">thickness</a>, 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 <a href="/facts/Edge_coloring/AcdpUxCv">colored</a> 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 <a href="/facts/Half_plane/AGknBgnw">half plane</a>, 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 (<a href="/facts/Homeomorphism_(graph_theory)/WbFo1mNW">subdivisions</a> of <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a>) that have unbounded book thickness,<a class="footnote-ref" id="fnref:44" href="#fn:44"><sup>44</sup></a><a class="footnote-ref" id="fnref:45" href="#fn:45"><sup>45</sup></a><a class="footnote-ref" id="fnref:46" href="#fn:46"><sup>46</sup></a> despite having thickness two.<a class="footnote-ref" id="fnref:47" href="#fn:47"><sup>47</sup></a> </p><p>Graphs of <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> k have book thickness at most <i>k</i> + 1<a class="footnote-ref" id="fnref:48" href="#fn:48"><sup>48</sup></a><a class="footnote-ref" id="fnref:49" href="#fn:49"><sup>49</sup></a> and this bound is tight for <i>k</i> > 2.<a class="footnote-ref" id="fnref:50" href="#fn:50"><sup>50</sup></a> Graphs with m edges have book thickness O ( m ) {\displaystyle O({\sqrt {m}})} ,<a class="footnote-ref" id="fnref:51" href="#fn:51"><sup>51</sup></a> and graphs of <a href="/facts/Genus_(mathematics)/o1Yhf8ty">genus</a> g have book thickness O ( g ) {\displaystyle O({\sqrt {g}})} .<a class="footnote-ref" id="fnref:52" href="#fn:52"><sup>52</sup></a> More generally, it has been stated that every <a href="/facts/Robertson%25E2%2580%2593Seymour_theorem/J7g4CJ74">minor-closed graph family</a> has bounded book thickness.<a class="footnote-ref" id="fnref:53" href="#fn:53"><sup>53</sup></a><a class="footnote-ref" id="fnref:54" href="#fn:54"><sup>54</sup></a> However, the proof of this claim rests on a previous claim that graphs embedded on non-orientable surfaces have bounded book thickness, for which a detailed proof has not been supplied.<a class="footnote-ref" id="fnref:55" href="#fn:55"><sup>55</sup></a> The <a href="/facts/1-planar_graph/HxeXsKo9">1-planar graphs</a>, which are not closed under minors,<a class="footnote-ref" id="fnref:56" href="#fn:56"><sup>56</sup></a> have bounded book thickness,<a class="footnote-ref" id="fnref:57" href="#fn:57"><sup>57</sup></a> but some 1-planar graphs including <i>K</i>2,2,2,2 have book thickness at least four.<a class="footnote-ref" id="fnref:58" href="#fn:58"><sup>58</sup></a> </p><p>Every <a href="/facts/Shallow_minor/YS9HTlDL">shallow minor</a> of a graph of bounded book thickness is a <a href="/facts/Sparse_graph/xFC7b7s9">sparse graph</a>, 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 Nešetřil & Ossona de Mendez (2012), the graphs of bounded book thickness have <a href="/facts/Bounded_expansion/9Dv8GYp9">bounded expansion</a>.<a class="footnote-ref" id="fnref:59" href="#fn:59"><sup>59</sup></a> However, even the graphs of bounded <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>, a much stronger requirement than having bounded expansion, can have unbounded book thickness.<a class="footnote-ref" id="fnref:60" href="#fn:60"><sup>60</sup></a> </p><p>Because graphs of book thickness two are planar graphs, they obey the <a href="/facts/Planar_separator_theorem/IfwGC9y3">planar separator theorem</a>: they have separators, subsets of vertices whose removal splits the graph into pieces with at most 2<i>n</i>/3 vertices each, with only O ( n ) {\displaystyle O({\sqrt {n}})} 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.<a class="footnote-ref" id="fnref:61" href="#fn:61"><sup>61</sup></a> </p><p>The edges within a single page of a book embedding behave in some ways like a <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack data structure</a>. 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 <a href="/facts/Queue_(abstract_data_type)/hVPjPXus">queue data structure</a>, 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 <a href="/facts/Queue_number/d2ENH4YC">queue number</a>.<a class="footnote-ref" id="fnref:62" href="#fn:62"><sup>62</sup></a><a class="footnote-ref" id="fnref:63" href="#fn:63"><sup>63</sup></a><a class="footnote-ref" id="fnref:64" href="#fn:64"><sup>64</sup></a> </p> <h3>Computational complexity</h3> <p>Finding the book thickness of a graph is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>. This follows from the fact that finding Hamiltonian cycles in maximal planar graphs is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:65" href="#fn:65"><sup>65</sup></a> 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.<a class="footnote-ref" id="fnref:66" href="#fn:66"><sup>66</sup></a> </p><p>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 <a href="/facts/Linear_time/77T62gmf">linear time</a>, as an instance of <a href="/facts/Planarity_testing/uVBsYdgf">planarity testing</a> for a graph formed by augmenting the given graph with a cycle connecting the vertices in their spine ordering.<a class="footnote-ref" id="fnref:67" href="#fn:67"><sup>67</sup></a> Unger (1992) claimed that finding three-page embeddings with a fixed spine ordering can also be performed in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> although his writeup of this result omits many details.<a class="footnote-ref" id="fnref:68" href="#fn:68"><sup>68</sup></a> 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 <a href="/facts/Graph_coloring/J6HoBfP0">coloring</a> <a href="/facts/Circle_graph/mI27LMXp">circle graphs</a>, the <a href="/facts/Intersection_graph/IehIvyR3">intersection graphs</a> of <a href="/facts/Chord_(geometry)/aAyoEdLd">chords</a> of a <a href="/facts/Circle/9fy5ggKn">circle</a>. 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.<a class="footnote-ref" id="fnref:69" href="#fn:69"><sup>69</sup></a><a class="footnote-ref" id="fnref:70" href="#fn:70"><sup>70</sup></a><a class="footnote-ref" id="fnref:71" href="#fn:71"><sup>71</sup></a> 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.<a class="footnote-ref" id="fnref:72" href="#fn:72"><sup>72</sup></a> </p><p>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 <a href="/facts/Linear_time/77T62gmf">linear time</a> by an algorithm based on <a href="/facts/SPQR_tree/M5caazhq">SPQR trees</a>.<a class="footnote-ref" id="fnref:73" href="#fn:73"><sup>73</sup></a><a class="footnote-ref" id="fnref:74" href="#fn:74"><sup>74</sup></a> 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. </p><p>As a consequence of bounded expansion, the <a href="/facts/Subgraph_isomorphism/86LLWRg4">subgraph isomorphism</a> 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 <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> of the larger graph, or whether it has a <a href="/facts/Graph_homomorphism/XSljQ25z">graph homomorphism</a> to the larger graph.<a class="footnote-ref" id="fnref:75" href="#fn:75"><sup>75</sup></a><a class="footnote-ref" id="fnref:76" href="#fn:76"><sup>76</sup></a> For the same reason, the problem of testing whether a graph of bounded book thickness obeys a given formula of <a href="/facts/First_order_logic/lcISqWIg">first order logic</a> is <a href="/facts/Parameterized_complexity/RoyaJGgJ">fixed-parameter tractable</a>.<a class="footnote-ref" id="fnref:77" href="#fn:77"><sup>77</sup></a> </p><p>Bekos, Kaufmann & Zielke (2015) describe a system for finding optimal book embeddings by transforming the problem into an instance of the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a> and applying a SAT solver to the resulting problem. They state that their system is capable of finding an optimal embedding for 400-vertex <a href="/facts/Maximal_planar_graph/plREagr9">maximal planar graphs</a> in approximately 20 minutes.<a class="footnote-ref" id="fnref:78" href="#fn:78"><sup>78</sup></a> </p> <h2 id="applications">Applications</h2> <h3>Fault-tolerant multiprocessing</h3> <p>One of the main motivations for studying book embedding cited by Chung, Leighton & Rosenberg (1987) involves an application in <a href="/facts/VLSI/l1Wgqr27">VLSI</a> design, to the organization of <a href="/facts/Fault_tolerance/rasrYlJk">fault-tolerant</a> <a href="/facts/Multiprocessor/aDCfehDQ">multiprocessors</a>. In the DIOGENES system developed by these authors, the <a href="/facts/CPU/Jxp1bqMV">CPUs</a> 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 <a href="/facts/Physical_layout/96BnDlT2">physical layout</a> of this system). Communication links connecting these processors are grouped into "bundles" which correspond to the pages of a book and act like <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stacks</a>: 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.<a class="footnote-ref" id="fnref:79" href="#fn:79"><sup>79</sup></a> Book embedding may also be used to model the placement of wires connecting VLSI components into the layers of a circuit.<a class="footnote-ref" id="fnref:80" href="#fn:80"><sup>80</sup></a> </p> <h3>Stack sorting</h3> <p>Another application cited by Chung, Leighton & Rosenberg (1987) concerns sorting <a href="/facts/Permutation/JSw9ukmv">permutations</a> using <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stacks</a>. An influential result of <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a> (1968) showed that a system that processes a <a href="/facts/Data_stream/57yDhBCd">data stream</a> by pushing incoming elements onto a stack and then, at appropriately chosen times, popping them from the stack onto an output stream can <a href="/facts/Sorting_algorithm/PwHpj1Gs">sort</a> the data if and only if its initial order is described by a <a href="/facts/Permutation/JSw9ukmv">permutation</a> that avoids the <a href="/facts/Permutation_pattern/ytUU2b91">permutation pattern</a> 231.<a class="footnote-ref" id="fnref:81" href="#fn:81"><sup>81</sup></a> Since then, there has been much work on similar problems of sorting data streams by more general systems of stacks and queues. In the system considered by Chung, Leighton & Rosenberg (1987), each element from an input data stream must be pushed onto one of several stacks. Then, once all of the data has been pushed in this way, the items are popped from these stacks (in an appropriate order) onto an output stream. 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.<a class="footnote-ref" id="fnref:82" href="#fn:82"><sup>82</sup></a> </p> <h3>Traffic control</h3> <p>As Kainen (1990) described, a book embedding may be used to describe the phases of a <a href="/facts/Traffic_signal/v5pwcfsQ">traffic signal</a> 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 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.<a class="footnote-ref" id="fnref:83" href="#fn:83"><sup>83</sup></a> </p> <h3>Graph drawing</h3> <p>Book embedding has also been frequently applied in the visualization of network data. Two of the standard layouts in <a href="/facts/Graph_drawing/uhh73BVo">graph drawing</a>, arc diagrams<a class="footnote-ref" id="fnref:84" href="#fn:84"><sup>84</sup></a> and circular layouts,<a class="footnote-ref" id="fnref:85" href="#fn:85"><sup>85</sup></a> can be viewed as book embeddings, and book embedding has also been applied in the construction of clustered layouts,<a class="footnote-ref" id="fnref:86" href="#fn:86"><sup>86</sup></a> simultaneous embeddings,<a class="footnote-ref" id="fnref:87" href="#fn:87"><sup>87</sup></a> and three-dimensional graph drawings.<a class="footnote-ref" id="fnref:88" href="#fn:88"><sup>88</sup></a> </p><p>An <a href="/facts/Arc_diagram/bb3aBBCj">arc diagram</a><a class="footnote-ref" id="fnref:89" href="#fn:89"><sup>89</sup></a> or linear embedding<a class="footnote-ref" id="fnref:90" href="#fn:90"><sup>90</sup></a> 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 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 <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">crossing numbers</a> of graphs.<a class="footnote-ref" id="fnref:91" href="#fn:91"><sup>91</sup></a><a class="footnote-ref" id="fnref:92" href="#fn:92"><sup>92</sup></a> 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.<a class="footnote-ref" id="fnref:93" href="#fn:93"><sup>93</sup></a> For every planar graph, it is always possible to find such an embedding in which each edge crosses the spine at most once.<a class="footnote-ref" id="fnref:94" href="#fn:94"><sup>94</sup></a> </p> <p>In another drawing style, the <a href="/facts/Circular_layout/41o5E5my">circular layout</a>, the vertices of a graph are placed on a circle and the edges are drawn either inside or outside the circle.<a class="footnote-ref" id="fnref:95" href="#fn:95"><sup>95</sup></a> 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.<a class="footnote-ref" id="fnref:96" href="#fn:96"><sup>96</sup></a> </p><p>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 <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>,<a class="footnote-ref" id="fnref:97" href="#fn:97"><sup>97</sup></a> but may be approximated with an approximation ratio of <i>O</i>(log2 <i>n</i>) where n is the number of vertices.<a class="footnote-ref" id="fnref:98" href="#fn:98"><sup>98</sup></a> Minimizing the one-page or two-page crossing number is <a href="/facts/Fixed-parameter_tractable/RoyaJGgJ">fixed-parameter tractable</a> when parameterized by the <a href="/facts/Cyclomatic_number/RqbfVDR6">cyclomatic number</a> of the given graph, or by a combination of the crossing number and the <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> of the graph.<a class="footnote-ref" id="fnref:99" href="#fn:99"><sup>99</sup></a><a class="footnote-ref" id="fnref:100" href="#fn:100"><sup>100</sup></a> Heuristic methods for reducing the crossing complexity have also been devised, based e.g. on a careful vertex insertion order and on <a href="/facts/Local_search_(optimization)/G1D2aHBz">local optimization</a>.<a class="footnote-ref" id="fnref:101" href="#fn:101"><sup>101</sup></a> </p><p>Two-page book embeddings with a fixed partition of the edges into pages can be interpreted as a form of <a href="/facts/Clustered_planarity/7Kp5ngtd">clustered planarity</a>, 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.<a class="footnote-ref" id="fnref:102" href="#fn:102"><sup>102</sup></a> Two-page book embedding has also been used to find <a href="/facts/Simultaneous_embedding/Ncdd2U0C">simultaneous embeddings</a> 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.<a class="footnote-ref" id="fnref:103" href="#fn:103"><sup>103</sup></a> </p><p>Book embeddings with more than two pages have also been used to construct three-dimensional drawings of graphs. In particular, Wood (2002) used a construction for book embeddings that keep the <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> of each vertex within each page low, as part of a method for embedding graphs into a three-dimensional grid of low volume.<a class="footnote-ref" id="fnref:104" href="#fn:104"><sup>104</sup></a> </p> <h3>RNA folding</h3> <p>In the study of how <a href="/facts/RNA/HxPeNfNj">RNA</a> molecules fold to form their structure, the standard form of <a href="/facts/Nucleic_acid_secondary_structure/qXjlsFK5">nucleic acid secondary structure</a> 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 <a href="/facts/Basepair/xmPpPQ9W">basepairs</a> 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. Haslinger & Stadler (1999) have proposed a so-called "bi-secondary structure" for certain RNA <a href="/facts/Pseudoknot/ATSPAmrV">pseudoknots</a> 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.<a class="footnote-ref" id="fnref:105" href="#fn:105"><sup>105</sup></a> </p><p>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 <a href="/facts/2-satisfiability/cUMH5x2y">2-satisfiability</a>, or as a problem of testing the <a href="/facts/Bipartite_graph/xWcXV9MB">bipartiteness</a> of the <a href="/facts/Circle_graph/mI27LMXp">circle graph</a> whose vertices are the basepairs and whose edges describe crossings between basepairs.<a class="footnote-ref" id="fnref:106" href="#fn:106"><sup>106</sup></a> Alternatively and more efficiently, as Haslinger & Stadler (1999) show, a bi-secondary structure exists if and only if the <i>diagram graph</i> 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 <a href="/facts/Planar_graph/plREagr9">planar graph</a>.<a class="footnote-ref" id="fnref:107" href="#fn:107"><sup>107</sup></a> This characterization allows bi-secondary structures to be recognized in <a href="/facts/Linear_time/77T62gmf">linear time</a> as an instance of <a href="/facts/Planarity_testing/uVBsYdgf">planarity testing</a>. </p><p>Blin et al. (2007) used the connection between secondary structures and book embeddings as part of a proof of the <a href="/facts/NP-hard/mQeNPv4R">NP-hardness</a> of certain problems in RNA secondary structure comparison.<a class="footnote-ref" id="fnref:108" href="#fn:108"><sup>108</sup></a> 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.<a class="footnote-ref" id="fnref:109" href="#fn:109"><sup>109</sup></a> </p> <h3>Computational complexity theory</h3> <p>Pavan, Tewari & Vinodchandran (2012) used book embedding to study the <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> of the <a href="/facts/Reachability/D8cQpSFQ">reachability</a> problem in <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a>. As they have observed, reachability for two-page directed graphs may be solved in unambiguous logarithmic space (the analogue, for <a href="/facts/L_(complexity)/vCMV0edS">logarithmic space complexity</a>, of the class <a href="/facts/UP_(complexity)/bVgohjhA">UP</a> of unambiguous polynomial-time problems). However, reachability for three-page directed graphs requires the full power of <a href="/facts/NL_(complexity)/FvNaeSaM">nondeterministic logarithmic space</a>. Thus, book embeddings seem intimately connected with the distinction between these two complexity classes.<a class="footnote-ref" id="fnref:110" href="#fn:110"><sup>110</sup></a> </p><p>The existence of <a href="/facts/Expander_graph/21stncb0">expander graphs</a> with constant page number<a class="footnote-ref" id="fnref:111" href="#fn:111"><sup>111</sup></a> is the key step in proving that there is no subquadratic-time simulation of two-tape <a href="/facts/Non-deterministic_Turing_machine/zv2x6XPG">non-deterministic Turing machines</a> by one-tape non-deterministic Turing machines.<a class="footnote-ref" id="fnref:112" href="#fn:112"><sup>112</sup></a> </p> <h3>Other areas of mathematics</h3> <p>McKenzie & Overbay (2010) study applications of book thickness in <a href="/facts/Abstract_algebra/YNNE1CNz">abstract algebra</a>, using graphs defined from the <a href="/facts/Zero_divisor/5GraAU8o">zero divisors</a> of a finite <a href="/facts/Local_ring/gRTdg5Qx">local ring</a> by making a vertex for each zero divisor and an edge for each pair of values whose product is zero.<a class="footnote-ref" id="fnref:113" href="#fn:113"><sup>113</sup></a> </p><p>In a multi-paper sequence, Dynnikov has studied the topological book embeddings of <a href="/facts/Knot_(mathematics)/UMtKJ36m">knots</a> and <a href="/facts/Link_(knot_theory)/hoFDYmVj">links</a>, 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.<a class="footnote-ref" id="fnref:114" href="#fn:114"><sup>114</sup></a><a class="footnote-ref" id="fnref:115" href="#fn:115"><sup>115</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Persinger, C. A. (1966), "Subsets of n-books in E3", Pacific Journal of Mathematics, 18: 169–173, doi:10.2140/pjm.1966.18.169, MR 0195077. <a href="/wiki/Pacific_Journal_of_Mathematics" target="_blank">/wiki/Pacific_Journal_of_Mathematics</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Atneosen, Gail Adele (1968), On the embeddability of compacta in n-books: intrinsic and extrinsic properties, Ph.D. thesis, Michigan State University, p. 79, MR 2617705. See also Atneosen, Gail H. (1972), "One-dimensional n-leaved continua" (PDF), Fundamenta Mathematicae, 74 (1): 43–45, doi:10.4064/fm-74-1-43-45, MR 0293592. <a href="http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:6905835" target="_blank">http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:6905835</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Kainen, Paul C. (1974), "Some recent results in topological graph theory", in Bari, Ruth A.; Harary, Frank (eds.), Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973), Lecture Notes in Mathematics, vol. 406, pp. 76–108. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Ollmann, L. Taylor (1973), "On the book thicknesses of various graphs", in Hoffman, Frederick; Levow, Roy B.; Thomas, Robert S. D. (eds.), Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. VIII, p. 459. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Yannakakis, Mihalis (1989), "Embedding planar graphs in four pages", Journal of Computer and System Sciences, 38: 36–67, doi:10.1016/0022-0000(89)90032-9 <a href="/wiki/Mihalis_Yannakakis" target="_blank">/wiki/Mihalis_Yannakakis</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Yannakakis, Mihalis (1986), "Four pages are necessary and sufficient for planar graphs", Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86), pp. 104–108, doi:10.1145/12130.12141, ISBN 0-89791-193-8, S2CID 5359519. <a href="0-89791-193-8" target="_blank">0-89791-193-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Haslinger, Christian; Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties", Bulletin of Mathematical Biology, 61 (3): 437–467, doi:10.1006/bulm.1998.0085, PMC 7197269, PMID 17883226. <a href="/wiki/Bulletin_of_Mathematical_Biology" target="_blank">/wiki/Bulletin_of_Mathematical_Biology</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Persinger, C. A. (1966), "Subsets of n-books in E3", Pacific Journal of Mathematics, 18: 169–173, doi:10.2140/pjm.1966.18.169, MR 0195077. <a href="/wiki/Pacific_Journal_of_Mathematics" target="_blank">/wiki/Pacific_Journal_of_Mathematics</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Hales, T. C. (1997), "Sphere packings. II", Discrete and Computational Geometry, 18 (2): 135–149, doi:10.1007/PL00009312, hdl:2027.42/42419, MR 1455511. <a href="/wiki/Thomas_Callister_Hales" target="_blank">/wiki/Thomas_Callister_Hales</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>The "spine" and "pages" terminology is more standard in modern graph-theoretic approaches to the subject. For the "back" and "leaves" terminology, see Persinger (1966). - Persinger, C. A. (1966), "Subsets of n-books in E3", Pacific Journal of Mathematics, 18: 169–173, doi:10.2140/pjm.1966.18.169, MR 0195077 <a href="https://doi.org/10.2140%2Fpjm.1966.18.169" target="_blank">https://doi.org/10.2140%2Fpjm.1966.18.169</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Shahrokhi, Farhad; Székely, László A.; Sýkora, Ondrej; Vrťo, Imrich (1996), "The book crossing number of a graph", Journal of Graph Theory, 21 (4): 413–424, doi:10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5, MR 1377615. <a href="/wiki/Journal_of_Graph_Theory" target="_blank">/wiki/Journal_of_Graph_Theory</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 198–218, doi:10.1137/0608018, MR 0881181. <a href="/wiki/SIAM_Journal_on_Algebraic_and_Discrete_Methods" target="_blank">/wiki/SIAM_Journal_on_Algebraic_and_Discrete_Methods</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Stöhr, Elena (1988), "A trade-off between page number and page width of book embeddings of graphs", Information and Computation, 79 (2): 155–162, doi:10.1016/0890-5401(88)90036-3, MR 0968104. <a href="/wiki/Information_and_Computation" target="_blank">/wiki/Information_and_Computation</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Stöhr, Elena (1991), "The pagewidth of trivalent planar graphs", Discrete Mathematics, 89 (1): 43–49, doi:10.1016/0012-365X(91)90398-L, MR 1108073. <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), "Embedding graphs into a three page book with O(M log N) crossings of edges over the spine", SIAM Journal on Discrete Mathematics, 12 (3): 337–341, doi:10.1137/S0895480195280319, MR 1710241. <a href="/wiki/SIAM_Journal_on_Discrete_Mathematics" target="_blank">/wiki/SIAM_Journal_on_Discrete_Mathematics</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Atneosen, Gail Adele (1968), On the embeddability of compacta in n-books: intrinsic and extrinsic properties, Ph.D. thesis, Michigan State University, p. 79, MR 2617705. See also Atneosen, Gail H. (1972), "One-dimensional n-leaved continua" (PDF), Fundamenta Mathematicae, 74 (1): 43–45, doi:10.4064/fm-74-1-43-45, MR 0293592. <a href="http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:6905835" target="_blank">http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:6905835</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Blankenship, Robin; Oporowski, Bogdan (1999), Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books, Technical Report 1999-4, Department of Mathematics, Louisiana State University, CiteSeerX 10.1.1.36.4358. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), "Embedding graphs into a three page book with O(M log N) crossings of edges over the spine", SIAM Journal on Discrete Mathematics, 12 (3): 337–341, doi:10.1137/S0895480195280319, MR 1710241. <a href="/wiki/SIAM_Journal_on_Discrete_Mathematics" target="_blank">/wiki/SIAM_Journal_on_Discrete_Mathematics</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>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", Discrete Applied Mathematics, 92 (2–3): 149–155, doi:10.1016/S0166-218X(99)00044-X, MR 1697548. <a href="/wiki/Discrete_Applied_Mathematics" target="_blank">/wiki/Discrete_Applied_Mathematics</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Ábrego, Bernardo M.; Aichholzer, Oswin; Fernández-Merchant, Silvia; Ramos, Pedro; Salazar, Gelasio (2012), "The 2-page crossing number of Kn (extended abstract)", Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12), ACM, New York, pp. 397–403, doi:10.1145/2261250.2261310, MR 3050657, S2CID 8344088. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>For additional results on the book thickness of complete bipartite graphs, see Enomoto, Hikoe; Nakamigawa, Tomoki; Ota, Katsuhiro (1997), "On the pagenumber of complete bipartite graphs", Journal of Combinatorial Theory, Series B, 71 (1): 111–120, doi:10.1006/jctb.1997.1773, MR 1469870; de Klerk, Etienne; Pasechnik, Dmitrii V.; Salazar, Gelasio (2014), "Book drawings of complete bipartite graphs", Discrete Applied Mathematics, 167: 80–93, arXiv:1210.2918, doi:10.1016/j.dam.2013.11.001, MR 3166108, S2CID 40920263. <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>Sperfeld, Konrad (2013), "On the page number of complete odd-partite graphs", Discrete Mathematics, 313 (17): 1689–1696, doi:10.1016/j.disc.2013.04.028, MR 3061004. <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>Hasunuma, Toru; Shibata, Yukio (1997), "Embedding de Bruijn, Kautz and shuffle-exchange networks in books", Discrete Applied Mathematics, 78 (1–3): 103–116, doi:10.1016/S0166-218X(97)00009-7, MR 1475820; Tanaka, Yuuki; Shibata, Yukio (2010), "On the pagenumber of the cube-connected cycles", Mathematics in Computer Science, 3 (1): 109–117, doi:10.1007/s11786-009-0012-y, MR 2596254, S2CID 11830437. See also Obrenić, Bojana (1993), "Embedding de Bruijn and shuffle-exchange graphs in five pages", SIAM Journal on Discrete Mathematics, 6 (4): 642–654, doi:10.1137/0406049, MR 1241401. <a href="/wiki/Discrete_Applied_Mathematics" target="_blank">/wiki/Discrete_Applied_Mathematics</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> <li id="fn:28"><p>Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></p></li> <li id="fn:29"><p>Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 198–218, doi:10.1137/0608018, MR 0881181. <a href="/wiki/SIAM_Journal_on_Algebraic_and_Discrete_Methods" target="_blank">/wiki/SIAM_Journal_on_Algebraic_and_Discrete_Methods</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></p></li> <li id="fn:30"><p>Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></p></li> <li id="fn:31"><p>Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></p></li> <li id="fn:32"><p>Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 198–218, doi:10.1137/0608018, MR 0881181. <a href="/wiki/SIAM_Journal_on_Algebraic_and_Discrete_Methods" target="_blank">/wiki/SIAM_Journal_on_Algebraic_and_Discrete_Methods</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></p></li> <li id="fn:33"><p>Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), "Two-page book embeddings of 4-planar graphs", Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 137–148, arXiv:1401.0684, doi:10.4230/LIPIcs.STACS.2014.137, ISBN 9783939897651. <a href="9783939897651" target="_blank">9783939897651</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></p></li> <li id="fn:34"><p>Heath, Lenny (1984), "Embedding planar graphs In seven pages", Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pp. 74–83, doi:10.1109/SFCS.1984.715903, ISBN 0-8186-0591-X. <a href="0-8186-0591-X" target="_blank">0-8186-0591-X</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></p></li> <li id="fn:35"><p>Yannakakis, Mihalis (1989), "Embedding planar graphs in four pages", Journal of Computer and System Sciences, 38: 36–67, doi:10.1016/0022-0000(89)90032-9 <a href="/wiki/Mihalis_Yannakakis" target="_blank">/wiki/Mihalis_Yannakakis</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></p></li> <li id="fn:36"><p>Yannakakis, Mihalis (1986), "Four pages are necessary and sufficient for planar graphs", Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86), pp. 104–108, doi:10.1145/12130.12141, ISBN 0-89791-193-8, S2CID 5359519. <a href="0-89791-193-8" target="_blank">0-89791-193-8</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></p></li> <li id="fn:37"><p>Bekos, Michael A.; Kaufmann, Micheal; Klute, Fabian; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), "Four Pages Are Indeed Necessary for Planar Graphs", Journal of Computational Geomerty, 1 (11): 332–353, arXiv:2004.07630. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></p></li> <li id="fn:38"><p>Yannakakis, Mihalis (1986), "Four pages are necessary and sufficient for planar graphs", Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86), pp. 104–108, doi:10.1145/12130.12141, ISBN 0-89791-193-8, S2CID 5359519. <a href="0-89791-193-8" target="_blank">0-89791-193-8</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></p></li> <li id="fn:39"><p>Yannakakis, Mihalis (1989), "Embedding planar graphs in four pages", Journal of Computer and System Sciences, 38: 36–67, doi:10.1016/0022-0000(89)90032-9 <a href="/wiki/Mihalis_Yannakakis" target="_blank">/wiki/Mihalis_Yannakakis</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></p></li> <li id="fn:40"><p>Bekos, Michael A.; Kaufmann, Micheal; Klute, Fabian; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), "Four Pages Are Indeed Necessary for Planar Graphs", Journal of Computational Geomerty, 1 (11): 332–353, arXiv:2004.07630. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></p></li> <li id="fn:41"><p>Eppstein, David (2001), "Separating geometric thickness from book thickness", arXiv:math.CO/0109195{{cite arXiv}}: CS1 maint: overridden setting (link). <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></p></li> <li id="fn:42"><p>Blankenship, Robin; Oporowski, Bogdan (1999), Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books, Technical Report 1999-4, Department of Mathematics, Louisiana State University, CiteSeerX 10.1.1.36.4358. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></p></li> <li id="fn:43"><p>Dujmović, Vida; Eppstein, David; Hickingbotham, Robert; Morin, Pat; Wood, David R. (August 2021), "Stack-number is not bounded by queue-number", Combinatorica, 42 (2): 151–164, arXiv:2011.04195, doi:10.1007/s00493-021-4585-7, S2CID 226281691 <a href="/wiki/Vida_Dujmovi%C4%87" target="_blank">/wiki/Vida_Dujmovi%C4%87</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></p></li> <li id="fn:44"><p>Eppstein, David (2001), "Separating geometric thickness from book thickness", arXiv:math.CO/0109195{{cite arXiv}}: CS1 maint: overridden setting (link). <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></p></li> <li id="fn:45"><p>Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), "Embedding graphs into a three page book with O(M log N) crossings of edges over the spine", SIAM Journal on Discrete Mathematics, 12 (3): 337–341, doi:10.1137/S0895480195280319, MR 1710241. <a href="/wiki/SIAM_Journal_on_Discrete_Mathematics" target="_blank">/wiki/SIAM_Journal_on_Discrete_Mathematics</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></p></li> <li id="fn:46"><p>Blankenship, Robin; Oporowski, Bogdan (1999), Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books, Technical Report 1999-4, Department of Mathematics, Louisiana State University, CiteSeerX 10.1.1.36.4358. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></p></li> <li id="fn:47"><p>Eppstein, David (2001), "Separating geometric thickness from book thickness", arXiv:math.CO/0109195{{cite arXiv}}: CS1 maint: overridden setting (link). <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></p></li> <li id="fn:48"><p>Dujmović, Vida; Wood, David R. (2007), "Graph treewidth and geometric thickness parameters", Discrete and Computational Geometry, 37 (4): 641–670, arXiv:math/0503553, doi:10.1007/s00454-007-1318-7, S2CID 9141367. <a href="/wiki/Vida_Dujmovi%C4%87" target="_blank">/wiki/Vida_Dujmovi%C4%87</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></p></li> <li id="fn:49"><p>Ganley, Joseph L.; Heath, Lenwood S. (2001), "The pagenumber of k-trees is O(k)", Discrete Applied Mathematics, 109 (3): 215–221, doi:10.1016/S0166-218X(00)00178-5, MR 1818238. <a href="/wiki/Discrete_Applied_Mathematics" target="_blank">/wiki/Discrete_Applied_Mathematics</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></p></li> <li id="fn:50"><p>Dujmović, Vida; Wood, David R. (2007), "Graph treewidth and geometric thickness parameters", Discrete and Computational Geometry, 37 (4): 641–670, arXiv:math/0503553, doi:10.1007/s00454-007-1318-7, S2CID 9141367. <a href="/wiki/Vida_Dujmovi%C4%87" target="_blank">/wiki/Vida_Dujmovi%C4%87</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></p></li> <li id="fn:51"><p>Malitz, Seth M. (1994), "Graphs with E edges have pagenumber O(√E)", Journal of Algorithms, 17 (1): 71–84, doi:10.1006/jagm.1994.1027, MR 1279269. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></p></li> <li id="fn:52"><p>Malitz, Seth M. (1994), "Genus g graphs have pagenumber O(√g)", Journal of Algorithms, 17 (1): 85–109, doi:10.1006/jagm.1994.1028, MR 1279270. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></p></li> <li id="fn:53"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058. <a href="978-3-642-27874-7" target="_blank">978-3-642-27874-7</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></p></li> <li id="fn:54"><p>Blankenship, R. (2003), Book Embeddings of Graphs, Ph.D. thesis, Department of Mathematics, Louisiana State University. As cited by Nešetřil & Ossona de Mendez (2012). - Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058 <a href="https://doi.org/10.1007%2F978-3-642-27875-4" target="_blank">https://doi.org/10.1007%2F978-3-642-27875-4</a> <a href="#fnref:54" class="footnote-back-ref">↩</a></p></li> <li id="fn:55"><p>Ozeki, Kenta; Nakamoto, Atsuhiro; Nozawa, Takayuki (2019), "Book embedding of graphs on the projective plane" (PDF), SIAM Journal on Discrete Mathematics, 33 (4): 1801–1836, doi:10.1137/16M1076174, MR 4013917 <a href="https://tgt.ynu.ac.jp/ozeki/2016NNO.pdf" target="_blank">https://tgt.ynu.ac.jp/ozeki/2016NNO.pdf</a> <a href="#fnref:55" class="footnote-back-ref">↩</a></p></li> <li id="fn:56"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058. <a href="978-3-642-27874-7" target="_blank">978-3-642-27874-7</a> <a href="#fnref:56" class="footnote-back-ref">↩</a></p></li> <li id="fn:57"><p>Bekos, Michael A.; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), "1-Planar graphs have constant book thickness", Algorithms – ESA 2015, Lecture Notes in Computer Science, vol. 9294, Springer, pp. 130–141, doi:10.1007/978-3-662-48350-3_12, ISBN 978-3-662-48349-7. <a href="978-3-662-48349-7" target="_blank">978-3-662-48349-7</a> <a href="#fnref:57" class="footnote-back-ref">↩</a></p></li> <li id="fn:58"><p>Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113–125. <a href="#fnref:58" class="footnote-back-ref">↩</a></p></li> <li id="fn:59"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058. <a href="978-3-642-27874-7" target="_blank">978-3-642-27874-7</a> <a href="#fnref:59" class="footnote-back-ref">↩</a></p></li> <li id="fn:60"><p>Barát, János; Matoušek, Jiří; Wood, David R. (2006), "Bounded-degree graphs have arbitrarily large geometric thickness", Electronic Journal of Combinatorics, 13 (1): R3, doi:10.37236/1029, MR 2200531. <a href="/wiki/Ji%C5%99%C3%AD_Matou%C5%A1ek_(mathematician)" target="_blank">/wiki/Ji%C5%99%C3%AD_Matou%C5%A1ek_(mathematician)</a> <a href="#fnref:60" class="footnote-back-ref">↩</a></p></li> <li id="fn:61"><p>Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R. (2015), "3-Monotone Expanders", arXiv:1501.05020 [math.CO]{{cite arXiv}}: CS1 maint: overridden setting (link), improving an earlier result showing the existence of expanders with constant pagenumber from Bourgain, Jean (2009), "Expanders and dimensional expansion", Comptes Rendus Mathématique, 347 (7–8): 357–362, doi:10.1016/j.crma.2009.02.009, MR 2537230; Bourgain, Jean; Yehudayoff, Amir (2013), "Expansion in S L 2 ( R ) {\displaystyle \mathrm {SL} _{2}(\mathbb {R} )} and monotone expanders", Geometric and Functional Analysis, 23 (1): 1–41, doi:10.1007/s00039-012-0200-9, MR 3037896, S2CID 121554827. See also Galil, Zvi; Kannan, Ravi; Szemerédi, Endre (1989), "On 3-pushdown graphs with large separators", Combinatorica, 9 (1): 9–19, doi:10.1007/BF02122679, MR 1010295, S2CID 37506294; Dvir, Zeev; Wigderson, Avi (2010), "Monotone expanders: constructions and applications", Theory of Computing, 6: 291–308, doi:10.4086/toc.2010.v006a012, MR 2770077. <a href="/wiki/Vida_Dujmovi%C4%87" target="_blank">/wiki/Vida_Dujmovi%C4%87</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></p></li> <li id="fn:62"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058. <a href="978-3-642-27874-7" target="_blank">978-3-642-27874-7</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></p></li> <li id="fn:63"><p>Heath, Lenwood S.; Rosenberg, Arnold L. (1992), "Laying out graphs using queues", SIAM Journal on Computing, 21 (5): 927–958, doi:10.1137/0221055, MR 1181408. <a href="/wiki/SIAM_Journal_on_Computing" target="_blank">/wiki/SIAM_Journal_on_Computing</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></p></li> <li id="fn:64"><p>Dujmović, Vida; Wood, David R. (2004), "On linear layouts of graphs", Discrete Mathematics & Theoretical Computer Science, 6 (2): 339–357, MR 2081479. <a href="/wiki/Vida_Dujmovi%C4%87" target="_blank">/wiki/Vida_Dujmovi%C4%87</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></p></li> <li id="fn:65"><p>Wigderson, Avi (February 1982), The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs (Technical Report #298), Department of EECS, Princeton University – via Institute for Advanced Study <a href="/wiki/Avi_Wigderson" target="_blank">/wiki/Avi_Wigderson</a> <a href="#fnref:65" class="footnote-back-ref">↩</a></p></li> <li id="fn:66"><p>Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design" (PDF), SIAM Journal on Algebraic and Discrete Methods, 8 (1): 33–58, doi:10.1137/0608002. <a href="/wiki/Fan_Chung" target="_blank">/wiki/Fan_Chung</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></p></li> <li id="fn:67"><p>Haslinger, Christian; Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties", Bulletin of Mathematical Biology, 61 (3): 437–467, doi:10.1006/bulm.1998.0085, PMC 7197269, PMID 17883226. <a href="/wiki/Bulletin_of_Mathematical_Biology" target="_blank">/wiki/Bulletin_of_Mathematical_Biology</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></p></li> <li id="fn:68"><p>Unger, Walter (1992), "The complexity of colouring circle graphs", STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings, Lecture Notes in Computer Science, vol. 577, Berlin: Springer, pp. 389–400, doi:10.1007/3-540-55210-3_199, ISBN 978-3-540-55210-9. <a href="978-3-540-55210-9" target="_blank">978-3-540-55210-9</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></p></li> <li id="fn:69"><p>Unger, Walter (1988), "On the k-colouring of circle-graphs", Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, vol. 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832, ISBN 3-540-18834-7. <a href="3-540-18834-7" target="_blank">3-540-18834-7</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></p></li> <li id="fn:70"><p>Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers, 39 (1): 124–127, doi:10.1109/12.46286, MR 1032144. <a href="/wiki/IEEE_Transactions_on_Computers" target="_blank">/wiki/IEEE_Transactions_on_Computers</a> <a href="#fnref:70" class="footnote-back-ref">↩</a></p></li> <li id="fn:71"><p>Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. (1980), "The complexity of coloring circular arcs and chords", SIAM Journal on Algebraic and Discrete Methods, 1 (2): 216–227, doi:10.1137/0601025, MR 0578325. <a href="/wiki/Michael_Garey" target="_blank">/wiki/Michael_Garey</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></p></li> <li id="fn:72"><p>Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers, 39 (1): 124–127, doi:10.1109/12.46286, MR 1032144. <a href="/wiki/IEEE_Transactions_on_Computers" target="_blank">/wiki/IEEE_Transactions_on_Computers</a> <a href="#fnref:72" class="footnote-back-ref">↩</a></p></li> <li id="fn:73"><p>Hong, Seok-Hee; Nagamochi, Hiroshi (2009), Two-page book embedding and clustered graph planarity (PDF), Technical report (2009-004 ed.), Dept. of Applied Mathematics and Physics, University of Kyoto, Japan, archived from the original (PDF) on 2020-09-24, retrieved 2014-06-16. <a href="/wiki/Seok-Hee_Hong" target="_blank">/wiki/Seok-Hee_Hong</a> <a href="#fnref:73" class="footnote-back-ref">↩</a></p></li> <li id="fn:74"><p>Angelini, Patrizio; Di Bartolomeo, Marco; Di Battista, Giuseppe (2013), "Implementing a partitioned 2-page book embedding testing algorithm", Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7704, Springer, pp. 79–89, arXiv:1209.0598, doi:10.1007/978-3-642-36763-2_8, ISBN 978-3-642-36762-5, MR 3067219, S2CID 15360191. <a href="978-3-642-36762-5" target="_blank">978-3-642-36762-5</a> <a href="#fnref:74" class="footnote-back-ref">↩</a></p></li> <li id="fn:75"><p>Nešetřil & Ossona de Mendez (2012), Corollary 18.1, p. 401. - Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058 <a href="https://doi.org/10.1007%2F978-3-642-27875-4" target="_blank">https://doi.org/10.1007%2F978-3-642-27875-4</a> <a href="#fnref:75" class="footnote-back-ref">↩</a></p></li> <li id="fn:76"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), "Grad and classes with bounded expansion. II. Algorithmic aspects", European Journal of Combinatorics, 29 (3): 777–791, arXiv:math/0508324, doi:10.1016/j.ejc.2006.07.014, MR 2397336, S2CID 1139740. <a href="/wiki/Jaroslav_Ne%C5%A1et%C5%99il" target="_blank">/wiki/Jaroslav_Ne%C5%A1et%C5%99il</a> <a href="#fnref:76" class="footnote-back-ref">↩</a></p></li> <li id="fn:77"><p>Nešetřil & Ossona de Mendez (2012), Theorem 18.7, p. 405. - Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058 <a href="https://doi.org/10.1007%2F978-3-642-27875-4" target="_blank">https://doi.org/10.1007%2F978-3-642-27875-4</a> <a href="#fnref:77" class="footnote-back-ref">↩</a></p></li> <li id="fn:78"><p>Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113–125. <a href="#fnref:78" class="footnote-back-ref">↩</a></p></li> <li id="fn:79"><p>Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design" (PDF), SIAM Journal on Algebraic and Discrete Methods, 8 (1): 33–58, doi:10.1137/0608002. <a href="/wiki/Fan_Chung" target="_blank">/wiki/Fan_Chung</a> <a href="#fnref:79" class="footnote-back-ref">↩</a></p></li> <li id="fn:80"><p>Rosenberg, Arnold L. (1986), "Book embeddings and wafer-scale integration", Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), Congressus Numerantium, vol. 54, pp. 217–224, MR 0885282. <a href="/wiki/Arnold_L._Rosenberg" target="_blank">/wiki/Arnold_L._Rosenberg</a> <a href="#fnref:80" class="footnote-back-ref">↩</a></p></li> <li id="fn:81"><p>Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, Section 2.2.1, Exercises 4 and 5, ISBN 0-201-89683-4, MR 0286317, OCLC 155842391. <a href="0-201-89683-4" target="_blank">0-201-89683-4</a> <a href="#fnref:81" class="footnote-back-ref">↩</a></p></li> <li id="fn:82"><p>Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design" (PDF), SIAM Journal on Algebraic and Discrete Methods, 8 (1): 33–58, doi:10.1137/0608002. <a href="/wiki/Fan_Chung" target="_blank">/wiki/Fan_Chung</a> <a href="#fnref:82" class="footnote-back-ref">↩</a></p></li> <li id="fn:83"><p>Kainen, Paul C. (1990), "The book thickness of a graph. II", Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congressus Numerantium, vol. 71, pp. 127–132, MR 1041623. <a href="/wiki/Paul_Chester_Kainen" target="_blank">/wiki/Paul_Chester_Kainen</a> <a href="#fnref:83" class="footnote-back-ref">↩</a></p></li> <li id="fn:84"><p>Wattenberg, M. (2002), "Arc diagrams: visualizing structure in strings", Proceedings of IEEE Symposium on Information Visualization (INFOVIS 2002), pp. 110–116, doi:10.1109/INFVIS.2002.1173155, ISBN 0-7695-1751-X, S2CID 881989. <a href="0-7695-1751-X" target="_blank">0-7695-1751-X</a> <a href="#fnref:84" class="footnote-back-ref">↩</a></p></li> <li id="fn:85"><p>Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, doi:10.1007/978-3-540-30559-0_28, ISBN 978-3-540-24132-4. <a href="978-3-540-24132-4" target="_blank">978-3-540-24132-4</a> <a href="#fnref:85" class="footnote-back-ref">↩</a></p></li> <li id="fn:86"><p>Hong, Seok-Hee; Nagamochi, Hiroshi (2009), Two-page book embedding and clustered graph planarity (PDF), Technical report (2009-004 ed.), Dept. of Applied Mathematics and Physics, University of Kyoto, Japan, archived from the original (PDF) on 2020-09-24, retrieved 2014-06-16. <a href="/wiki/Seok-Hee_Hong" target="_blank">/wiki/Seok-Hee_Hong</a> <a href="#fnref:86" class="footnote-back-ref">↩</a></p></li> <li id="fn:87"><p>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", Journal of Discrete Algorithms, 14: 150–172, doi:10.1016/j.jda.2011.12.015, MR 2922068. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:87" class="footnote-back-ref">↩</a></p></li> <li id="fn:88"><p>Wood, David R. (2002), "Bounded degree book embeddings and three-dimensional orthogonal graph drawing", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2265, Springer, Berlin, pp. 312–327, doi:10.1007/3-540-45848-4_25, ISBN 978-3-540-43309-5, MR 1962433. <a href="978-3-540-43309-5" target="_blank">978-3-540-43309-5</a> <a href="#fnref:88" class="footnote-back-ref">↩</a></p></li> <li id="fn:89"><p>Wattenberg, M. (2002), "Arc diagrams: visualizing structure in strings", Proceedings of IEEE Symposium on Information Visualization (INFOVIS 2002), pp. 110–116, doi:10.1109/INFVIS.2002.1173155, ISBN 0-7695-1751-X, S2CID 881989. <a href="0-7695-1751-X" target="_blank">0-7695-1751-X</a> <a href="#fnref:89" class="footnote-back-ref">↩</a></p></li> <li id="fn:90"><p>Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers, 39 (1): 124–127, doi:10.1109/12.46286, MR 1032144. <a href="/wiki/IEEE_Transactions_on_Computers" target="_blank">/wiki/IEEE_Transactions_on_Computers</a> <a href="#fnref:90" class="footnote-back-ref">↩</a></p></li> <li id="fn:91"><p>Saaty, Thomas L. (1964), "The minimum number of intersections in complete graphs", Proceedings of the National Academy of Sciences of the United States of America, 52 (3): 688–690, Bibcode:1964PNAS...52..688S, doi:10.1073/pnas.52.3.688, MR 0166772, PMC 300329, PMID 16591215. <a href="/wiki/Thomas_L._Saaty" target="_blank">/wiki/Thomas_L._Saaty</a> <a href="#fnref:91" class="footnote-back-ref">↩</a></p></li> <li id="fn:92"><p>Nicholson, T. A. J. (1968), "Permutation procedure for minimising the number of crossings in a network", Proceedings of the Institution of Electrical Engineers, 115: 21–26, doi:10.1049/piee.1968.0004, MR 0311416. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:92" class="footnote-back-ref">↩</a></p></li> <li id="fn:93"><p>Miyauchi, Miki (2006), "Topological book embedding of bipartite graphs", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A (5): 1223–1226, Bibcode:2006IEITF..89.1223M, doi:10.1093/ietfec/e89-a.5.1223. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:93" class="footnote-back-ref">↩</a></p></li> <li id="fn:94"><p>Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), "Computing upward topological book embeddings of upward planar digraphs", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4835, Springer, pp. 172–183, doi:10.1007/978-3-540-77120-3_17, ISBN 978-3-540-77118-0. <a href="978-3-540-77118-0" target="_blank">978-3-540-77118-0</a> <a href="#fnref:94" class="footnote-back-ref">↩</a></p></li> <li id="fn:95"><p>Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, doi:10.1007/978-3-540-30559-0_28, ISBN 978-3-540-24132-4. <a href="978-3-540-24132-4" target="_blank">978-3-540-24132-4</a> <a href="#fnref:95" class="footnote-back-ref">↩</a></p></li> <li id="fn:96"><p>He, Hongmei; Sykora, Ondrej (2004), "New circular drawing algorithms", Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15–19, 2004. <a href="https://dspace.lboro.ac.uk/2134/2386" target="_blank">https://dspace.lboro.ac.uk/2134/2386</a> <a href="#fnref:96" class="footnote-back-ref">↩</a></p></li> <li id="fn:97"><p>Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers, 39 (1): 124–127, doi:10.1109/12.46286, MR 1032144. <a href="/wiki/IEEE_Transactions_on_Computers" target="_blank">/wiki/IEEE_Transactions_on_Computers</a> <a href="#fnref:97" class="footnote-back-ref">↩</a></p></li> <li id="fn:98"><p>Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings, Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, doi:10.1007/3-540-59071-4_53, ISBN 978-3-540-59071-2. <a href="978-3-540-59071-2" target="_blank">978-3-540-59071-2</a> <a href="#fnref:98" class="footnote-back-ref">↩</a></p></li> <li id="fn:99"><p>Bannister, Michael J.; Eppstein, David; Simons, Joseph A. (2013), "Fixed parameter tractability of crossing minimization of almost-trees", Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23–25, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8242, pp. 340–351, arXiv:1308.5741, doi:10.1007/978-3-319-03841-4_30, ISBN 978-3-319-03840-7, S2CID 10142319. <a href="978-3-319-03840-7" target="_blank">978-3-319-03840-7</a> <a href="#fnref:99" class="footnote-back-ref">↩</a></p></li> <li id="fn:100"><p>Bannister, Michael J.; Eppstein, David (2014), "Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth", Proc. 22nd Int. Symp. Graph Drawing (GD 2014), Lecture Notes in Computer Science, vol. 8871, Springer-Verlag, pp. 210–221, arXiv:1408.6321, doi:10.1007/978-3-662-45803-7_18, ISBN 978-3-319-12567-1, MR 3333228. <a href="978-3-319-12567-1" target="_blank">978-3-319-12567-1</a> <a href="#fnref:100" class="footnote-back-ref">↩</a></p></li> <li id="fn:101"><p>Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, doi:10.1007/978-3-540-30559-0_28, ISBN 978-3-540-24132-4. <a href="978-3-540-24132-4" target="_blank">978-3-540-24132-4</a> <a href="#fnref:101" class="footnote-back-ref">↩</a></p></li> <li id="fn:102"><p>Hong, Seok-Hee; Nagamochi, Hiroshi (2009), Two-page book embedding and clustered graph planarity (PDF), Technical report (2009-004 ed.), Dept. of Applied Mathematics and Physics, University of Kyoto, Japan, archived from the original (PDF) on 2020-09-24, retrieved 2014-06-16. <a href="/wiki/Seok-Hee_Hong" target="_blank">/wiki/Seok-Hee_Hong</a> <a href="#fnref:102" class="footnote-back-ref">↩</a></p></li> <li id="fn:103"><p>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", Journal of Discrete Algorithms, 14: 150–172, doi:10.1016/j.jda.2011.12.015, MR 2922068. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:103" class="footnote-back-ref">↩</a></p></li> <li id="fn:104"><p>Wood, David R. (2002), "Bounded degree book embeddings and three-dimensional orthogonal graph drawing", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2265, Springer, Berlin, pp. 312–327, doi:10.1007/3-540-45848-4_25, ISBN 978-3-540-43309-5, MR 1962433. <a href="978-3-540-43309-5" target="_blank">978-3-540-43309-5</a> <a href="#fnref:104" class="footnote-back-ref">↩</a></p></li> <li id="fn:105"><p>Haslinger, Christian; Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties", Bulletin of Mathematical Biology, 61 (3): 437–467, doi:10.1006/bulm.1998.0085, PMC 7197269, PMID 17883226. <a href="/wiki/Bulletin_of_Mathematical_Biology" target="_blank">/wiki/Bulletin_of_Mathematical_Biology</a> <a href="#fnref:105" class="footnote-back-ref">↩</a></p></li> <li id="fn:106"><p>Haslinger, Christian; Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties", Bulletin of Mathematical Biology, 61 (3): 437–467, doi:10.1006/bulm.1998.0085, PMC 7197269, PMID 17883226. <a href="/wiki/Bulletin_of_Mathematical_Biology" target="_blank">/wiki/Bulletin_of_Mathematical_Biology</a> <a href="#fnref:106" class="footnote-back-ref">↩</a></p></li> <li id="fn:107"><p>Haslinger, Christian; Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties", Bulletin of Mathematical Biology, 61 (3): 437–467, doi:10.1006/bulm.1998.0085, PMC 7197269, PMID 17883226. <a href="/wiki/Bulletin_of_Mathematical_Biology" target="_blank">/wiki/Bulletin_of_Mathematical_Biology</a> <a href="#fnref:107" class="footnote-back-ref">↩</a></p></li> <li id="fn:108"><p>Blin, Guillaume; Fertin, Guillaume; Rusu, Irena; Sinoquet, Christine (2007), "Extending the hardness of RNA secondary structure comparison", Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers (PDF), Lecture Notes in Computer Science, vol. 4614, pp. 140–151, doi:10.1007/978-3-540-74450-4_13, ISBN 978-3-540-74449-8. <a href="978-3-540-74449-8" target="_blank">978-3-540-74449-8</a> <a href="#fnref:108" class="footnote-back-ref">↩</a></p></li> <li id="fn:109"><p>Clote, Peter; Dobrev, Stefan; Dotu, Ivan; Kranakis, Evangelos; Krizanc, Danny; Urrutia, Jorge (2012), "On the page number of RNA secondary structures with pseudoknots", Journal of Mathematical Biology, 65 (6–7): 1337–1357, doi:10.1007/s00285-011-0493-6, PMID 22159642, S2CID 8700502. <a href="/wiki/Jorge_Urrutia_Galicia" target="_blank">/wiki/Jorge_Urrutia_Galicia</a> <a href="#fnref:109" class="footnote-back-ref">↩</a></p></li> <li id="fn:110"><p>Pavan, A.; Tewari, Raghunath; Vinodchandran, N. V. (2012), "On the power of unambiguity in log-space", Computational Complexity, 21 (4): 643–670, arXiv:1001.2034, doi:10.1007/s00037-012-0047-3, MR 2988774, S2CID 8666071. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:110" class="footnote-back-ref">↩</a></p></li> <li id="fn:111"><p>Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R. (2015), "3-Monotone Expanders", arXiv:1501.05020 [math.CO]{{cite arXiv}}: CS1 maint: overridden setting (link), improving an earlier result showing the existence of expanders with constant pagenumber from Bourgain, Jean (2009), "Expanders and dimensional expansion", Comptes Rendus Mathématique, 347 (7–8): 357–362, doi:10.1016/j.crma.2009.02.009, MR 2537230; Bourgain, Jean; Yehudayoff, Amir (2013), "Expansion in S L 2 ( R ) {\displaystyle \mathrm {SL} _{2}(\mathbb {R} )} and monotone expanders", Geometric and Functional Analysis, 23 (1): 1–41, doi:10.1007/s00039-012-0200-9, MR 3037896, S2CID 121554827. See also Galil, Zvi; Kannan, Ravi; Szemerédi, Endre (1989), "On 3-pushdown graphs with large separators", Combinatorica, 9 (1): 9–19, doi:10.1007/BF02122679, MR 1010295, S2CID 37506294; Dvir, Zeev; Wigderson, Avi (2010), "Monotone expanders: constructions and applications", Theory of Computing, 6: 291–308, doi:10.4086/toc.2010.v006a012, MR 2770077. <a href="/wiki/Vida_Dujmovi%C4%87" target="_blank">/wiki/Vida_Dujmovi%C4%87</a> <a href="#fnref:111" class="footnote-back-ref">↩</a></p></li> <li id="fn:112"><p>Galil, Zvi; Kannan, Ravi; Szemerédi, Endre (1989), "On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines", Journal of Computer and System Sciences, 38 (1): 134–149, doi:10.1016/0022-0000(89)90036-6. <a href="/wiki/Zvi_Galil" target="_blank">/wiki/Zvi_Galil</a> <a href="#fnref:112" class="footnote-back-ref">↩</a></p></li> <li id="fn:113"><p>McKenzie, Thomas; Overbay, Shannon (2010), "Book embeddings and zero divisors", Ars Combinatoria, 95: 55–63, MR 2656248. <a href="/wiki/Ars_Combinatoria_(journal)" target="_blank">/wiki/Ars_Combinatoria_(journal)</a> <a href="#fnref:113" class="footnote-back-ref">↩</a></p></li> <li id="fn:114"><p>Dynnikov, I. A. (1999), "Three-page approach to knot theory. Coding and local motions", Rossiĭskaya Akademiya Nauk, 33 (4): 25–37, 96, doi:10.1007/BF02467109, MR 1746427, S2CID 121089736. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:114" class="footnote-back-ref">↩</a></p></li> <li id="fn:115"><p>Dynnikov, I. A. (2001), "A new way to represent links, one-dimensional formalism and untangling technology", Acta Applicandae Mathematicae, 69 (3): 243–283, doi:10.1023/A:1014299416618, MR 1885279, S2CID 116488382. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:115" class="footnote-back-ref">↩</a></p></li> </ol>