A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> Abstract The book thickness bt ( G ) of a graph G is defined, its basic properties are delineated, and relations are given with other invariants such as thickness, genus, and chromatic number. A graph G has book thickness bt ( G ) ≤ 2 if and only if it is a subgraph of a hamiltonian planar graph, but we conjecture that there are planar graphs with arbitrarily high book thickness. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> Abstract An algorithm is presented which embeds any planar graph in a book of four pages. The algorithm runs in linear time. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> Let G be a planar graph of n vertices, v1,..., vn, and let {p1,...,pn} be a set of n points in the plane. We present an algorithm for constructing in O(n2) time a planar embedding of G, where vertex vi is represented by point pi and each edge is represented by a polygonal curve with O(n) bends (internal vertices.) This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/403 bends. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> A new and distinct cultivar of Impatiens plant named Merengue, characterized by its large, light pink flowers with dark red-purple eye at base of petals; compact growth habit, excellent self-branching, dark green leaves infused with purple, pleasantly contrasting foliage and flower colors, floriferous habit, and its suitability for use both as a bedding plant and in its hanging basket culture. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> Point-set embeddings and large-angle crossings are two areas of graph drawing that independently have received a lot of attention in the past few years. In this paper, we consider problems in the intersection of these two areas. Given the point-set-embedding scenario, we are interested in how much we gain in terms of computational complexity, curve complexity, and generality if we allow large-angle crossings as compared to the planar case. ::: ::: We investigate two drawing styles where only bends or both bends and edges must be drawn on an underlying grid. We present various results for drawings with one, two, and three bends per edge. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> This paper describes algorithms for computing non-planar drawings of planar graphs in subquadratic area such that: (i) edge crossings are allowed only if they create large angles; (ii) the maximum number of bends per edge is bounded by a (small) constant. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> Note: Special Issue on Selected Papers from GD '09. Accepted, subject to minor revisions Reference EPFL-ARTICLE-158708 Record created on 2010-11-26, modified on 2017-05-12 <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> In a book embedding of a graph G, the vertices of G are placed in order along a straight-line called spine of the book, and the edges of G are drawn on a set of half-planes, called the pages of the book, such that two edges drawn on a page do not cross each other. The minimum number of pages in which a graph can be embedded is called the book-thickness or the page-number of the graph. It is known that every planar graph has a book embedding on at most four pages. Here we investigate the book-embeddings of 1-planar graphs. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. We prove that every 1-planar graph has a book embedding on at most 16 pages and every 3-connected 1-planar graph has a book embedding on at most 12 pages. The drawings can be computed in linear time from any given 1-planar embedding of the graph. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> In a book embedding, the vertices of a graph are placed on the spine of a book and the edges are assigned to pages, so that edges on the same page do not cross. In this paper, we prove that every $1$-planar graph (that is, a graph that can be drawn on the plane such that no edge is crossed more than once) admits an embedding in a book with constant number of pages. To the best of our knowledge, the best non-trivial previous upper-bound is $O(\sqrt{n})$, where $n$ is the number of vertices of the graph. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> Point-Set RAC Embeddings (PSRE). <s> It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not closed under taking minors. For fixed $g$ and $k$, we show that every $n$-vertex graph that can be embedded on a surface of genus $g$ with at most $k$ crossings per edge has stack-number $\mathcal{O}(\log n)$; this includes $k$-planar graphs. The previously best known bound for the stack-number of these families was $\mathcal{O}(\sqrt{n})$, except in the case of $1$-planar graphs. Analogous results are proved for map graphs that can be embedded on a surface of fixed genus. None of these families is closed under taking minors. The main ingredient in the proof of these results is a construction proving that $n$-vertex graphs that admit constant layered separators have $\mathcal{O}(\log n)$ stack-number. <s> BIB010
Given a set S of points in the plane and a graph G with n = |S | vertices, a Point-Set Embedding (PSE) Γ of G on S is a drawing of G such that the vertices are placed to the points of S through a one-to-one mapping, which can be given as part of the input (see, e.g., BIB003 ) or not (see, e.g., BIB004 ). Fink et al. studied Point-Set RAC Embeddings (PSREs) of graphs; that is, PSEs where the points of S belong to an n × n grid and no two points are horizontally or vertically aligned BIB005 . They concentrate on computing PSREs with few bends per edge, where bends must occupy grid points as for the vertices. Different algorithmic results and bounds on the number of bends per edge are given, also under the assumption that the edge segments are restricted to be on grid lines. Among their results, they prove that every graph with n vertices and m edges admits a PSRE on any n × n grid point set with at most three bends per edge in O ((n + m)  ) area, which also implies that every planar graph admits a RAC drawing with at most three bends per edge in quadratic area, thus improving a previous result BIB006 in terms of bends per edge (see Section 7.3). On the negative side, testing whether a graph admits a PSRE without bends is NP-hard BIB006 . Open problems. Although the study of planar book embeddings has a long tradition in graph drawing (see, e.g., BIB001  BIB002 ), the study of its beyond-planar counterpart is much more recent. The question can be studied by either considering k-page drawings with forbidden crossing configurations (see, e.g.,  ) or by focusing on k-page book embeddings of beyond-planar graphs (see, e.g., BIB008 BIB009 BIB010 ). For example, we mention the following two problems. Not all planar acyclic digraphs have a straight-line upward RAC drawing BIB007 , thus we ask: