1 INTRODUCTION
In the mid-1980s, the early pioneers of graph drawing had the intuition that a drawing with too many edge crossings is harder to read than a drawing of the same graph with fewer edge crossings (see, e.g., [38, 39, 79, 211]). This intuition was later confirmed by a series of cognitive experimental studies (see, e.g., [200, 201, 225]). As a result, a large part of the existing literature on graph drawing showcases elegant algorithms and sophisticated data structures under the assumption that the input graph is planar (i.e., it admits a drawing without edge crossings). When the input graph is nonplanar, crossing minimization heuristics are used to insert a small number of dummy vertices corresponding to the edge crossings to obtain a planarization of the input graph. A crossing-free drawing of the planarization can be computed using one of the algorithms for planar graphs, and then the crossings are reinserted by removing the dummy vertices. This approach is commonly adopted and works well for graphs of relatively small size, up to a few hundred vertices and edges (see, e.g., [95, 166]). However, the technological advances of the past 20 years have generated torrents of relational data that are typically modeled as large graphs with thousands of vertices (or more). These graphs are often hard to visually analyze due, mainly, to their large size, which typically implies that a high number of edge crossings is unavoidable even by the most sophisticated planarization approaches. As a consequence, a strong consensus has developed that a new theory of nonplanar graph drawing is needed.
In this context, in the early 2000s, Mutzel ran an informal experiment with computer scientists at a Dagstuhl workshop where she presented two different drawings of the same bipartite graph: One has the minimum number of edge crossings, the second has $41\%$ more edge crossings, but it has a skewness of four, which means that all crossings can be removed by deleting four edges in the drawing. All computer scientists found the drawing with skewness four more readable than the one with fewer edge crossings. This is reported [185] as anecdotal evidence that the topological properties of the edge crossings may be more important than their number.
Besides the topological properties of the edge crossings, the impact of their geometric properties on the readability of a nonplanar drawing was evaluated in a pioneering sequence of user experiments performed in the graph drawing research lab at the University of Sydney. By means of an eye-tracking device, the experiments present statistical evidence that crossings significantly affect human understanding if they form acute angles, but if these angles vary in the range from about $\frac{\pi }{3}$ to $\frac{\pi }{2}$ they guarantee good readability properties [160, 162, 164].
These empirical experiences suggest that a new theory of nonplanar graph drawing can be developed under the assumption that not only the number of edge crossings but also their (topological and/or geometric) properties have an impact on the readability of a diagram. Hence, a natural step toward understanding nonplanar representations of graphs is to classify and study them in terms of forbidden crossing configurations. This is, in a broad sense, the aim and scope of the rapidly growing research area of graph drawing beyond planarity 1. Table 1 reports some examples of beyond-planar graphs with a description of their forbidden crossing configurations2.
 |
Overview and paper organization. The goal of this survey is to classify and describe prominent results and promising research directions in the fertile area of graph drawing beyond planarity. The survey addresses the following questions.
- What are the forbidden crossing configurations and the main research directions that have been studied so far?
- For each such direction, what are the main combinatorial results, and which algorithms have been designed, implemented, and experimentally evaluated?
- What are the most relevant open problems and the least explored research directions in this area?
To answer Question Q1, in Section 3 we define graph families that avoid forbidden crossing configurations, and we present a taxonomy of the main research directions in graph drawing beyond planarity. Sections 4–9 address Question Q2, using the taxonomy as a guideline to classify the main combinatorial and algorithmic results. At the end of each section, we address Question Q3 by discussing some relevant open problems. Basic definitions on graph drawing can be found in Section 2.
2 BASIC DEFINITIONS ON GRAPH DRAWING
Let $G=(V,E)$ be a (finite) graph. If not otherwise specified, we assume that $G$ may contain multiple edges but no self-loops. A drawing $\Gamma$ of $G$ maps each vertex $v \in V$ to a distinct point $p_v$ of the plane and each edge $(u,v) \in E$ to a simple Jordan arc with endpoints $p_u$ and $p_v$. In notation and terminology, we make no distinction between the vertices and edges of a graph and the points and arcs representing them, respectively. Two edges of $\Gamma$ cross if they have a point in common distinct from their endpoints; this point is a crossing. We assume that an edge does not contain a vertex other than its endpoints, no two edges meet tangentially, and no three edges share a crossing. $\Gamma$ is simple if any two edges intersect in at most one point, which is either a common endpoint or an interior point where the two edges properly cross. Thus, in a simple drawing, two adjacent edges do not cross and two nonadjacent edges cross at most once.
A drawing $\Gamma$ of $G$ divides the plane into topologically connected regions, called faces, separated by edges or fragments of edges. The infinite region is called the external face; the other regions are the internal faces. Note that the boundary of a face may contain both vertices of the graph and crossings. An embedding of $G$ is an equivalence class of drawings of $G$ under homeomorphism of the plane (i.e., is a class of drawings of $G$ that define the same set of [external and internal] faces). A graph with a fixed embedding is called an embedded graph. A drawing without crossings is planar. A graph is planar if it admits a planar drawing. A planar embedding is the embedding of a planar drawing. A graph with a fixed planar embedding is an embedded planar graph, or, briefly, a plane graph. An embedding of a graph $G$ defines, for each vertex $v$ and for each crossing $c$, the clockwise order of the edges incident to $v$ and to $c$. A rotation system of $G$ is a relaxation of an embedding of $G$ in which the clockwise order of the edges is fixed only for each vertex, while no information is given about which pairs of edges cross or their order of intersection. If $G$ is planar, a planar embedding of $G$ corresponds to a rotation system plus the choice of the external face (see Figure 1).
In a polyline drawing of a graph, each edge is a chain of segments; a bend is a point where two segments of the same edge meet. A $k$-bend drawing is a polyline drawing with at most $k$ bends per edge. A 0-bend drawing is also called a straight-line drawing.
We remark that, in the literature, a drawing of a graph is sometimes called a topological graph and a straight-line drawing is sometimes called a geometric graph (see, e.g., Chapter 10 in [217]). In the remainder of this article, we use the pair of terms “drawing” and “topological graph” and the pair “straight-line drawing” and “geometric graph” interchangeably.
3 FORBIDDEN CONFIGURATIONS AND MAIN RESEARCH DIRECTIONS
In Section 3.1, we survey forbidden crossing configurations; in Section 3.2, we present a taxonomy of the most explored research directions in graph drawing beyond planarity.
3.1 Graph Families
The beyond-planar graph families considered in this survey are defined as graphs that admit drawings without specific forbidden configurations (i.e., sets of edges that violate some desired topological or geometric property of the edge crossings). Table 1 provides a schematic illustration of some beyond-planar graph families, among the most studied. For each family $X$, we define what a drawing of type $X$ is. A graph belongs to family $X$ if it admits a drawing of type $X$. Definitions based on first-order logic formulas have been recently proposed for many of these types of drawings [64].
RAC drawings. A straight-line drawing, such that any two crossing edges form $\frac{\pi }{2}$ angles at their crossing point, is a straight-line RAC (Right Angle Crossings). RAC drawings are introduced in Didimo et al. [118], motivated by cognitive studies that suggest a positive correlation between large crossing angles and human understanding of graph visualizations [160, 162, 164], and by the common use of large angle crossings in handmade real-world diagrams, such as metro maps [203, 223]. RAC drawings with edge bends are also studied in the literature and will be discussed in this survey.
3.2 Main Research Directions
The tree of Figure 3 summarizes a taxonomy of the graph drawing beyond the planarity area. The first-level nodes identify the main research directions studied so far; we classify the results in the literature according to these directions. The intermediate nodes are refinements of the main directions. The leaves refer to the sections of the survey where the research directions are described in detail; most of these sections report one or more summarizing tables, which are also noted in the corresponding leaves. Here, we briefly describe the main research directions.
4 EDGE DENSITY
The problem of establishing the maximum number of edges in a given type of beyond-planar graph has been extensively studied in the literature. We recall some basic definitions needed to describe the main results in this research direction. Let $\mathcal {F}$ be a beyond-planar graph family and let $G$ be an $n$-vertex graph in $\mathcal {F}$. $G$ is maximal (in $\mathcal {F}$) if adding any edge to $G$ leads to a graph that is not in $\mathcal {F}$. $G$ is maximally dense if it has the maximum number of edges over all $n$-vertex graphs in $\mathcal {F}$. The edge density of $G$ is the ratio between its number of edges and its number of vertices. $G$ is optimal if it has the maximum edge density over all graphs of $\mathcal {F}$. Note that an optimal graph is also maximally dense, while the converse may not be true; similarly, a maximally dense graph is maximal, but there are maximal graphs that are not maximally dense; Figure 4(a) shows a maximally dense 1-planar graph with 5 vertices that is not optimal; Figure 4(b) shows a 1-planar graph with 12 vertices that is maximal but not optimal, and Figure 4(c) shows an optimal 1-planar graph with 12 vertices.
| Graph Family | Max. Num. Edges | Tight | Refs |
|---|---|---|---|
| 1-planar | $4n - 8$ |  | [58, 197] |
| straight-line 1-planar | $4n - 9$ |  | [2, 115] |
| bipartite 1-planar | $3n-8$ for even $n \ne 6$ |  | [168] |
| $3n-9$ otherwise | |||
| IC-planar | $3.25n - 6$ |  | [231] |
| NIC-planar | $3.6n - 7.2$ |  | [86] |
| 2-planar | $5n - 10$ |  | [197] |
| 3-planar | $5.5(n - 2)$ | $+$ | [194] |
| 4-planar | $6n - 12$ | $+$ | [3] |
| $k$-planar $(k \ge 5)$ | $3.81\sqrt {k}\,n$ | $\times$ | [3] |
| 3-quasi planar | $6.5n-20$ | $+$ | [8] |
| 4-quasi planar | $72(n-2)$ | $\times$ | [1] |
| $k$-quasi planar $(k \ge 5)$ | $c_k n \log n$ | $\bigcirc$ | [212] |
| skewness-$k$ | $3n-6+k$ |  | Trivial |
| $k$-apex | $3(n-k)-6+\sum _{i=1}^k(n-i)$ |  | Trivial |
| $(k,l)$-grid-free | $c_{k,l}\,n$ | $\times$ | [192] |
| radial-$(k,l)$-grid-free | $8 \cdot 24^lkn$ | $\times$ | [192] |
| natural-$k$-grid-free | $O(n \log ^{4k-6} n)$ | $\bigcirc$ | [4] |
| straight-line natural-$k$-grid-free | $O(kn \log ^2 n)$ | $\bigcirc$ | [4] |
| fan-crossing-free | $4n-8$ |  | [82] |
| straight-line fan-crossing-free | $4n-9$ |  | [82] |
| $k$-fan-crossing-free ($k \ge 3$) | $3(k-1)(n-2)$ | $\times$ | [82] |
| fan-planar | $5n-10$ |  | [169] |
| straight-line RAC | $4n - 10$ |  | [118] |
| straight-line ACE$\alpha$ | $3(3n-6)$ | $\times$ | [5] |
| straight-line ACL$\alpha$ | $\frac{\pi }{\alpha }(3n-6)$ | $\times$ | [128] |
| 1-gap-planar | $5n-10$ |  | [34] |
| $k$-gap-planar ($k\gt 1$) | $O(\sqrt {k}n)$ | $\times$ | [34] |
| straight-line (3-length-path)-sif | $O(n \log n)$ | $\bigcirc$ | [193] |
| straight-line (5-length-path)-sif | $O(n\log n/\log \log n)$ | $\bigcirc$ | [193] |
| straight-line (4-length-cycle)-sif | $O(n^{8/5}$) | $\bigcirc$ | [199] |
| planarly-connected | $c\,n$ | $\times$ | [7] |
| Most of the bounds in the table hold for simple drawings only; though few of them are still valid for non-simple drawings. The symbol | |||
Find a tight upper bound on the edge density of $k$-quasi planar graphs for $k\gt 4$. The problem is relevant also when the edges are drawn as $x$-monotone curves.
Find tight upper bounds on the edge density of (simple) $k$-planar graphs for $k \ge 3$.
Starting references for Problem 1 are listed in the References [143, 212, 220, 221]. We recall that Pach et al. conjecture an upper bound that is linear in the number of vertices [195]. Concerning Problem 2, recent papers discuss the edge density of (not necessarily simple) 3-planar graphs [46, 47].
Another research direction is concerned with providing lower bounds on the number of edges of maximal beyond-planar graphs. This type of question is mostly unexplored; results are known for 1- and 2-planar graphs [30, 62]. We suggest the following.
Find a lower bound on the edge density of maximal straight-line RAC graphs.
5 RECOGNITION
Given a graph $G$ and a family $\mathcal {F}$ of beyond-planar graphs, the recognition problem studies the complexity of deciding whether a graph $G$ belongs to $\mathcal {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 [159]. 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 [147, 176], even if the skewness of the input graph is 1 [76]. 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 [35]. Recognizing 1-planar graphs remains NP-complete also when the input graph comes with a fixed rotation system, which must be preserved [31]. 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 [66]; the testing algorithm exploits a structural characterization of optimal 1-planar graphs [213]. Recently, a similar structural characterization has been proved for optimal 2-planar and optimal 3-planar graphs [47], 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., [61]). We refer the reader to the annotated bibliography by Kobourov et al. for further references [175]. It is worth remarking that several papers present interesting bounds of graph parameters for 1-planar 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 [127], $O(\sqrt {kn})$ treewidth and $O(k)$ layered treewidth [126], and bounded expansion [187] (see [175] for more results).
Recognizing skewness-$k$ graphs is NP-complete in the general case [183], but the problem can be solved in $O(n)$ time for any fixed value of $k$ (i.e., it is FPT with parameter $k$) [173].
The set of 1-apex graphs is closed under the operation of taking minors [149], hence these graphs have a forbidden graph characterization by the Robertson-Seymour theorem [204]. However, the set of obstructions for these graphs has only been partially discovered [184]. Recognizing $n$-vertex $k$-apex graphs is NP-complete [180], but there is an $O(n)$-time algorithm if $k$ is a fixed constant [172].
Recognizing fan-planar graphs is NP-complete [53], even for a fixed rotation system [42]. The same holds for 1-gap-planar graphs [34].
Recognizing straight-line RAC drawable graphs is NP-hard in general [25], but can be solved in linear time for complete bipartite graphs [117]. Even the more restricted problem of deciding whether a graph admits a straight-line RAC drawing with at most one crossing per edge is NP-hard [44]. It is, however, unknown if recognizing straight-line RAC (1-planar) drawable graphs belongs to NP because the complexity of deciding whether an embedded graph has an embedding-preserving 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 [44, 81] (see also Section 7).
Concerning $\alpha$-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 $\frac{1}{4}$-SHPED, then $n\lt 165$; also, if a graph has bandwidth $k$, it has a $\Theta (\frac{1}{k})$-SHPED [71]. 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 $\alpha$ may not be the same for all the edges) is NP-hard but becomes polynomial-time solvable for geometric 2-planar graphs [71]. Table 3 summarizes the results discussed in this section.
| Graph Family | Restrictions | Complexity | Refs |
|---|---|---|---|
| 1-planar | NP-complete | [147, 176] | |
| 1-planar | bounded bandwidth, pathwidth, or treewidth | NP-complete | [35] |
| 1-planar | bounded cyclomatic number or treedepth | $O(n)$ | [35] |
| 1-planar | fixed rotation system | NP-complete | [31] |
| 1-planar | skewness-1 | NP-complete | [77] |
| optimal 1-planar | $O(n)$ | [66] | |
| skewness-$k$ | NP-complete | [183] | |
| skewness-$k$ | bounded $k$ | $O(n)$ | [173] |
| $k$-apex | NP-complete | [180] | |
| $k$-apex | bounded $k$ | $O(n)$ | [172] |
| fan-planar | NP-complete | [53] | |
| fan-planar | fixed rotation system | NP-complete | [42] |
| straight-line RAC | NP-hard | [25] | |
| staight-line 1-planar RAC | NP-hard | [44] | |
| 1-gap-planar | NP-complete | [34] | |
| 1-gap-planar | fixed rotation system | NP-complete | [34] |
Investigate graph parameters for which the recognition problem for some families of beyond-planar graphs becomes tractable. For example, in the light of the results for 1-planar graphs, is the recognition problem of 1-gap-planar graphs FPT with respect to the cyclomatic number or tree depth?
Furthermore, the recognition problem remains unexplored for many other families of beyond-planar graphs. This poses several open questions. For example:
What is the complexity of deciding whether a graph is $k$-quasi planar? The question is already interesting when $k=3$.
It is know that every graph has a RAC drawing with at most three bends per edge [118] and that it has $O(n)$ edges if either one bend or two bends per edge are allowed [15, 28] (see Section 7). Recognizing straight-line RAC graphs is NP-hard [25], but the following question is still open.
What is the complexity of recognizing $k$-bend RAC drawable graphs, for $k \in \lbrace 1,2\rbrace$?
A characterization of the graphs that admit an $\alpha$-SHPED is unknown.
What is the complexity of deciding whether a graph admits an $\alpha$-SHPED? In particular, what is the complexity for $\alpha = \frac{1}{4}$?
6 RELATIONSHIPS BETWEEN GRAPH FAMILIES
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.
Brandenburg et al. study the RAC drawability of the 1-planar graphs with independent pairs of crossing edges (the IC-planar graphs) [67]. They show that every IC-planar graph has a straight-line RAC drawing, while this is not true for the larger class of the NIC-planar graphs [33].
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 [44]: 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.
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 \ge 3$) because three mutually crossing edges imply that two independent edges are crossed by a third one.
 |
| In each pairwise comparison, when applicable, we assume $k \le h$. The table does not report inclusion relationships about restricted subfamilies, such as IC-planar graphs, NIC-planar graphs, and optimal straight-line RAC graphs. These relationships are discussed in the text. |
Characterize the straight-line RAC graphs that are 1-planar.
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 [14, 152] and every optimal 3-planar graph is also 3-quasi planar [47], the following questions on the combinatorial relationships between $k$-planarity and $h$-quasi planarity remain unanswered.
Is a $k$-planar graph also $k$-quasi planar? For sufficiently large values of $k$, is every $k$-planar graph $f(k)$-quasi planar, for some function $f(k)=o(k)$?
Finally, the relationships between some pairs of beyond-planar graph families have not yet been studied. For example:
What is the relationship between $k$-gap planar and fan-planar graphs, for $k \ge 1$?
7 QUALITY METRICS
While beyond-planar graphs focus on properties of edge crossings, other quality metrics have been extensively used in the literature to produce geometric representations of graphs that are clear and pleasing for the reader. For example, in a polyline drawing, the vertices of the graph are points and the edges are polylines whose complexity should be kept as low as possible to assist the reader. A common measure to capture the edge complexity of a polyline drawing is the number of bends per edge. Results concerning the edge complexity of beyond-planar graphs are presented in Section 7.1. Other drawing paradigms, like visibility representations and contact representations, convey edges as horizontal or vertical segments and shift the complexity to the vertices, which are drawn using more general shapes such as bars, rectangles, or polygons. We survey work related to the vertex complexity of beyond-planar graphs in Section 7.2. Finally, a common goal for polyline drawings is to use integer coordinates for vertices and bend points and to fit the drawing into a small bounding box, in order to display the drawing onto a screen with finite resolution. In particular, the area of a polyline drawing is the area occupied by its bounding box (i.e., by the minimum axis-aligned box containing the drawing). If the bounding box has side lengths $X-1$ and $Y-1$, we say that the drawing has area $X \times Y$. Results concerning the area requirement of beyond-planar graphs in combination with edge/vertex complexity requirements are considered in Sections 7.1 $-$ 7.2. Section 7.3 discusses area-crossings tradeoffs for beyond-planar drawings of planar graphs.
7.1 Edge Complexity
| Graph Family | Restrictions | Complexity of testing | Refs |
|---|---|---|---|
| 1-planar | fixed embedding | $O(n)$ | [158] |
| 1-planar | fixed pairs of crossing edges | $O(n)$ | [156] |
| maximal skewness-1 | fixed embedding | $O(n)$ | [132] |
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 [118], while 1-bend and 2-bend RAC drawable graphs have at most $5.5n-11$ edges [15] or $74.2n$ edges [28], respectively. If we allow up to four bends per edge, every graph can be drawn RAC in $O(n^3)$ area [103]. For graphs with bounded vertex degree, we have the following results [18]: $(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$\alpha$ drawings with one or two bends per edge, it is proved that they have at most $27n$ edges and $385n$ edges, respectively [5, 6]. On the other hand, every graph admits an ACL$\alpha$ drawing with one bend per edge in $O(n^2)$ area [103].
Table 6 summarizes the main results concerning tradeoffs between the number of bends per edge and the area requirement of beyond-planar drawings.
| Number of bends per edge | ||||||
|---|---|---|---|---|---|---|
| Graph Family | 0 | 1 | 2 | 3 | 4 | Refs |
| IC-planar | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | [67] |
| NIC-plane RAC | ? | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | [81] |
| 1-planar | $\Omega (2^n)$ | ? | $O(n^4)$ | $O(n^4)$ | $O(n^4)$ | [158], this paper |
| 1-plane RAC | $\Omega (2^n)$ | ? | $O(n^6)$ | $O(n^6)$ | $O(n^6)$ | [81, 158] |
| RAC | $\Omega (n^2)$ | $O(n^2)$, if $\Delta \le 6$ | $O(n^2)$, if $\Delta \le 3$ | $O(n^4)$ | $O(n^3)$ | [18, 103, 118] |
| ACL$\alpha$ | ? | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | [103] |
| $\Delta$ denotes the maximum vertex degree. The question mark indicates that no area bound is known. | ||||||
7.2 Vertex Complexity
A bar visibility representation of a graph $G$ maps each vertex of $G$ to a distinct horizontal segment, called bar, and each edge of $G$ to a vertical unobstructed segment, called visibility, between the two bars corresponding to its end-vertices. This kind of representation is intrinsically planar, and, on the other hand, every planar graph admits this representation3 (see, e.g., [215, 227]). In order to realize nonplanar graphs, other visibility models have been proposed, such as bar $k$-visibility representations and rectangle visibility representations.
In a bar $k$-visibility representation, each visibility intersects at most $k$ bars [89]. In particular, it is proved that every 1-planar graph has a bar 1-visibility representation [63, 139]. A rectangle visibility representation maps each vertex to an axis-aligned rectangle and each edge to a horizontal or vertical visibility between the two corresponding rectangles [208, 228]. In general, there are 1-plane graphs, and even IC-plane graphs, that do not admit such a representation. Biedl et al. describe a linear-time algorithm to test whether a 1-plane graph admits an embedding-preserving rectangle visibility representation and to compute one if it exists [51]. The algorithm is based on a characterization that extends the set of obstructions used by Thomassen to characterize the stretchable 1-plane graphs [216]. The rectangle visibility model has been recently generalized to extend the class of representable graphs; namely, in a generalized model, called ortho-polygon visibility representations, the vertices are drawn as general orthogonal polygons [99]. Di Giacomo et al. prove that every 1-plane graph admits an embedding-preserving ortho-polygon visibility representation [99]. If the input graph is 3-connected, one can construct a representation such that each vertex has at most 12 reflex corners, while 2 reflex corners may be needed. If the graph is only 2-connected, it may require at least one vertex with a linear number of reflex corners. The upper bound for 3-connected 1-plane graphs exploits results on edge partitions (see also [43, 100, 179]). The gap for 3-connected 1-plane graphs has been recently reduced, proving that at most 5 reflex corners per vertex always suffice, while 4 reflex corners are needed in some cases [182].
A further visibility model, called L-visibility representations, maps every vertex to a horizontal and a vertical segment sharing an endpoint (i.e., by an L-shape in the set 
), and each edge to a horizontal or vertical visibility segment joining the two L-shapes corresponding to its two end-vertices. It is proved that every IC-planar graph admits an L-visibility representation [181].
Visibility representations of 1-planar graphs have been studied also in 3D. A $z$-parallel visibility representation maps the vertices of a graph to isothetic disjoint rectangles parallel to the $xy$-plane and the edges to visibilities parallel to the $z$-axis. Every 1-plane graph has a $z$-parallel visibility representation [17]. The computed drawing is such that there is a plane orthogonal to the rectangles of the representation, and the intersection of this plane with the representation defines a bar 1-visibility representation of the graph.
Finally, Alam et al. studied contact representations in which vertices are represented by axis-aligned polyhedra in 3D and edges are realized by non-zero area common boundaries between corresponding polyhedra [12]. They prove that every optimal 1-plane graph can be realized as a contact representation where vertices are axis-aligned boxes if it contains no separating 4-cycles or as a contact representation where vertices are L-shaped polyhedra otherwise. Table 7 summarizes the main results on visibility and contact representations of 1-planar graphs.
| Visibility | Contact | |||||||
|---|---|---|---|---|---|---|---|---|
| Graph Family | RVR | B1VR | OPVR | LVR | ZPR | BCR | LCR | Refs |
| IC-planar |  |  |  |  |  | ? | ? | [12] [17] [51] [63][99] [139] [181] |
| optimal 1-planar with no separating 4-cycles | $\times$ |  |  |  |  |  |  | |
| optimal 1-planar | $\times$ |  |  |  |  | ? |  | |
| 1-planar | $\times$ |  |  | $\times$ |  | ? | ? | |
| $\times$ indicates that there are instances of the graph family not admitting that visibility or contact representation. | ||||||||
7.3 Area-Crossing Tradeoffs for Planar Graphs
The area requirement of planar straight-line drawings is a widely investigated problem. Motivated by VLSI applications, seminal papers studied how to compute area-efficient graph layouts [178, 219]. Different popular results establish that an $n$-vertex planar graph can always be drawn with straight-line edges in $O(n^2)$ area [88, 207]. This bound is worst-case optimal for the family of planar graphs as there are infinitely many planar graphs whose planar drawings require quadratic area [88]. Several attempts have been made to prove the existence of straight-line planar drawings with $o(n^2)$ area for specific subfamilies of planar graphs, such as trees, outerplanar graphs, and series-parallel graphs (see, e.g., [106] for references on these results).
A natural question that arises from the aforementioned results is whether allowing some edge crossings may help to reduce the area of a drawing of a planar graph. In other words, what is the area requirement of beyond-planar drawings of planar graphs? Wood shows that, for any fixed positive integer $k \gt 0$, all $k$-colorable graphs have a straight-line drawing in linear area; this implies that planar graphs always admit $O(n)$ area straight-line drawings with crossing edges [229]. However, the technique by Wood can give rise to drawings where some edges contain a linear number of crossings and the angles at which two edges cross can be arbitrarily small.
The use of edge crossings that form large angles is studied in different papers. Straight-line RAC drawings of planar graphs may require $\Omega (n^2)$ area [18], thus right angle crossing drawings do not help to reduce the area requirement bound for planar graphs in the general case. On the positive side, for infinitely many values of $n$, there exists an $n$-vertex planar graph whose requirement is $\Theta (n^2)$ for straight-line planar drawings and $\Theta (n)$ for straight-line RAC drawings [222]. Analogous results hold for other quality metrics such as uniform edge length and angular resolution [222]. In addition, every planar graph admits an ACL$\alpha$ drawing with two bends per edge in $O(n^\frac{5}{3})$ area [20], and every planar graph with vertex-degree at most $\Delta$ admits a 4-bend RAC drawing in $O(n \sqrt {\Delta n})$ area [20]. Note that, if $\Delta$ is a sublinear function of $n$, these RAC drawings have subquadratic area.
Compact nonplanar drawings of planar graphs with a constant or sublinear number of crossings per edge are also studied [106]. Every $n$-vertex outerplanar graph admits a straight-line drawing with $O(\frac{n}{\log n})$ crossings per edge in $O(n \log n)$ area. Also, for any given $\epsilon \gt 0$, every $n$-vertex outerplanar graph admits a straight-line drawing with $O(n^{1-\epsilon })$ crossings per edge in $O(n^{1+\epsilon })$ area, which gives a clear tradeoff scheme between area requirement and number of crossings per edge. These results are based on a linear-time drawing algorithm, which can also be applied to other subfamilies of planar graphs that admit a “level” drawing with specific properties, such as flat series-parallel graphs with bounded degree (see [106]). Nonetheless, if we insist on having a constant number of crossings per edge, planar and nonplanar drawings of planar graphs have in general the same area requirement. This is true even for series-parallel graphs [107].
On the positive side, every $n$-vertex planar graph has a straight-line $o(n)$-quasi planar drawing in $o(n^2)$ area. More precisely, by combining drawing techniques in Di Giacomo et al. [107] with results on the track number of planar graphs [125], one can prove that every $n$-vertex planar graph admits either a straight-line $O(\log n)$-quasi planar drawing in $O(n \log ^{3} n)$ area or a straight-line $O(\log ^{2} n)$-quasi planar drawing in $O(n \log n)$ area. Also, every partial 2-tree admits a linear-area straight-line drawing with thickness at most 10 and hence a linear-area 11-quasi planar straight-line drawing [107]. Outerplanar graphs and flat series-parallel graphs with bounded vertex degree (which are partial 2-trees) have quasi planar and 5-quasi planar drawings in linear area, respectively [105]. Table 8 summarizes the main results presented in this subsection.
 | straight-l. $k$-planar | straight-l. $k$-quasi planar | $k$-bend RAC | $k$-bend ACL$\alpha$ | ||||
|---|---|---|---|---|---|---|---|---|
| Area | $k$ | Area | $k$ | Area | $k$ | Area | $k$ | |
| outerplanar | $O(n^{1+\epsilon })$ | $O(n^{1-\epsilon })$ | $O(n)$ | 3 | ? | ? | ||
| $O(n \log n)$ | $O(\frac{n}{\log n})$ | |||||||
| flat series-parallel bounded degree | $O(n^{1+\epsilon })$ | $O(n^{1-\epsilon })$ | $O(n)$ | 5 | ? | ? | ||
| $O(n \log n)$ | $O(\frac{n}{\log n})$ | |||||||
| partial 2-tree | $\Omega (n2^{\sqrt {\log n}})$ | $O(1)$ | $O(n)$ | 11 | ? | ? | ||
| planar | $\Omega (n^2)$ | $O(1)$ | $O(n \log ^3 n)$ | $O(\log n)$ | $\Omega (n^2)$ | 0 | $O(n^\frac{5}{3})$ | 2 |
| $O(n)$ | $O(n)$ | $O(n \log n)$ | $O(\log ^2 n)$ | $O(n \sqrt {\Delta n})$ | 4 | |||
| $\Delta$ denotes the maximum vertex degree. The question mark indicates that bounds better than those for planar drawings are not known. For reasons of space, the table does not report the corresponding references. | ||||||||
Characterize the stretchable $k$-quasi planar topological graphs (even when $k=3$).
Another research stream is about embedding-preserving drawings with good crossing angle resolution. This question is interesting even for structurally simple topological graphs. For example:
Does every topological graph of maximum vertex degree three admit an embedding-preserving straight-line RAC drawing?
Finally, we recall that a characterization of the almost-plane graphs that are stretchable is known only when the number of edges is $3n-5$ (a characterization for nonmaximal is known on the sphere but not in the plane) [132]. Hence, a natural question is the following:
Characterize the topological skewness-$k$ graphs that are stretchable. This question is interesting also when $k=1$ and the number of edges is smaller than $3n-5$.
Several open problems can also be deduced by looking at the “?” in Tables 6, 7, and 8. For example:
It is known that every 1-planar graph has a RAC drawing with at most one bend per edge [44]. However, it is not known whether such a drawing can be computed in polynomial area.
Regarding this problem, it has been recently shown that NIC-plane graphs admit an embedding-preserving 1-bend RAC drawing in quadratic area [81].
Do 1-planar graphs admit a box contact representation? The question is interesting even for subfamilies of 1-planar graphs, such as IC-planar graphs.
Do planar graphs admit a $k$-bend RAC drawing in subquadratic area with $k \ge 4$?
When $k=4$, the answer is affirmative if the maximum vertex-degree is sublinear [20].
8 CONSTRAINTS
Several papers concentrate on beyond-planar drawings where the vertices and/or the edges have additional geometric constraints. We discuss the main scenarios studied in the literature.
8.1 Vertices on Lines, Circles, and External Boundary
The study of graph layouts in which vertices are placed on a given set of horizontal lines, often called layers, or on a set of concentric circles, has a well-established tradition in graph drawing [95, 102].
Characterizations for those graphs that admit either 2-layer RAC drawings [98], or 2-layer 1-planar drawings [115], or 2-layer fan-planar drawings [52] are known; all of them can be regarded as generalizations of caterpillars, the class of 2-layer planar drawable graphs [134]. 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 $\langle u_1,u_2, \dots , u_\frac{n}{2} \rangle$ and $\langle v_1,v_2, \dots , v_\frac{n}{2} \rangle$, plus the edges $(u_i, v_i)$, $(i = 1, 2, \dots , \frac{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}$ [53].
| Graph Family | Max. Num. Edges | Tight | Refs |
|---|---|---|---|
| 2-layer 1-planar | $1.5n-2$ |  | [115] |
| 2-layer RAC | $1.5n-2$ |  | [98] |
| 2-layer fan-planar | $2n-4$ |  | [53] |
| outer 1-planar | $2.5n-4$ |  | [29, 115] |
| outer fan-planar | $3n-5$ |  | [53] |
| convex geometric $k$-quasi planar | $2(k-1)n-\binom{2k-1}{2}$ |  | [78, 124, 186] |
| convex geometric fan-crossing-free | $\lfloor 5n/2 - 4 \rfloor$ |  | [69] |
| Graph Family | Complexity | Refs |
|---|---|---|
| 2-layer RAC | $O(n)$ | [98] |
| 2-connected 2-layer fan-planar | $O(n)$ | [52] |
| outer 1-planar | $O(n)$ | [29, 155] |
| full outer 2-planar | $O(n)$ | [157] |
| maximal outer fan-planar | $O(n)$ | [42] |
| circular RAC | $O(n)$ | [91] |
| upward RAC | NP-hard | [18] |
| simultaneous RAC | NP-hard | [148] |
| $k$-SEFE | NP-complete | [148] |
| straight-line point-set RAC | NP-hard | [142] |
From the algorithmic point of view, there exist linear-time testing and drawing algorithms for 2-layer RAC graphs [98] and for 2-connected 2-layer fan-planar graphs [52], while the complexity of recognizing 2-layer fan-planar graphs when the graph is only 1-connected is still open. For 2-layer 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 [98]. We remark that the crossing minimization problem is a well-known NP-complete problem in the general case, which remains hard even for 2-layer drawings without the restriction that crossing edges are orthogonal [135].
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\Delta$ crossings per edge, where $\Delta$ is the maximum vertex-degree of the graph and 1-page drawings of partial 2-trees with at most $\Delta ^2$ crossings per edge [54]. 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 [127], while for 1-planar graphs $O(1)$ upper bounds are known [11, 41]. Furthermore, if the queue number of planar graphs is bounded (which is still unknown with the best upper bound being $O(\log {n})$ [129]), then the same is true for $k$-planar graphs [131].
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 [42]. 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 [191]. 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 [80]. 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 $(\lfloor \sqrt {4k+1} \rfloor +1)$-degenerate and consequently $(\lfloor \sqrt {4k+1} \rfloor + 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] [165] 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 second-order logic and have bounded treewidth. In Chaplick et al. [80], it is also proved that planar graphs and outer quasi planar graphs are incomparable classes under containment, while in Geneson et al. [146] 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. [91]. 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 [90]. Di Giacomo et al. study how to draw outer 1-planar graphs with a small number of edge slopes [110]. They prove that every outer 1-planar graph admits an outer 1-planar straight-line drawing that uses $O(\Delta)$ different slopes, where $\Delta$ is the maximum vertex-degree of the graphs.
8.2 Upward RAC Drawings, Simultaneous RAC and Point-Set RAC Embedding
RAC drawings have been studied in combination with other popular graph drawing conventions that impose additional geometric constraints on the layout, namely the upward drawing convention for directed graphs (digraphs for short), the simultaneous embedding convention for multiple graphs with the same vertex set, and the point-set embedding convention. We discuss them here.
Is there a function $f(\cdot)$ such that every planar graph of vertex-degree at most $\Delta$ admits a 2-page drawing that is $f(\Delta)$-planar?
Establish tight bounds on the book thickness of $k$-planar graphs (even when $k=1$).
Not all planar acyclic digraphs have a straight-line upward RAC drawing [18], thus we ask:
Does every acyclic planar digraph admit a 1-bend upward RAC drawing?
Every pair of planar graphs sharing their vertex set admits an SRE with at most six bends per edge [48]. On the other hand, if no restriction on the edge crossings is given, such a pair admits an SE with at most two bends per edge [109].
Does every pair of planar graphs that share their vertex set admit a simultaneous RAC embedding with less than six bends per edge?
A set $S$ of points in the plane is universal for a family of graphs if every element of the family admits a PSE on $S$ with straight-line edges. A well-known result is that a universal point set of size $n$ that supports straight-line crossing-free drawings of all planar graphs with $n$ vertices does not exist [88]. One may wonder whether a beyond-planar version of this problem is more likely to have a positive answer. In particular, we ask the following.
Is there a set $S$ of $n$ points in the plane such that every planar graph with $n$ vertices admits an $f(n)$-planar point-set embedding on $S$ with straight-line edges such that $f(n) \in o(n)$?
9 IMPLEMENTATIONS AND EXPERIMENTS
The applied research in graph drawing beyond planarity has been mainly pursued along two directions: $(i)$ Cognitive experiments aimed to better understand the impact of some types of forbidden configurations on the capability of a user to execute visualization-based analysis tasks. $(ii)$ The implementation and experimentation of algorithms to compute beyond-planar graph drawings and the development of visualization systems for real-world application domains. We briefly discuss the contributions in these two directions.
Recall that PEDs aim to reduce edge crossings and visual clutter; the central part of each edge is erased and the length of the two remaining segments are computed to preserve useful geometric information [40]. An $\alpha$-SHPED of a straight-line drawing is immediately defined for a fixed value of $\alpha$ [72]. In particular, some edge crossings may not be avoidable, although the amount of ink removed from the original drawing might be large (e.g., $50\%$ when $\alpha =\frac{1}{4}$). On the other hand, it is possible to maximize the ink and remove edge crossings by using different values of $\alpha$ for different edges. Binucci et al. present a user study in which PEDs obtained via heuristics are compared with the standard model $\frac{1}{4}$-SHPED [56]. The results suggest that the benefit of homogeneity overcomes, in terms of readability, the benefit of fewer crossings and more ink.
Other experiments on beyond-planar graphs focus on a so-called edge stratification approach to analyze complex visualizations of graphs [108]. The approach is based on partitioning the edge set of a drawing into a minimal number of layers, such that the edges in each layer define a drawing with some desired properties related to crossings. For example, one can require that the drawing of each layer is planar, or that its crossing angles are larger than a given constant $\alpha$, or that it is $k$-planar for some fixed $k$. The experiments show that the stratification approach is mainly useful for local tasks such as counting the vertex degrees, while it is less effective for more global tasks such as finding shortest paths between pairs of vertices. The edge stratification algorithms proposed by Di Giacomo et al. are sometimes computationally expensive, especially when the drawing on each layer is required to be $k$-planar for relatively large values of $k$; most of these algorithms can be successfully applied to drawings with a few hundred vertices and edges [108].
To compute layered drawings of graphs with large-angle crossings (see Section 8), Di Giacomo et al. describe building block heuristics for extracting a maximum 2-layer RAC subgraph of a given bipartite graph [101]. They study both the setting in which no fixed ordering for the vertices of each partition set is given and the setting in which one of the two sets has a fixed linear ordering.
We finally mention the implementation of an algorithm that computes Ortho-Polygon Visibility Representations (OPVRs) of (nonplanar) graphs [99]. As explained in Section 7.2, in an OPVR of a graph $G$, each vertex is represented as an orthogonal polygon and each edge is either a horizontal or a vertical segment. The vertex complexity of an OPVR is the maximum number of reflex angles inside a polygon representing a vertex. Assuming that the graph $G$ comes with a fixed embedding, the algorithm in Di Giacomo et al. [99] tests in $O(n^2)$ time whether an OPVR of $G$ exists and, if so, it computes in $O(n^\frac{5}{2}\log ^\frac{3}{2}n)$ time an embedding-preserving OPVR of $G$ with minimum vertex complexity. This algorithm has been experimented on a large set of 1-plane graphs, which always admit an OPVR. The results show that, in practice, the computed OPVRs have usually a high percentage (up to $90\%$ in some cases) of vertices drawn with no reflex corners (i.e., as rectangles).
As already mentioned, Mutzel observed that the readability of a 2-layer drawing may not just depend on the number but also on the type of edge crossings [185]. We propose to study the following problem, for which some efforts have been limited so far to RAC drawings [101].
Design heuristics that reduce the number of forbidden crossing configurations in 2-layered drawings of bipartite graphs and perform a user study to compare the obtained drawings with those computed by means of 2-layer crossing minimization heuristics.
It would be interesting to analyze the practical impact that the various forbidden edge crossing configurations have in real-world drawings. For example, one could consider a large benchmark of real-world graphs with various sizes, draw these graphs by using different algorithms (e.g., force-directed algorithms), and then analyze the frequency of occurrence of each forbidden edge crossing configuration in these drawings. We summarize this problem as follows.
Analyze the impact of various forbidden edge crossing configurations in a large set of real-world drawings.
Finally, a very promising research direction is to perform new experiments and develop new theories on graph drawing beyond planarity based on the following user-centered approach: (i) Develop theories on how people read drawings based on HCI experiments; (ii) define optimization criteria on the edge crossings and their configurations; (iii) design combinatorial models and efficient algorithms; and (iv) experimentally verify the efficiency and effectiveness of the algorithms with new experiments that may lead to refining the model and/or the optimization goals.
10 CONCLUSION
The treatment of edge crossings in graph visualization embraces other topics that have not been discussed in the previous sections. Although these topics are not properly recognized as part of the literature on graph drawing beyond planarity, recent works have established connections with beyond-planar graph families, which highlight new and interesting research directions.
ACKNOWLEDGMENTS
We thank the anonymous referees of this article for their useful suggestions.