A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> We consider graphs drawn in the plane such that every edge crosses at most one other edge. We characterize, in terms of two forbidden sub-configurations, which of these graphs are equivalent to drawings such that all edges are straight line segments. As a consequence we obtain a complete characterization of the pairs of dual graphs that can be represented as geometric dual graphs such that all edges except one are straight line segments. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> Every three-connected planar graph with n vertices has a drawing on an O(n(2)) x O(n(2)) grid in which all faces are strictly convex polygons. These drawings are obtained by perturbing (not strictly) convex drawings on O(n) x O(n) grids. Tighter bounds are obtained when the faces have fewer sides. In the proof, we derive an explicit lower bound on the number of primitive vectors in a triangle. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> In this paper we study non-planar drawings of graphs, and study trade-offs between the crossing resolution (i.e., the minimum angle formed by two crossing segments), the curve complexity (i.e., maximum number of bends per edge), the total number of bends, and the area. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> We consider graphs that admit polyline drawings where all crossings occur at the same angle α ∈ (0, π/2). We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has O(n) edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <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> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> A plane graph is a graph embedded in a plane without edge crossings. Fary’s theorem states that every plane graph can be drawn as a straight-line drawing, preserving the embedding of the plane graph. In this paper, we extend Fary’s theorem to a class of non-planar graphs. More specifically, we study the problem of drawing 1-plane graphs with straight-line edges. A 1-plane graph is a graph embedded in a plane with at most one crossing per edge. We give a characterisation of those 1-plane graphs that admit a straight-line drawing. The proof of the characterisation consists of a linear time testing algorithm and a drawing algorithm. Further, we show that there are 1-plane graphs for which every straight-line drawing has exponential area. To the best of our knowledge, this is the first result to extend Fary’s theorem to non-planar graphs. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <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> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> We consider graphs that admit polyline drawings where all crossings occur at the same angle $\alpha\in (0,\frac{\pi}{2}]$. We prove that every graph on $n$ vertices that admits such a polyline drawing with at most two bends per edge has $O(n)$ edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1-planar graphs do not admit straight-line drawings. We show that every 3-connected 1-planar graph has a straight-line drawing on an integer grid of quadratic size, with the exception of a single edge on the outer face that has one bend. The drawing can be computed in linear time from any given 1-planar embedding of the graph. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> Thomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335-341, 1988]. In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Re-embedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <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> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <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> BIB013 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <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> BIB014 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> While orthogonal drawings have a long history, smooth orthogonal drawings have been introduced only recently. So far, only planar drawings or drawings with an arbitrary number of crossings per edge have been studied. Recently, a lot of research effort in graph drawing has been directed towards the study of beyond-planar graphs such as 1-planar graphs, which admit a drawing where each edge is crossed at most once. In this paper, we consider graphs with a fixed embedding. For 1-planar graphs, we present algorithms that yield orthogonal drawings with optimal curve complexity and smooth orthogonal drawings with small curve complexity. For the subclass of outer-1-planar graphs, which can be drawn such that all vertices lie on the outer face, we achieve optimal curve complexity for both, orthogonal and smooth orthogonal drawings. <s> BIB015 </s> A Survey on Graph Drawing Beyond Planarity <s> Edge Complexity <s> We show that the 1-planar slope number of 3-connected cubic 1-planar graphs is at most 4 when edges are drawn as polygonal curves with at most 1 bend each. This bound is obtained by drawings whose vertex and crossing resolution is at least $\pi/4$. On the other hand, if the embedding is fixed, then there is a 3-connected cubic 1-planar graph that needs 3 slopes when drawn with at most 1 bend per edge. We also show that 2 slopes always suffice for 1-planar drawings of subcubic 1-planar graphs with at most 2 bends per edge. This bound is obtained with vertex resolution $\pi/2$ and the drawing is RAC (crossing resolution $\pi/2$). Finally, we prove lower bounds for the slope number of straight-line 1-planar drawings in terms of number of vertices and maximum degree. <s> BIB016
Stretchability. The famous Fáry's theorem states that every plane graph is stretchable; that is, it has an embedding-preserving straight-line drawing  (this result was also independently proved by Wagner  and Stein  ). So far, little effort has been made to extend this result to beyond-planar graphs. In 1988, Thomassen initiated the study of the stretchability problem for 1-plane graphs BIB001 . He proved that, differently from plane graphs, a 1-plane graph admits an embedding-preserving straight-line drawing if and only if it contains neither B-configurations nor W-configurations as subgraphs BIB001 (see and Nagamochi have studied the stretchability problem of 1-plane graphs in a more relaxed setting BIB011 . They describe a linear-time algorithm that tests whether a 1-plane graph is stretchable assuming that the rotation system and the external face of the graph can change, while requiring the pairs of crossing edges to stay the same. Eades et al. study the stretchabilty problem for skewness-1 graphs BIB010 . They characterize the maximal topological skewness-1 graphs that are stretchable and give a linear-time testing and drawing algorithm based on this characterization. Table 5 summarizes the aforementioned results. Polyline drawings. As reported in the paragraph about stretchability, the class of 1-plane graphs admitting a straight-line drawing has been characterized BIB001 , and there exist 1-plane graphs such that every embedding-preserving straight-line drawing requires an exponential area BIB006 . Later, Alam et al. proved that every 3-connected 1-planar graph admits a 1-planar embedding that can be realized as a straight-line drawing except for at most one edge BIB009 ; this drawing has quadratic area. On the other hand, it is obvious that every 1-plane graph admits a 1-bend drawing as it suffices to replace each crossing with a dummy vertex and compute a straight-line drawing of the resulting plane graph (possible overlaps of bend points can be removed by slight perturbations). Furthermore, it is not difficult to see that every 1-plane graph can be drawn with at most two bends per edge in O (n 4 ) area (refer to Figure 7 ). Replace each crossing with a dummy face of degree four; augment the resulting plane graph to be 3-connected so that no edge is inserted in the dummy faces; compute a straight-line planar drawing such that all the faces are strictly convex and the area of the drawing is O (n 2 ) × O (n 2 ) BIB002 ; replace all dummy vertices with bend points, remove all dummy edges, and reinsert the crossings. Chaplick, Lipp, Wolff, and Zink recently proved that every n-vertex 1-plane graph actually admits an embedding-preserving 1-bend RAC drawing; if two bends per edge are allowed, a RAC drawing can be computed in O (n 6 ) area BIB014 . They also prove that every NIC-plane graph admits an embedding-preserving 1-bend RAC drawing in quadratic area. We remark that the existence of 1-bend 1-planar RAC drawings for every 1-plane graph was already known BIB012 , but only assuming that the drawing algorithm can change the 1planar embedding of the input graph. We also remark that for a simple family of 1-plane graphs, called kite-triangulations, an Ω(n 3 ) area lower bound for embedding-preserving straight-line RAC drawings is established BIB005 . A kite-triangulation is obtained by augmenting a plane triangulation with edges inside pairs of adjacent faces. Additional results concerned with other restricted classes of 1-planar graphs, such as the IC-planar graphs, are surveyed in Kobourov et al. BIB013 . In recent papers, Argyriou et al. BIB015 and Kindermann et al. BIB016 study 1-planar graphs with small vertex degree. Argyriou et al. focus on orthogonal drawings (i.e., drawings where the edges are polylines with horizontal and vertical segments) and smooth orthogonal drawings (where circular arcs are also allowed) of 1-planar graphs. In particular, they show that all 1-planar graphs with vertex degree at most four have an orthogonal drawing with at most three bends per edge and a smooth orthogonal drawing with at most two bends per edge. Kindermann et al. prove that every 3-connected 1-planar graph with vertex degree at most three can be drawn with at most one bend per edge by using at most four different slopes for the edge segments and such that the minimum angle between two adjacent edges or between two crossing edges is at least π /4. They also prove that every 1-planar graph with vertex degree at most three admits a 1-planar drawing with at most two bends per edge by using two orthogonal slopes (hence obtaining a RAC drawing). The edge complexity of RAC drawings has also been studied regardless of the number of crossings per edge. Every n-vertex graph has a 3-bend RAC drawing in O (n 4 ) area  , while 1-bend and 2-bend RAC drawable graphs have at most 5.5n − 11 edges  or 74.2n edges BIB007 , respectively. If we allow up to four bends per edge, every graph can be drawn RAC in O (n 3 ) area BIB003 . For graphs with bounded vertex degree, we have the following results BIB005 : (i) every graph with vertex degree at most three has a 1-bend RAC drawing; (ii) every graph with vertex degree at most six has a 2-bend RAC drawing. In both (i) and (ii), the drawing is computed in O (n) time and has O (n 2 ) area. Concerning ACEα drawings with one or two bends per edge, it is proved that they have at most 27n edges and 385n edges, respectively BIB004 BIB008 . On the other hand, every graph admits an ACLα drawing with one bend per edge in O (n 2 ) area BIB003 . Table 6 summarizes the main results concerning tradeoffs between the number of bends per edge and the area requirement of beyond-planar drawings.