A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> The paper describes a method for laying out networks by computer so that the number of crossings between the network connections is close to a minimum. The problem is relevant to the design of printed circuits, where special wiring arrangements have to be made when crossings occur. The network is expressed in the form of a permutation, which is convenient for manipulation, by deforming the network so that the node points lie on a straight line with the connections drawn as semicircles above an below the node line. Locally optimal networks are defined so that no gain can result from moving an individual node to a new position, and a 2-stage method of construction is proposed. The formulas used to calculate the number of crossings consist primarily of summations, so that the procedure is quickly performed on a computer. The method has been tested on some trial networks for which the minimum number of crossings is known, and it has also been compared with Monte Carlo methods on random networks. The results are encouraging in all cases. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> Two kinds of new methods are developed to obtain effective representations of hierarchies automatically: theoretical and heuristic methods. The methods determine the positions of vertices in two steps. First the order of the vertices in each level is determined to reduce the number of crossings of edges. Then horizontal positions of the vertices are determined to improve further the readability of drawings. The theoretical methods are useful in recognizing the nature of the problem, and the heuristic methods make it possible to enlarge the size of hierarchies with which we can deal. Performance tests of the heuristic methods and several applications are presented. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> The k-SAT problem is to determine if a given k-CNF has a satisfying assignment. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k?3. Here exponential time means 2?n for some ?>0. In this paper, assuming that, for k?3, k-SAT requires exponential time complexity, we show that the complexity of k-SAT increases as k increases. More precisely, for k?3, define sk=inf{?:there exists 2?n algorithm for solving k-SAT}. Define ETH (Exponential-Time Hypothesis) for k-SAT as follows: for k?3, sk>0. In this paper, we show that sk is increasing infinitely often assuming ETH for k-SAT. Let s∞ be the limit of sk. We will in fact show that sk?(1?d/k)s∞ for some constant d>0. We prove this result by bringing together the ideas of critical clauses and the Sparsification Lemma to reduce the satisfiability of a k-CNF to the satisfiability of a disjunction of 2?nk?-CNFs in fewer variables for some k??k and arbitrarily small ?>0. We also show that such a disjunction can be computed in time 2?n for arbitrarily small ?>0. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> This paper introduces a new visualization method, the arc diagram, which is capable of representing complex patterns of repetition in string data. Arc diagrams improve over previous methods such as dotplots because they scale efficiently for strings that contain many instances of the same subsequence. This paper describes design and implementation issues related to arc diagrams and shows how they may be applied to visualize such diverse data as music, text, and compiled code. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> Note: Professor Pach's number: [172]; 2nd edition Reference DCG-CHAPTER-2008-027 Record created on 2008-11-18, modified on 2017-05-12 <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed “barycenter” heuristic for this problem is analyzed. An alternative method, the “median” heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> A \emphk-stack layout (respectively, \emphk-queuelayout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. A \emphk-track layout of a graph consists of a vertex k-colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The \emphstack-number (respectively, \emphqueue-number, \emphtrack-number) of a graph G, denoted by sn(G) (qn(G), tn(G)), is the minimum k such that G has a k-stack (k-queue, k-track) layout.\par This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3-stack subdivision. The best known upper bound on the number of division vertices per edge in a 3-stack subdivision of an n-vertex graph G is improved from O(log n) to O(log min\sn(G),qn(G)\). This result reduces the question of whether queue-number is bounded by stack-number to whether 3-stack graphs have bounded queue number.\par It is proved that every graph has a 2-queue subdivision, a 4-track subdivision, and a mixed 1-stack 1-queue subdivision. All these values are optimal for every non-planar graph. In addition, we characterise those graphs with k-stack, k-queue, and k-track subdivisions, for all values of k. The number of division vertices per edge in the case of 2-queue and 4-track subdivisions, namely O(log qn(G)), is optimal to within a constant factor, for every graph G. \par Applications to 3D polyline grid drawings are presented. For example, it is proved that every graph G has a 3D polyline grid drawing with the vertices on a rectangular prism, and with O(log qn(G)) bends per edge. Finally, we establish a tight relationship between queue layouts and so-called 2-track thickness of bipartite graphs. \par <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> A 2-layer drawing represents a bipartite graph where each vertex is a point on one of two parallel lines, no two vertices on the same line are adjacent, and the edges are straight-line segments. In this paper we study 2-layer drawings where any two crossing edges meet at right angle. We characterize the graphs that admit this type of drawing, provide linear-time testing and embedding algorithms, and present a polynomial-time crossing minimization technique. Also, for a given graph G and a constant k, we prove that it is \(\mathcal{NP}\)-complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> There is strong empirical evidence that human perception of a graph drawing is negatively correlated with the number of edge crossings. However, recent experiments show that one can reduce the negative effect by ensuring that the edges that cross do so at large angles. These experiments have motivated a number of mathematical and algorithmic studies of “right angle crossing (RAC)” drawings of graphs, where the edges cross each other perpendicularly. In this paper we give an algorithm for constructing RAC drawings of “outer-1-plane” graphs, that is, topological graphs in which each vertex appears on the outer face, and each edge crosses at most one other edge. The drawing algorithm preserves the embedding of the input graph. This is one of the few algorithms available to construct RAC drawings. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> A 1-planar drawing of a graph is such that each edge is crossed at most once. In 1997, Pach and Toth showed that any 1-planar drawing with n vertices has at most 4n-8 edges and that this bound is tight for n>=12. We show that, in fact, 1-planar drawings with n vertices have at most 4n-9 edges, if we require that the edges are straight-line segments. We also prove that this bound is tight for infinitely many values of n>=8. Furthermore, we investigate the density of 1-planar straight-line drawings with additional constraints on the vertex positions. We show that 1-planar drawings of bipartite graphs whose vertices lie on two distinct horizontal layers have at most 1.5n-2 edges, and we prove that 1-planar drawings such that all vertices lie on a circumference have at most 2.5n-4 edges; both these bounds are also tight. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists. <s> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments. <s> BIB013 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <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> 2-layer drawings. <s> A 2-page drawing of a graph is such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line. If all edges are in the same half-plane, the drawing is called a 1-page drawing. We want to compute 1-page and 2-page drawings of planar graphs such that the number of crossings per edge does not depend on the number of the vertices. We show that for any constant k, there exist planar graphs that require more than k crossings per edge in either a 1-page or a 2-page drawing. We then prove that if the vertex degree is bounded by \(\varDelta \), every planar 3-tree has a 2-page drawing with a number of crossings per edge that only depends on \(\varDelta \). Finally, we show a similar result for 1-page drawings of partial 2-trees. <s> BIB015 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <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> BIB016 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> A graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time, and specialize 1-planar graphs, whose recognition is $${NP}$$NP-hard. We explore o1p graphs. Our first main result is a linear-time algorithm that takes a graph as input and returns a positive or a negative witness for o1p. If a graph $$G$$G is o1p, then the algorithm computes an embedding and can augment $$G$$G to a maximal o1p graph. Otherwise, $$G$$G includes one of six minors, which is detected by the recognition algorithm. Secondly, we establish structural properties of o1p graphs. o1p graphs are planar and are subgraphs of planar graphs with a Hamiltonian cycle. They are neither closed under edge contraction nor under subdivision. Several important graph parameters, such as treewidth, colorability, stack number, and queue number, increase by one from outerplanar to o1p graphs. Every o1p graph of size $$n$$n has at most $$\frac{5}{2} n - 4$$52n-4 edges and there are maximal o1p graphs with $$\frac{11}{5} n - \frac{18}{5}$$115n-185 edges, and these bounds are tight. Finally, every o1p graph has a straight-line grid drawing in $$\fancyscript{O}(n^2)$$O(n2) area with all vertices in the outer face, a planar visibility representation in $$\fancyscript{O}(n \log n)$$O(nlogn) area, and a 3D straight-line drawing in linear volume, and these drawings can be constructed in linear time. <s> BIB017 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Unfortunately, testing the 1-planarity of a graph is known as NP-complete. ::: ::: This paper initiates the study of the problem of the testing 2-planarity of a graph, in particular, testing the "full-outer-2-planarity" of a graph. A graph is outer-2-planar, if it admits an outer-2-planar embedding, that is every vertex is on the outer boundary and no edge has more than two crossings. A graph is fully-outer-2-planar, if it admits a fully-outer-2-planar embedding, that is an outer-2-planar embedding such that no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and fully-outer-2-planar graphs, and prove that triconnected fully-outer-2-planar graphs have a constant number of fully-outer-2-planar embeddings. Based on these properties, we present linear-time algorithms for testing the fully-outer-2-planarity of a graph G, whose vertex-connectivity is 1, 2 or at least 3. The algorithm also produces a fully-outer-2-planar embedding of a graph, if it exists. Moreover, we show that every fully-outer-2-planar embedding admits a straight-line drawing. <s> BIB018 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <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> BIB019 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <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> BIB020 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> A common representational style for drawing graphs is the so-called circular drawings, where vertices are represented as points on a circle, and edges are represented as straight line segments. In such drawings, edges may cross; these edge crossings have a negative effect on human readability.Recent empirical research shows that increasing the angles of edge crossings reduces the negative effect of crossings on human readability. This result has motivated a number of recent investigations of right angle crossing graph drawings, where each crossing angle is π 2 .The main result of this paper is a characterization of graphs that admit a circular right angle crossing drawing. We present a linear-time algorithm for testing and constructing such a drawing of a graph, if it exists.Further, we give an upper bound on the number of edges in a circular right angle crossing drawing, and we note that the optimization problem of constructing circular drawings with large angle crossings can be formulated as a quadratic programming problem. <s> BIB021 </s> A Survey on Graph Drawing Beyond Planarity <s> 2-layer drawings. <s> We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., convex drawings. We consider two families of graph classes with nice convex drawings: outer $k$-planar graphs, where each edge is crossed by at most $k$ other edges; and, outer $k$-quasi-planar graphs where no $k$ edges can mutually cross. We show that the outer $k$-planar graphs are $(\lfloor\sqrt{4k+1}\rfloor+1)$-degenerate, and consequently that every outer $k$-planar graph can be $(\lfloor\sqrt{4k+1}\rfloor+2)$-colored, and this bound is tight. We further show that every outer $k$-planar graph has a balanced separator of size $O(k)$. This implies that every outer $k$-planar graph has treewidth $O(k)$. For fixed $k$, these small balanced separators allow us to obtain a simple quasi-polynomial time algorithm to test whether a given graph is outer $k$-planar, i.e., none of these recognition problems are NP-complete unless ETH fails. For the outer $k$-quasi-planar graphs we prove that, unlike other beyond-planar graph classes, every edge-maximal $n$-vertex outer $k$-quasi planar graph has the same number of edges, namely $2(k-1)n - \binom{2k-1}{2}$. We also construct planar 3-trees that are not outer $3$-quasi-planar. Finally, we restrict outer $k$-planar and outer $k$-quasi-planar drawings to \emph{closed} drawings, where the vertex sequence on the boundary is a cycle in the graph. For each $k$, we express closed outer $k$-planarity and \emph{closed outer $k$-quasi-planarity} in extended monadic second-order logic. Thus, closed outer $k$-planarity is linear-time testable by Courcelle's Theorem. <s> BIB022
In the beyond planarity context, straight-line 2-layer drawings have been investigated for RAC, 1-planar, and fan-planar graphs in terms of both edge density and recognition. In a 2-layer drawing, the vertices are distributed along two horizontal layers, and vertices of the same layer cannot be adjacent. Thus, the graph is necessarily bipartite. The study of 2-layer drawings has two main motivations: (i) They are a natural way to visually convey bipartite graphs; (ii) algorithms that compute 2-layer drawings are building blocks of the popular Sugiyama's framework BIB002 used to draw graphs on multiple horizontal layers. Characterizations for those graphs that admit either 2-layer RAC drawings BIB009 , or 2-layer 1planar drawings BIB011 , or 2-layer fan-planar drawings  are known; all of them can be regarded as generalizations of caterpillars, the class of 2-layer planar drawable graphs  . The upper bounds on the edge density of these graph families are reported in Table 9 . In particular, the optimal 2-layer 1-planar graphs coincide with the optimal 2-layer RAC graphs and have 1.5n − 2 edges, where n is the number of vertices of the graph. They are called ladders and consist of two paths of the same length u 1 , u 2 , . . . ,u n 2 and v 1 , v 2 , . . . ,v n 2 , plus the edges (u i , v i ), (i = 1, 2, . . . , n 2 ); see Figures 8(a) and 8(b). A maximal 2-layer fan-planar graph is called a snake and is obtained from an outerplane ladder by adding, inside each internal face, an arbitrary number (possibly none) of paths of length two joining a pair of non-adjacent vertices of the face. Intuitively, a snake is a bipartite planar graph composed of a chain of complete bipartite graphs K 2,h ; see Figure 8 (c). The family of optimal 2-layer fan-planar graphs on n vertices includes K 2,n−2  . From the algorithmic point of view, there exist linear-time testing and drawing algorithms for 2-layer RAC graphs BIB009 and for 2-connected 2-layer fan-planar graphs  , while the complexity of recognizing 2-layer fan-planar graphs when the graph is only 1-connected is still open. For 2layer RAC graphs, it is also possible to compute, in O (n 2 log n) time, a 2-layer RAC drawing with minimum number of crossings BIB009 . We remark that the crossing minimization problem is a wellknown NP-complete problem in the general case, which remains hard even for 2-layer drawings without the restriction that crossing edges are orthogonal BIB007 . k-page drawings. Let be a line, called a spine. In a k-page drawing of a graph, each vertex is mapped to a distinct point of and each edge is drawn as a semicircle in one of k distinct half-planes incident to . Each of these half-planes is called a page. We recall that k-page drawings are among the oldest and more common graph drawing conventions, and they can be found with different names in the literature. For example, they are sometimes called linear layouts (see, e.g.,  ); also, a 2-page drawing is sometimes called a permutation representation (see, e.g., BIB001 ) or linear drawing (see, e.g.,  ), while a 1-page drawing is also called an arc diagram (see, e.g., BIB004 ). If no two disjoint edges cross, a k-page drawing is a k-page stack layout. The minimum value of k, such that a graph G has a k-page stack layout, is the stack number (or page number) of G. If no two disjoint edges nest, a k-page drawing is a k-page queue layout. The minimum value of k, such that a graph G has a k-page queue layout, is the queue number of G. Stack and queue layouts have been extensively studied for planar and regular graphs (see, e.g., the survey of Díaz, Petit, and Serna BIB005 ). In the context of beyond planarity, k-page drawings have been studied within two different research directions. On the one hand, the problem of computing k-page drawings with a limited number of crossings per edge has been studied; on the other hand, the problem of determining the stack and queue number of beyond-planar graphs has been studied. Concerning the first direction, Binucci et al. describe linear-time algorithms to compute 2-page drawings of planar 3-trees with at most 2Δ crossings per edge, where Δ is the maximum vertex-degree of the graph and 1-page drawings of partial 2-trees with at most Δ 2 crossings per edge BIB015 . In both cases, the authors show that the number of crossings per edge cannot be bounded by a constant. As for the second direction, Dujmovic and Frati proved a O (log n) upper bound on the stack number of k-planar graphs BIB019 , while for 1-planar graphs O (1) upper bounds are known BIB016 BIB020 . Furthermore, if the queue number of planar graphs is bounded (which is still unknown with the best upper bound being O (log n)  ), then the same is true for k-planar graphs BIB008 . Outer and convex drawings. Beyond-planar graphs that admit a layout in which all vertices lie on a circle enclosing the whole drawing or, more generally, on the external boundary of the drawing, can be regarded as generalizations of the outerplanar graphs. For any integer k > 0, a kplanar drawing with this property is an outer k-planar graph. Outer 1-planar graphs have at most 2.5n − 4 edges BIB017 BIB011 , which is a tight bound. They can be recognized in linear time BIB017 BIB012 and drawn in linear time, both as straight-line drawings with all vertices on the external face in O (n 2 ) area and as visibility representations in O (n log n) area BIB017 . Hong and Nagamochi extended the recognition problem to full outer 2-planar graphs (i.e., outer 2-planar graphs with no crossing on the external boundary BIB018 ). They prove that also this class of graphs can be recognized in linear time. Density and recognition results are described also for outer fan-planar graphs. They have at most 3n − 5 edges (see Table 9 ), but, in contrast to outer 1-planar graphs, the complexity of the recognition problem is not known in general, while it is linear-time solvable for maximal outer fan-planar graphs BIB014 . Table 9 reports other tight bounds for geometric beyond-planar graphs with all vertices in convex position, such as k-quasi planar graphs and fan-crossing-free graphs. Bounds for more specific families are listed in the geometric graph theory chapter of the Handbook of Discrete and Computational Geometry BIB006 . Note that the edge crossings in a geometric graph with vertices in convex position are the same as those of a 1-page drawing in which the order of the vertices along the spine equals the circular order of the vertices on the convex polygon. Several interesting properties of convex geometric k-planar and k-quasi planar graphs have been recently investigated BIB022 . Recall that a graph is d-degenerate if every subgraph has a vertex of degree at most d. It is shown that convex geometric k-planar graphs are ( √ 4k + 1 + 1)-degenerate and consequently ( √ 4k + 1 + 2)-colorable. Furthermore, they have a balanced separator of size at most 2k + 3, which allows the design of a quasi-polynomial time recognition algorithm for this class of graphs (i.e., the recognition problem is not NP-hard unless the Exponential Time Hypothesis [ETH] BIB003 fails). Convex geometric k-planar graphs in which all the vertices form a simple cycle can be recognized in linear time because they can be expressed in extended monadic secondorder logic and have bounded treewidth. In Chaplick et al. BIB022 , it is also proved that planar graphs and outer quasi planar graphs are incomparable classes under containment, while in Geneson et al. BIB013 it shown that semi-bar k-visibility graphs are outer (k + 2)-quasi planar. A characterization of the class of graphs that admit a RAC drawing in which all vertices lie on a circle, along with a linear-time testing and layout algorithm, is given in Dehkordi et al. BIB021 . Outer 1-planar graphs have been studied in combination with other types of constraints or beyond-planar graphs. Dehkordi and Eades show that every outer 1-planar graph admits an outer RAC drawing BIB010 . Di Giacomo et al. study how to draw outer 1-planar graphs with a small number of edge slopes  . They prove that every outer 1-planar graph admits an outer 1-planar straight-line drawing that uses O (Δ) different slopes, where Δ is the maximum vertex-degree of the graphs.