A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm used depth-first search and has O ( V ) time and space bounds, where V is the number of vertices in G . An ALGOL implementation of the algorithm succesfully tested graphs with as many as 900 vertices in less than 12 seconds. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We prove Wagner's conjecture, that for every infinite set of finite graphs, one of its members is isomorphic to a minor of another. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> AbstractWe consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum ::: independent set, minimum vertex cover, minimum dominating set and many others, admit polynomial time approximation schemes when restricted to such graphs. This extends previous results by Baker and Eppstein to a much broader class of graphs. We also prove that for the considered class of graphs, there are balanced separators of size $O(\sqrt{n})$ where n is a number of vertices in the graph. On the negative side, we prove that it is intractable to recognize the graphs embeddable in the plane with at most one crossing per edge. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We show that for every fixed k, there is a linear time algorithm that decides whether or not a given graph has crossing number at most k, and if this is the case, computes a drawing of the graph in the plane with at most k crossings. This answers the question posed by Grohe (STOC'01 and JCSS 2004). Our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan lin1, which determines if a given graph is planar in linear time. Our algorithm can also be compared to the algorithms by Mohar (STOC'96 and Siam J. Discrete Math 2001), for testing the embeddability of an input graph in a fixed surface. For each surface s, Mohar describes an algorithm which yields either an embedding of G in s or a minor of G which is not embeddable in s and is minimal with this property. The same approach allows us to obtain linear time algorithms for the same question for a variety of other crossing numbers. We can also determine in linear time if an input graph can be made planar by the deletion of k edges (for fixed k). <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> A nonplanar graph G is near-planar if it contains an edge e such that G−e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hliněný and Salazar (Graph Drawing GD’06). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Ne\v{s}et\v{r}il and Ossona de Mendez. These classes are defined by the fact that the maximum average degree of a shallow minor of a graph in the class is bounded by a function of the depth of the shallow minor. Several linear-time algorithms are known for bounded expansion classes (such as subgraph isomorphism testing), and they allow restricted homomorphism dualities, amongst other desirable properties. In this paper we establish two new characterisations of bounded expansion classes, one in terms of so-called topological parameters, the other in terms of controlling dense parts. The latter characterisation is then used to show that the notion of bounded expansion is compatible with Erd\"os-R\'enyi model of random graphs with constant average degree. In particular, we prove that for every fixed $d>0$, there exists a class with bounded expansion, such that a random graph of order $n$ and edge probability $d/n$ asymptotically almost surely belongs to the class. We then present several new examples of classes with bounded expansion that do not exclude some topological minor, and appear naturally in the context of graph drawing or graph colouring. In particular, we prove that the following classes have bounded expansion: graphs that can be drawn in the plane with a bounded number of crossings per edge, graphs with bounded stack number, graphs with bounded queue number, and graphs with bounded non-repetitive chromatic number. We also prove that graphs with `linear' crossing number are contained in a topologically-closed class, while graphs with bounded crossing number are contained in a minor-closed class. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We show that for every fixed $k$, there is a linear time algorithm that decides whether or not a given graph has a vertex set $X$ of order at most $k$ such that $G-X$ is planar (we call this class of graphs {\it $k$-apex}), and if this is the case, computes a drawing of the graph in the plane after deleting at most $k$ vertices. In fact, in this case, we shall determine the minimum value $l \leq k$such that after deleting some $l$ vertices, the resulting graph is planar. If this is not the case, then the algorithm gives rise to a minor which is not $k$-apex and is minimal with this property. This answers the question posed by Cabello and Mohar in 2005, and by Kawarabayashi and Reed (STOC'07), respectively. Note that the case $k=0$ is the planarity case. Thus our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan (J. ACM 1974), which determines if a given graph is planar in linear time. Our algorithm can be also compared to the algorithms by Mohar (STOC'96 and Siam J. Discrete Math 2001) for testing the embeddability of an input graph in a fixed surface in linear time, by Kawarabayashi and Mohar (STOC'08) for testing polyhedral embeddability of an input graph in a fixed surface in linear time, and by Kawarabayashi and Reed (STOC'07) for testing the fixed crossing number in linear time. Note that deciding the genus of $k$-apex graphs is NP-complete, even for $k=1$, as shown by Mohar. Thus $k$-apex graphs are very different from bounded genus graphs in a sense.%\cite{Mo-apex}.In addition, for any fixed $c, k$, we apply our algorithm to obtain a linear time approximation scheme for weighted TSP, and for minimum weighted $c$-edge-connected submultigraph, respectively, for $k$-apex graphs. (In this case, an embedding of a $k$-apex graph is not given in the input). The first result generalizes the recent planar result by Klein (FOCS'05), while the second result generalizes Czumaj et al. (SODA'04). We also extend several optimization results for planar graphs by Baker (J. ACM. 1994) and others to $k$-apex graphs. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We show that, for any given non-spherical orientable closed surface F^2, there exists an optimal 1-planar graph which can be embedded on F^2 as a triangulation. On the other hand, we prove that there does not exist any such graph for the nonorientable closed surfaces of genus at most 3. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> A Right Angle Crossing drawing (RAC drawing for short) of a graph is such that edges can only cross at an angle of @p2. In this paper we provide a characterization of the complete bipartite graphs that admit a straight-line RAC drawing. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non-1-planar graph $G$ is minimal if the graph $G-e$ is 1-planar for every edge $e$ of $G$. We construct two infinite families of minimal non-1-planar graphs and show that for every integer $n > 62$, there are at least $2^{(n-54)/4}$ nonisomorphic minimal non-1-planar graphs of order $n$. It is also proved that testing 1-planarity is NP-complete. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction $\delta$ of the edge lengths ($\delta$-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. ::: We show that, for a fixed stub--edge length ratio $\delta$, not all graphs have a $\delta$-SHPED. Specifically, we show that $K_{241}$ does not have a 1/4-SHPED, while bandwidth-$k$ graphs always have a $\Theta(1/\sqrt{k})$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively. This is a strengthening of a recent result of Didimo et al. <s> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known to be NP-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains NP-complete for graphs of bounded bandwidth, pathwidth, or treewidth. <s> BIB013 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. ::: ::: In this paper, we present a polynomial-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-hard, for the case where the rotation system i.e., the cyclic order of the edges around each vertex is given. <s> BIB014 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. 1-planarity is known NP-hard, even for graphs of bounded bandwidth, pathwidth, or treewidth, and for near-planar graphs in which an edge is added to a planar graph. On the other hand, there is a linear time 1-planarity testing algorithm for maximal 1-planar graphs with a given rotation system. In this work, we show that 1-planarity remains NP-hard even for 3-connected graphs with (or without) a rotation system. Moreover, the crossing number problem remains NP-hard for 3-connected 1-planar graphs with (or without) a rotation system. <s> BIB015 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> A graph with n vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of \(4n-8\) edges. We show that optimal 1-planar graphs can be recognized in linear time. Our algorithm implements a graph reduction system with two rules, which can be used to reduce every optimal 1-planar graph to an irreducible extended wheel graph. The graph reduction system is non-deterministic, constraint, and non-confluent. <s> BIB016 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We prove that triangulated IC-planar and NIC-planar graphs can be recognized in cubic time. ::: A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. A drawing is IC-planar if, in addition, each vertex is incident to at most one crossing edge and NIC-planar if two pairs of crossing edges share at most one vertex. In a triangulated drawing each face is a triangle. In consequence, planar-maximal and maximal IC-planar and NIC-planar graphs can be recognized in O(n^5) time and maximum and optimal ones in O(n^3) time. In contrast, recognizing 3-connected IC-planar and NIC-planar graphs is NP-complete, even if the graphs are given with a rotation system which describes the cyclic ordering of the edges at each vertex. Our results complement similar ones for 1-planar graphs. <s> BIB017 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <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> BIB018 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> A graph is $k$-planar if it can be drawn in the plane such that no edge is crossed more than $k$ times. While for $k=1$, optimal $1$-planar graphs, i.e., those with $n$ vertices and exactly $4n-8$ edges, have been completely characterized, this has not been the case for $k \geq 2$. For $k=2,3$ and $4$, upper bounds on the edge density have been developed for the case of simple graphs by Pach and Toth, Pach et al. and Ackerman, which have been used to improve the well-known "Crossing Lemma". Recently, we proved that these bounds also apply to non-simple $2$- and $3$-planar graphs without homotopic parallel edges and self-loops. ::: In this paper, we completely characterize optimal $2$- and $3$-planar graphs, i.e., those that achieve the aforementioned upper bounds. We prove that they have a remarkably simple regular structure, although they might be non-simple. The new characterization allows us to develop notable insights concerning new inclusion relationships with other graph classes. <s> BIB019 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> Abstract The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry. This annotated bibliography aims to provide a guiding reference to researchers who want to have an overview of the large body of literature about 1-planar graphs. It reviews the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. As an additional contribution, we offer a list of open problems on 1-planar graphs. <s> BIB020 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We introduce the family of k-gap-planar graphs for \(k \ge 0\), i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition finds motivation in edge casing, as a \(k\)-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs. <s> BIB021 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> Abstract A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A k-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most k bends and edges cross only at right angles. A graph is k-bend RAC if it has a k -bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing) . The relationships between 1-planar and k -bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: ( i ) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? ( i i ) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs. <s> BIB022 </s> A Survey on Graph Drawing Beyond Planarity <s> RECOGNITION <s> We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. <s> BIB023
Given a graph G and a family F of beyond-planar graphs, the recognition problem studies the complexity of deciding whether a graph G belongs to F . As we have seen in Section 4, several families of beyond-planar graphs are sparse, and this may suggest a correspondence with planar graphs, which can be recognized in linear time BIB001 . Unfortunately, this is not the case, and for most of the studied beyond-planar graph families, the recognition problem is in fact hard. Recognizing 1-planar graphs is NP-complete in general BIB003 BIB010 , even if the skewness of the input graph is 1 BIB005 . The problem is, however, Fixed-Parameter Tractable (FPT) with respect to the vertex-cover number, the cyclomatic number, or the tree-depth of the input graph BIB013 . Recognizing 1-planar graphs remains NP-complete also when the input graph comes with a fixed rotation system, which must be preserved BIB015 . On the positive side, deciding whether a graph with n vertices is optimal 1-planar (i.e., it is 1-planar and has 4n − 8 edges) is O (n)-time solvable BIB016 ; the testing algorithm exploits a structural characterization of optimal 1-planar graphs BIB008 . Recently, a similar structural characterization has been proved for optimal 2-planar and optimal 3-planar graphs BIB019 , although the complexity of recognizing these graphs is still unknown. Polynomial time recognition algorithms are also known for other subfamilies of 1-planar graphs (see, e.g., BIB017 ). We refer the reader to the annotated bibliography by Kobourov et al. for further references BIB020 . It is worth remarking that several papers present interesting bounds of graph parameters for 1planar and k-planar graphs, which shed some light on the structure of these graphs and thus may be of interest for the design of FPT recognition algorithms. For example, k-planar graphs on n vertices have O (log n) book thickness BIB018 , O ( √ kn) treewidth and O (k ) layered treewidth  , and bounded expansion BIB006 (see BIB020 for more results). Recognizing skewness-k graphs is NP-complete in the general case  , but the problem can be solved in O (n) time for any fixed value of k (i.e., it is FPT with parameter k) BIB004 . The set of 1-apex graphs is closed under the operation of taking minors  , hence these graphs have a forbidden graph characterization by the Robertson-Seymour theorem BIB002 . However, the set of obstructions for these graphs has only been partially discovered  . Recognizing n-vertex k-apex graphs is NP-complete  , but there is an O (n)-time algorithm if k is a fixed constant BIB007 . Recognizing fan-planar graphs is NP-complete  , even for a fixed rotation system BIB014 . The same holds for 1-gap-planar graphs BIB021 . Recognizing straight-line RAC drawable graphs is NP-hard in general  , but can be solved in linear time for complete bipartite graphs BIB009 . Even the more restricted problem of deciding whether a graph admits a straight-line RAC drawing with at most one crossing per edge is NPhard BIB022 . It is, however, unknown if recognizing straight-line RAC (1-planar) drawable graphs BIB021 belongs to NP because the complexity of deciding whether an embedded graph has an embeddingpreserving straight-line RAC (1-planar) drawing is unknown. On the other hand, every 1-plane graph admits a 1-bend RAC drawing with at most one crossing per edge BIB022 BIB023 (see also Section 7) . Concerning α-SHPEDs, there are necessary or sufficient conditions for their existence, although the complexity of the recognition problem has not been established. If an n-vertex complete graph has a 1 4 -SHPED, then n < 165; also, if a graph has bandwidth k, it has a Θ( 1 k )-SHPED BIB011 . Similar bounds are given for complete bipartite graphs. The problem of maximizing the total stub length (or ink) to turn a geometric graph into a partial edge drawing that is symmetric but not necessarily homogeneous (the value of α may not be the same for all the edges) is NP-hard but becomes polynomial-time solvable for geometric 2-planar graphs BIB011 . Table 3 summarizes the results discussed in this section. Open problems. As shown in Table 3 , the general recognition problem is NP-hard for most of the considered families. However, only a few papers deal with FPT algorithms, and no other types of exponential-time recognition algorithms have been considered. This motivates the following. It is know that every graph has a RAC drawing with at most three bends per edge  and that it has O (n) edges if either one bend or two bends per edge are allowed  BIB012 (see Section 7) . Recognizing straight-line RAC graphs is NP-hard  , but the following question is still open. A Survey on Graph Drawing Beyond Planarity 4:13 Problem 6. What is the complexity of recognizing k-bend RAC drawable graphs, for k ∈ {1, 2}? A characterization of the graphs that admit an α-SHPED is unknown.