A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <s> A Right Angle Crossing Graph (also called a RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A 1-planar graph is a graph that has a drawing where every edge is crossed at most once. This paper studies the combinatorial relationship between the family of RAC graphs and the family of 1-planar graphs. It is proved that: (1) all RAC graphs having maximal edge density belong to the intersection of the two families; and (2) there is no inclusion relationship between the two families. As a by-product of the proof technique, it is also shown that every RAC graph with maximal edge density is the union of two maximal planar graphs. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <s> IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossedi¾?at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graphi¾?G withi¾?n vertices, we present an On-time algorithm that computes a straight-line drawing ofi¾?G in quadratic area, and an $$On^3$$-time algorithm that computes a straight-line drawing ofi¾?G with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is $$\mathrm {NP}$$-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <s> We prove that if an $n$-vertex graph $G$ can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then $G$ has $O(n)$ edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal $1$-planar and fan-planar graphs. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <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> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <s> A graph is k-planar \((k \ge 1)\) if it can be drawn in the plane such that no edge is crossed \(k+1\) times or more. A graph is k-quasi-planar \((k \ge 2)\) if it can be drawn in the plane with no k pairwise crossing edges. The families of k-planar and k-quasi-planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for \(k \ge 3\), every k-planar graph is \((k+1)\)-quasi-planar. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <s> It is shown that every 2-planar graph is quasiplanar, that is, if a simple graph admits a drawing in the plane such that every edge is crossed at most twice, then it also admits a drawing in which no three edges pairwise cross. We further show that quasiplanarity is witnessed by a simple topological drawing, that is, any two edges cross at most once and adjacent edges do not cross. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <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> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <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> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> RELATIONSHIPS BETWEEN GRAPH FAMILIES <s> Abstract A drawing of a graph in the plane is 1-planar if each edge is crossed at most once, fan-crossing if each edge can only cross edges with a common endpoint, and fan-crossing free if no edge is crossed by two or more edges with a common endpoint. In an outer drawing all vertices must be placed in the outer face. A graph is (outer-) 1-planar (fan-crossing, fan-crossing free) if it admits a respective drawing. Fan-crossing and fan-crossing free are complementary properties. Hence, a drawing is 1-planar if and only if it is fan-crossing and fan-crossing free. We show that there are graphs that are simultaneously (outer-) fan-crossing and fan-crossing free but not (outer-) 1-planar. <s> BIB009
Some families of beyond-planar graphs have similar edge densities or exhibit similar structural and topological properties. In these cases, it is natural to ask whether they have some inclusion relationships. In what follows, we survey the main results concerning this research direction. RAC graphs and 1-planar graphs. One of the most studied problems on the subject is the relationship between RAC graphs and 1-planar graphs. Recall that straight-line RAC drawings have at most 4n − 10 edges, while topological (respectively, geometric) 1-planar graphs have at most 4n − 8 edges (respectively, 4n − 9). This immediately implies that optimal 1-planar graphs are not straight-line RAC. Eades and Liotta proved in fact that these two families are in general incomparable, and they provide a series of interesting results about their relationships BIB001 . They exhibit an infinite subfamily of straight-line RAC graphs with n ≥ 85 vertices that are not 1-planar (see, e.g., Figure 5 (a)), and they show that there exist infinitely many 1-planar graphs with 4n − 10 edges that are not straight-line RAC (see, e.g., Figure 5 (b)). On the positive side, every optimal straight-line RAC graph is 1-planar (see, e.g., Figure 4(d) ). Brandenburg et al. study the RAC drawability of the 1-planar graphs with independent pairs of crossing edges (the IC-planar graphs) BIB002 . They show that every IC-planar graph has a straightline RAC drawing, while this is not true for the larger class of the NIC-planar graphs  . The incomparability of straight-line RAC graphs and 1-planar graphs, together with the fact that IC-planar graphs always admit a straight-line RAC drawing (which is also 1-planar), suggest two interesting questions: (i) What is the complexity of deciding whether a graph admits a drawing that is both 1-planar and straight-line RAC? (ii) Does every 1-planar graph admit a 1-planar drawing that is also RAC if we allow at most one bend per edge? These questions have been recently answered BIB004 : Question (i) is NP-hard, as already mentioned in Section 5 (see Table 3 ), while Question (ii) has a positive answer. Figure 5 (c) shows a 1-planar RAC drawing with at most one bend per edge of the graph in Figure 5 (b). Additional inclusion relationships between 1-planar and straight-line RAC drawings have been studied for constrained drawings, and they are summarized in Section 8. k-planar graphs and k-quasi planar graphs. Note that the tight bounds on the edge density of 3-planar and 3-quasi planar graphs imply the existence of 3-quasi planar graphs that are not 3-planar. On the other hand, for k ≥ 1, every k-planar graph is clearly (k + 2)-quasi planar. These two observations have motivated recent work on the relationship between k-planar graphs and kquasi planar graphs BIB005 : For k ≥ 3, every k-planar graph is (k + 1)-quasi planar. The proof of this result is based on a rerouting argument that starts from a k-planar drawing and resolves all possible bundles of k + 1 pairwise crossing edges. The drawing produced by this technique is (k + 1)-quasi planar, but it may not be k-planar anymore. This result has been later extended to the case k = 2 BIB006 . Thus, every k-planar graph is (k + 1)-quasi planar, for k ≥ 2. k-planar graphs, fan-planar graphs, fan-crossing-free graphs. Since optimal fan-planar graphs have the same density as optimal 2-planar graphs (optimal n-vertex graphs have 5n − 10 edges for these two families), Binucci et al. study the relationship between fan-planar and k-planar graphs  . They prove that these two families are incomparable. On the one hand, they show that for any k ≥ 2 there exists a fan-planar graph that is not k-planar; the proof uses a complete 3-partite graph K 1,3,h , where the index h depends on k; this graph is clearly fan-planar but any of its drawings contains too many crossings to be k-planar. On the other hand, they exhibit 2-planar graphs that are not fan-planar. Recently, Brandenburg proved that there are graphs that are both fan-planar and fan-crossing-free but not 1-planar BIB009 . k-gap planar graphs, k-planar graphs, k-quasi planar graphs. Bae et al. studied the relationship between k-gap planar graphs and both k-planar and k-quasi planar graphs BIB007 . By using Hall's theorem, they prove that for every k ≥ 1 all 2k-planar graphs are k-gap planar. On the other hand, for every fixed k ≥ 1, there exists a 1-gap planar graph that is not k-planar. Similarly, by using a counting argument on the number of crossings, they prove that all k-gap planar graphs are 2k + 2-quasi planar, while for all k ≥ 1, they exhibit a quasi planar graph that is not k-gap planar. Planarly connected graphs, 1-planar graphs, fan-planar graphs. Ackerman motivates the study of planarly connected graphs with the fact that both maximally dense 1-planar graphs and maximally dense fan-planar graphs are planarly connected BIB003 . For 1-planar graphs, the high-level idea is to consider a drawing with the minimum number of crossings of a maximally dense graph; in such a drawing, for every pair of crossing edges there is a crossing-free edge that connects their endpoints, as otherwise one could contradict either the fact that the drawing is crossing minimal or the fact that the graph is maximally dense. The idea for fan-planar graphs is similar. Most of the intersection relationships between different families of beyond-planar graph families are summarized in Table 4 . Each family in a row (respectively, column) is represented by a thin (respectively, thick) circle. Each cell reports the relationship between the corresponding row and column using the common Venn diagram notation. Note that some relationships immediately derive from the definitions. For example, a fan-planar drawing is always k-quasi planar (for each k ≥ 3) because three mutually crossing edges imply that two independent edges are crossed by a third one. Open problems. Table 4 shows that some pairs of beyond-planar graph families have a non-empty intersection that is not an inclusion. In these cases, it is interesting to characterize the graphs that belong to both families. For example, there are 1-planar graphs that are not straight-line RAC, there are straight-line RAC graphs that are not 1-planar, all optimal straight-line RAC graphs are 1-planar, and all IC-planar graphs are straight-line RAC BIB002 BIB001 Other questions can be asked for those cells of Table 4 that show a proper inclusion between two families of beyond-planar graphs. For example, while every k-planar graph is (k + 1)-quasi planar BIB005 BIB006 and every optimal 3-planar graph is also 3-quasi planar BIB008 , the following questions on the combinatorial relationships between k-planarity and h-quasi planarity remain unanswered. Finally, the relationships between some pairs of beyond-planar graph families have not yet been studied. For example: Problem 10. What is the relationship between k-gap planar and fan-planar graphs, for k ≥ 1?