A Survey on Graph Drawing Beyond Planarity A Survey on Graph Drawing Beyond Planarity

Università degli Studi di Perugia, Italy

ACM Comput. Surv., Vol. 52, No. 1, Article 4, Publication date: February 2019.
DOI: https://doi.org/10.1145/3301281

Graph Drawing Beyond Planarity is a rapidly growing research area that classifies and studies geometric representations of nonplanar graphs in terms of forbidden crossing configurations. The aim of this survey is to describe the main research directions in this area, the most prominent known results, and some of the most challenging open problems.

CCS Concepts: • Mathematics of computing → Graph theory; Graphs and surfaces; Extremal graph theory; Graph algorithms; • Human-centered computing → Visualization;

Additional Key Words and Phrases: Graph theory, graph planarity, graph drawing, graph algorithms

ACM Reference format:
Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. 2019. A Survey on Graph Drawing Beyond Planarity. ACM Comput. Surv. 52, 1, Article 4 (February 2019), 37 pages. https://doi.org/10.1145/3301281


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.

Table 1. Examples of Beyond-Planar Graph Families

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.

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 49 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.


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).

Fig. 1.
Fig. 1. (a)–(b) Two drawings with the same rotation system but with different embeddings. (c)–(d) Two planar embeddings that differ for the choice of the outer face.

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.


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].

$k$-planar drawings. A $k$-planar drawing $(k \ge 1)$ does not contain an edge crossed more than $k$ times. The family of $k$-planar graphs, for $k=1$, was introduced in 1965 in the context of the simultaneous vertex-face coloring of planar graphs [202]. The study of $k$-planar graphs, for $k \gt 1$, was proposed for the first time as a tool for finding lower bounds on the crossing number of a graph [197] (i.e., on the minimum number of crossings in a drawing of a graph).

$k$-quasi planar drawings. A $k$-quasi planar drawing $(k \ge 3)$ does not have $k$ mutually crossing edges. The first results about $k$-quasi planar graphs date back to the 1980s and ’90s, when some authors addressed the problem of determining the maximum number of edges for these graphs [13, 196], answering questions posed even earlier [9, 32, 177].

Skewness-$k$ drawings. A skewness-$k$ drawing $(k \ge 1)$ is such that the removal of at most $k$ edges makes the drawing planar. In terms of forbidden configuration, it means that the drawing does not contain a set of crossings not covered by (at most) $k$ edges. A graph has skewness $k$ if it admits a skewness-$k$ drawing. Graphs with skewness $k$ are mainly studied for $k=1$, under the name of almost planar (or near planar) graphs, especially in terms of crossing number [76, 77]. Some authors also studied the problem of efficiently computing a skewness-$k$ drawing of a graph $G=(V,E)$ ($k \ge 1$) with the minimum number of crossings and with a fixed planar subgraph $G^{\prime }=(V,E \setminus F)$, where $|F|=k$ [84, 150]. For $k=1$, this problem is linear-time solvable and the solution gives an approximation to the crossing number of the almost planar graph $G$ [150].

$k$-apex drawings. A $k$-apex drawing $(k \ge 1)$ is such that the removal of at most $k$ vertices makes the drawing planar. It means that the drawing does not contain a set of crossing edges not covered by (at most) $k$ vertices. It is immediately seen that a skewness-$k$ drawing is also a $k$-apex drawing, but not vice versa. It is known that 1-apex graphs, mainly recognized as apex graphs in the literature, are closed under the operation of taking minors. They have connections with other aspects of graph minor theory (see, e.g., [205, 218]) and play a role in the relations between treewidth and graph diameter [92, 136]. Chimani et al. showed that computing an apex drawing with the minimum number of crossings and an identified apex vertex can be done efficiently [83].

$(k,l)$-grid-free drawings. For $k,l \ge 1$, a $(k,l)$-grid-free drawing does not contain a $(k,l)$-grid (i.e., two groups of $k$ and $l$ edges, respectively), such that each edge of the first group crosses all the edges of the second group. If the $k$ edges are incident to the same vertex, the $(k,l)$-grid is radial; if the $l$ edges are also incident to the same vertex, the $(k,l)$-grid is biradial. A $(k,l)$-grid is natural if all its edges are independent and no two edges in the same group cross. Pach et al. introduced $(k,l)$-grid-free graphs as a generalization of $k$-quasi planar graphs, and they investigated upper bounds on their number of edges [192].

$k$-fan-crossing-free drawings. A $k$-fan-crossing-free drawing does not contain $k \ge 2$ adjacent edges that cross another edge. A 2-fan-crossing-free drawing is also called fan-crossing-free. Cheong et al. introduced the class of $k$-fan-crossing-free graphs as a special case of the class of radial $(k,l)$-grid-free graphs where $k \ge 2$ and $l=1$ [82]; they were interested in establishing upper bounds on the number of edges for these graphs.

Fan-planar drawings. A fan-planar drawing does not contain two independent edges that cross a third one or two adjacent edges that cross another edge from different “sides” [169]. This family of drawings is somehow opposite to the class of fan-crossing-free drawings. From a practical point of view, fan-planar drawings can be used to create drawings with few edge crossings per edge in a confluent drawing style [114] (see, e.g., Figure 2). Note that a fan-planar drawing cannot contain a $(k,l)$-grid that is not radial, for $k \ge 2$.

Fig. 2.
Fig. 2. (a) A fan-planar drawing of a graph $G$ with 12 crossings. (b) A confluent drawing of $G$ with 3 crossings. (c) A fan-planar drawing with 16 crossings of another graph $G^{\prime }$. (d) A confluent drawing of $G^{\prime }$ with 8 crossings.

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.

ACE$\alpha$ and ACL$\alpha$ drawings. ACE$\alpha$ and ACL$\alpha$ drawings are natural variants of RAC drawings that are parametric in a value $\alpha \in (0,\frac{\pi }{2})$. In a straight-line ACE$\alpha$ drawing, any two crossing edges form an angle equal to $\alpha$. Graphs that admit this type of drawing were originally introduced with the name of $\alpha$AC$^=$ graphs [5, 6]. In a straight-line ACL$\alpha$ drawing, the value of any crossing angle is at least $\alpha$. These drawings were independently introduced by two different works; in Di Giacomo et al. [103] they are called LAC$_\alpha$ drawings, and in Dujmovic et al. [128] they are called $\alpha$AC drawings. As for RAC drawings, ACE$\alpha$ and ACL$\alpha$ drawings with edge bends are also considered in this survey.

Partial edge drawings (PEDs). In a Partial Edge Drawing (PED) the “middle” part of each edge is omitted to obtain a crossing-free representation. The idea behind this drawing style was introduced to visualize network overload between switches of the AT&T long-distance telephone network in the United States [40]. In particular, in an $\alpha$- Symmetric Homogeneous PED (SHPED) $(0\lt \alpha \lt \frac{1}{2})$, each edge $(u,v)$ is (partially) drawn as a pair of segments, called $\alpha$-stubs, one incident to $u$, the other incident to $v$, and each being a fraction $\alpha$ of segment $\overline{uv}$; the two stubs do not cross. The $\alpha$-SHPED model has been formally defined only recently [72] and has inspired both theoretical [71] and practical research (see, e.g., [56, 73]). Bruckdorfer et al. extended this model for graphs with maximum degree four, where the drawings are orthogonal and have at most one bend per edge [74].

$k$-gap-planar drawings. In a $k$-gap-planar drawing it is possible to map each crossing to one of the two corresponding crossing edges so that, for each edge $e,$ at most $k$ crossings are mapped to $e$. This family generalizes $k$-planar graphs and was introduced in Bae et al. [34] with a practical motivation inspired by edge casing, a method commonly used to alleviate the visual clutter caused by crossing lines [23, 138]. In a cased drawing of a graph, each crossing is resolved by locally interrupting one of the two crossing edges, and a $k$-gap-planar graph can be equivalently defined as a graph that admits a cased drawing in which each edge has at most $k$ gaps.

$H$-self-intersecting-free drawings. Given a graph $H$, a straight-line $H$-self-intersecting-free ( $H$-sif) drawing does not contain a self-intersecting geometric graph isomorphic to $H$. This definition specializes the more general $H$-free drawings, which do not contain graphs isomorphic to $H$. Typical forbidden configurations consider self-intersecting paths or cycles [193, 199], whose study was triggered by classical extremal problems on forbidden geometric subgraphs (see, e.g., [177]).

Planarly connected drawings. In a planarly connected drawing, each pair of crossing edges is independent and there is a crossing-free edge that connects two of their endpoints [7]. As will be discussed in Section 6, the main motivation for the study of these graphs comes from the fact that this family includes meaningful subfamilies of 1-planar and fan-planar drawings [7].

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.

Fig. 3.
Fig. 3. Tree that summarizes the taxonomy used in this survey.

Density. Since the mid-1960s, different authors (see, e.g., [32, 59, 177]) initiated the study of the following Turán-type problem: What is the maximum number of edges that a drawing of a graph can have without containing a given type of forbidden crossing configuration? Since then, this question has been long studied for all families of beyond-planar drawings. Results about the edge density of beyond-planar graphs are discussed in Section 4.

Recognition. In contrast to planarity testing, which is solvable in linear time [159], recognizing whether a graph belongs to a certain family of beyond-planar graphs is computationally hard for most families. For some subfamilies of beyond-planar graphs and/or under additional restrictions of the input, the recognition problem is polynomial-time solvable. Results about the recognition problem of different families of beyond-planar graphs are surveyed in Section 5.

Relationships. Studying the combinatorial relationships between different families of beyond-planar graphs is a fundamental step toward developing a comprehensive theory of graph drawing beyond planarity. The typical question in this context is the following: Let $F$ and $F^{\prime }$ be two forbidden types of crossing configurations (for example, $F$ may be “four mutually crossing edges” and $F^{\prime }$ may be “an edge crossed by three distinct edges”). If a graph $G$ admits a drawing where $F$ is forbidden, does $G$ also admit a drawing where $F^{\prime }$ is forbidden? Results about relationships of inclusion or of intersection between families of beyond-planar graphs are described in Section 6.

Quality metrics. In addition to forbidding some types of edge crossings in a nonplanar drawing, one can pursue some geometric optimization goals, often called quality metrics or aesthetic requirements, such as minimizing the drawing area for a given resolution rule, maximizing the drawing aspect ratio, or minimizing the number of different slopes used to draw the edges or the number of bends per edge. Quality metrics have a strong impact on the visual complexity of a drawing (see, e.g., [95, 170]). Results about this research direction are presented in Section 7. We remark that, within this research direction, the stretchability problem asks for computing an embedding-preserving straight-line drawing, and it has been studied for planar drawings since the mid-1930s (see, e.g., [141, 210, 224]).

Constraints. Depending on the type of graph and/or application, additional constraints can be imposed on a drawing. For example, for bipartite graphs, a typical constraint is to represent the vertices of each partition set on one of two parallel lines, which is a fundamental step in the so-called Sugiyama approach for layered drawings [211]. Other constraints require that all vertices are collinear in the so-called $k$-page drawing model [49, 190] or co-circular in the circular layout model [209]. Results about constrained beyond-planar graphs are surveyed in Section 8.

Implementations and experiments. The road to an effective technology transfer of the algorithmic solutions developed in the area of graph drawing beyond planarity has just begun. The initial steps in this direction are summarized in Section 9.


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.

Fig. 4.
Fig. 4. (a) A maximally dense 1-planar graph with 5 vertices and 10 edges. (b) A 1-planar graph with 12 vertices and 39 edges that is maximal but not optimal. (c) An optimal 1-planar graph with 12 vertices and 40 edges. (d) An optimal straight-line RAC graph with 7 vertices and 18 edges.

Density of $k$-planar graphs. For $1 \le k \le 4$, Pach and Tóth prove that $k$-planar graphs have at most $(k+3)(n-2)$ edges [197], and they also use this result to improve an earlier lower bound on the crossing number of a graph. In particular, the resulting bounds are tight for $k=1$ and for $k=2$, which means that the optimal 1-planar graphs have $4n-8$ edges and the optimal 2-planar graphs have $5n-10$ edges. The best known upper bounds for $k=3$ and $k=4$ are $5.5n-11$ [194] and $6n-12$ [3], respectively. For $k \gt 4$, the best known upper bound is $3,81\sqrt {k}\,n$ [3], which improves a previous bound of $4.108\sqrt {k}\,n$ [197]. Lower bounds on the edge density of maximal 1-planar graphs are given in Brandenburg et al. [62]. For bipartite 1-planar graphs, Karpov proves a tight bound of $3n-6$ when $n$ is even and $n \ne 6$, and of $3n -9$ otherwise [168]. Different subfamilies of 1-planar graphs have also been studied, such as 1-planar graphs where no two pairs of crossing edges share an end-vertex, called IC-planar graphs, and those for which two pairs of crossing edges share at most one end-vertex, called NIC-planar graphs. We report these bounds in Table 2. More results about the edge density of 1-planar graphs are surveyed in Kobourov et al. [175].

Table 2. Density
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 in column Tightness means that the bound is tight; the symbols $\times$ and $+$ mean that the bound is tight up to a multiplicative or to an additive constant, respectively, while the symbol $\bigcirc$ means that the bound may be far from tight.

Density of $k$-quasi planar graphs. In 1996, Pach, Shahrokhi, and Szegedy conjectured that, for any fixed $k \ge 2$, there exists a constant $c_k$, depending only on $k$, such that every $k$-quasi planar graph on $n$ vertices has at most $c_k n$ edges. This conjecture has been proved for $k=3$ and $k=4$ by various authors, with the best upper bounds currently known being $6.5n-20$ [8] and $72(n-2)$ [1], respectively. For $k\gt 4,$ the conjecture remains unproved, but several superlinear upper bounds have been established; the current best upper bound is $c_k n \log n$, for a suitable constant $c_k$ [212]. An $O(n \log n)$ upper bound for $k$-quasi planar graphs with $x$-monotone edges is also known [220, 221].

Density of fan-planar, $k$-fan-crossing-free, and $k$-gap graphs. Both fan-planar and 1-gap planar graphs on $n$ vertices have at most $5n-10$ edges, which is a tight bound [34, 169]. Recall that the same bound holds for 2-planar graphs. For $k \gt 1$, a $k$-gap planar graph has $O(\sqrt {k}n)$ edges [34]. A fan-crossing-free graph has at most $4n-8$ edges, and at most $4n-9$ if the edges are drawn as straight lines [82]. These bounds are analogous to those for topological and geometric 1-planar graphs. For $k\gt 2$, $k$-fan-crossing-free graphs have at most $3(k-1)(n-2)$ edges [82].

Density of straight-line RAC graphs, ACE$\alpha$ graphs, and ACL$\alpha$ graphs. Since straight-line RAC graphs are fan-crossing-free, they cannot have more than $4n-9$ edges. In fact, the maximum number of edges of a straight-line RAC graph is $4n-10$ [118], and for each $k \ge 3$ there exists a straight-line RAC graph $G_k$ with $n=3k-5$ vertices and $4n-10$ edges (i.e., optimal). Graph $G_k$ is constructed as follows (see Figure 4(d)): $(i)$ start from a triangulated plane graph on $k$ vertices; $(ii)$ add to this graph its dual, except for the node corresponding to the external face; $(iii)$ for each node $u$ of the dual, add the three edges that connect $u$ to the three vertices of the face corresponding to $u$. The fact that two edges of a straight-line RAC drawing $\Gamma$ of a graph $G$ can cross only at right angles immediately implies that the crossing graph of $\Gamma$ is bipartite; the crossing graph of $\Gamma$ has a vertex $v_e$ for each edge $e$ of $G$ and an edge $(v_e,v_{e^{\prime }})$ if the $e$ and $e^{\prime }$ cross in $\Gamma$. Hence, we can bi-color the edges of $G$ such that each color set induces a planar graph, which implies that $G$ has at most $6n-12$ edges. The $4n-10$ bound is proved by exploiting a finer coloring of the edges of $G$ with three colors and different counting arguments based on Euler's formula for planar graphs [118]. Dujmovic et al. provide an alternative proof of this bound, based on charging techniques [128]. They also show that straight-line ACL$\alpha$ graphs have at most $\frac{\pi }{\alpha }(3n-6)$ edges; the proof is based on a partition of the edges into distinct buckets, according to their directions, so that each bucket induces a planar graph. With similar arguments, it is shown that straight-line ACE$\alpha$ graphs have at most $3(3n-6)$ edges [5]. These bounds for ACL$\alpha$ and ACE$\alpha$ graphs are not known to be tight.

Density of other graph families. Since a skewness-$k$ graph $G$ becomes planar after the removal of at most $k$ edges, $G$ has at most $3n-6+k$ edges. This bound is trivially achieved by adding $k$ edges to a maximal planar graph. Similarly, removing at most $k$ vertices from an $n$-vertex $k$-apex graph yields a planar graph, and thus $k$-apex graphs have at most $3(n-k)-6+\sum _{i=1}^k(n-i)$ edges. A graph attaining this bound is constructed from a maximal planar graph, iteratively adding one vertex connected to all other vertices of the graph. $(k,l)$-grid-free and radial-$(k,l)$-grid-free graphs have at most $c_{k,l}\,n$ edges (where $c_{k,l}$ is constant in $n$ but depends on $k$ and $l$) and $8 \cdot 24^lkn$ edges, respectively [192], while natural-$k$-grid-free graphs have $O(n \log ^{4k-6} n)$ edges [4]. Concerning straight-line (3-length-path)-sif and straight-line (4-length-path)-sif graphs, it is shown that they have $O(n \log n)$ and $O(n\log n/\log \log n)$ edges, respectively [193], while straight-line (4-length-cycle)-sif graphs have $O(n^{8/5})$ edges [199]. Finally, planarly connected graphs have $c \, n$ edges, where $c$ is a constant [7]. Table 2 summarizes the discussed bounds on the edge density of beyond-planar graphs.

Open problems. Although Turán-type questions on beyond-planar drawings have been studied for a long time and the geometric graph theory literature contains many results, there are still beautiful open problems. For several families of beyond-planar graphs, the upper bounds on the maximum number of edges reported in Table 2 are not tight. Hence, the goal of achieving tight bounds for each of these families gives rise to an array of challenging problems. We find particular interest in the following (see also [70, 217]).

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.


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.

Table 3. Recognition
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]

Open problems. As shown in Table 3, the general recognition problem is NP-hard for most of the considered families. However, only a few papers deal with FPT algorithms, and no other types of exponential-time recognition algorithms have been considered. This motivates the following.

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}$?


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 [133]. They exhibit an infinite subfamily of straight-line RAC graphs with $n \ge 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)).

Fig. 5.
Fig. 5. (a) Schematic illustration of a straight-line RAC graph that is not 1-planar; each dashed edge $(u,v)$ represents four paths of three edges between $u$ and $v$, like those connecting vertices $\lbrace 3, 4\rbrace$ and vertices $\lbrace 2, 5\rbrace$. (b) A 1-plane graph with $4n-10$ edges that does not admit a straight-line RAC drawing; an infinite family of this type of graphs can be obtained by recursively plugging the whole graph inside the 4-cycle $\lbrace 5,6,7,8\rbrace$. (c) A 1-planar 1-bend RAC drawing of the graph in Figure 5(b).

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.

$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 \ge 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 $k$-quasi planar graphs [14]: For $k \ge 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$ [152]. Thus, every $k$-planar graph is $(k+1)$-quasi planar, for $k \ge 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 [53]. They prove that these two families are incomparable. On the one hand, they show that for any $k \ge 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 [65].

$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 [34]. By using Hall's theorem, they prove that for every $k \ge 1$ all $2k$-planar graphs are $k$-gap planar. On the other hand, for every fixed $k \ge 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 \ge 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 [7]. 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 \ge 3$) because three mutually crossing edges imply that two independent edges are crossed by a third one.

Table 4. Relationships

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.

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 [67, 133]. However, the following is still open.

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$?


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

Stretchability. The famous Fáry's theorem states that every plane graph is stretchable; that is, it has an embedding-preserving straight-line drawing [141] (this result was also independently proved by Wagner [224] and Stein [210]). 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 [216]. 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 [216] (see Figures 6(a)–6(b)). Later, Thomassen's characterization has been used to design a linear-time algorithm to test whether a 1-plane graph is stretchable [158]. This algorithm is based on an efficient procedure that checks whether a 1-plane graph $G$ contains any B- or W-configuration, and, if not, it also returns a straight-line drawing of $G$. Figures 6(c)–6(d) show a stretchable 1-plane graph $G$ and a straight-line drawing of $G$, respectively. Recently, Hong and Nagamochi have studied the stretchability problem of 1-plane graphs in a more relaxed setting [156]. 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 [132]. 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.

Fig. 6.
Fig. 6. (a) B-configuration. (b) W-configuration. (c) A 1-plane graph $G$. (d) Straight-line drawing of $G$.
Table 5. Stretchability
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]

Polyline drawings. As reported in the paragraph about stretchability, the class of 1-plane graphs admitting a straight-line drawing has been characterized [216], and there exist 1-plane graphs such that every embedding-preserving straight-line drawing requires an exponential area [158]. 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 [10]; 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)\times O(n^2)$ [36]; 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 [81]. 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 [44], but only assuming that the drawing algorithm can change the 1-planar embedding of the input graph. We also remark that for a simple family of 1-plane graphs, called kite-triangulations, an $\Omega (n^3)$ area lower bound for embedding-preserving straight-line RAC drawings is established [18]. 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. [175]. In recent papers, Argyriou et al. [27] and Kindermann et al. [174] 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 $\pi /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).

Fig. 7.
Fig. 7. Illustration of a technique for computing 2-bend drawings of 1-plane graphs in $O(n^4)$ area.

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.

Table 6. Edge Complexity and Area Requirement Tradeoffs
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.

Table 7. Vertex Complexity
Visibility Contact
IC-planar ? ? [12] [17]
[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. means that all instances in the graph family can be drawn with that visibility or contact representation. The question mark means that it not known whether the answer is $\times$ or . LEGEND: RVR = rectangle visibility representation, B1VR = bar 1-visibility representation, $k$OPVR = ortho-polygon visibility representation, LVR = L-visibility representation, ZPR = $z$-parallel visibility representation, BCR = box contact representation, LCR = L-shaped 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.

Table 8. Area-Crossings Tradeoffs for Planar Graphs
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.

Open problems. The stretchability problem for beyond-planar graphs is a fertile and essentially unexplored research subject. As a matter of fact, for any type of forbidden crossing configuration, the corresponding stretchability question gives rise to an open problem. For example:

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].


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].

2-layer drawings. 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 [211] used to draw graphs on multiple horizontal layers.

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].

Fig. 8.
Fig. 8. (a) A ladder $G$; (b) A 2-layer 1-planar drawing of $G$ that is also RAC. (c) A snake.
Table 9. Density for Constrained Families
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]
Table 10. Recognition for Constrained Families
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].

$k$-page drawings. Let $\ell$ be a line, called a spine. In a $k$-page drawing of a graph, each vertex is mapped to a distinct point of $\ell$ and each edge is drawn as a semicircle in one of $k$ distinct half-planes incident to $\ell$. 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., [130]); also, a 2-page drawing is sometimes called a permutation representation (see, e.g., [189]) or linear drawing (see, e.g., [75]), while a 1-page drawing is also called an arc diagram (see, e.g., [226]). 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 [113]).

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].

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 \gt 0$, a $k$-planar drawing with this property is an outer $k$-planar graph. Outer 1-planar graphs have at most $2.5n-4$ edges [29, 115], which is a tight bound. They can be recognized in linear time [29, 155] 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 [29]. 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 [157]). 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 [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.

Upward RAC drawings. In an upward drawing of a digraph, each edge is a curve monotonically increasing in the vertical direction (see, e.g., [95]). Upward drawings are used to visually convey the structure of acyclic digraphs and have also been extended to visualize other kinds of networks [50, 55]. Testing whether a given planar digraph admits an upward planar (i.e., crossing-free) drawing is one of the most studied problems in this context; refer to Didimo [116] for a survey. Although polynomial-time testing algorithms are known for specific subfamilies of planar digraphs or when the digraph has a fixed embedding, the testing problem is NP-complete in general [145]. Also, although a planar digraph has an upward planar drawing if and only if it has a straight-line upward planar drawing [96], there are digraphs for which every straight-line upward planar drawing requires exponential area [96, 97]; quadratic area is always achievable if we allow edge bends. Similar questions have been investigated for RAC drawings. Angelini et al. proved that deciding whether a planar acyclic digraph admits a straight-line upward RAC drawing is NP-hard and that the area required by an $n$-vertex straight-line upward RAC drawing may be exponential in $n$ [18].

Simultaneous RAC Embedding (SRE). Given two planar graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ with the same vertex set, a simultaneous embedding (SE) of $G_1$ and $G_2$ is a pair of planar drawings, $\Gamma _1$ of $G_1$ and $\Gamma _2$ of $G_2$, such that each vertex $v \in V$ has the same position in $\Gamma _1$ and $\Gamma _2$ (the edges of $\Gamma _1$ can cross those of $\Gamma _2$). The SE problem was introduced a decade ago, motivated by several practical scenarios [68], and since then it has been widely studied (see, e.g., [57] for a survey). A Simultaneous RAC Embedding (SRE) of two graphs $G_1$ and $G_2$ is an SE with the additional property that the union of the two planar drawings $\Gamma _1$ and $\Gamma _2$ is RAC. The SRE problem was originally introduced for straight-line drawings [24], showing that only restricted pairs of planar subgraphs admit such an embedding; for example, a wheel and a cycle might not admit a straight-line SRE. In general, deciding whether a pair of graphs admits an SRE with straight-line edges is NP-hard [148], while every pair of planar graphs has an SRE with at most six bends per edge [48]. The number of bends per edge can be further reduced for some combinations of specific subfamilies of planar graphs. Moreover, an SRE with at most two bends exists for those pairs of graphs admitting a special type of visibility representation in which vertices are axis-aligned L-shapes and edges are vertical or horizontal lines of sight connecting pairs of such shapes [140]. Another variant of SE in graph drawing beyond planarity considers a simultaneous embedding of two graphs $G_1$ and $G_2$ in which each of the two drawings $\Gamma _1$ and $\Gamma _2$ is allowed to have some desired type of crossings. This setting generalizes the classical SE instead of restricting it. For example, Di Giacomo et al. study Simultaneous Geometric Quasi Planar Embedding (SGQPE), where each $\Gamma _i$ is a straight-line quasi planar drawing [104]. They show, for instance, that a tree and a path always admit an SGQPE, in contrast to the negative result in the simultaneous geometric planar embedding setting [22].

Point-Set RAC Embeddings (PSRE). Given a set $S$ of points in the plane and a graph $G$ with $n=|S|$ vertices, a Point-Set Embedding (PSE) $\Gamma$ of $G$ on $S$ is a drawing of $G$ such that the vertices are placed to the points of $S$ through a one-to-one mapping, which can be given as part of the input (see, e.g., [198]) or not (see, e.g., [171]). Fink et al. studied Point-Set RAC Embeddings (PSREs) of graphs; that is, PSEs where the points of $S$ belong to an $n \times n$ grid and no two points are horizontally or vertically aligned [142]. They concentrate on computing PSREs with few bends per edge, where bends must occupy grid points as for the vertices. Different algorithmic results and bounds on the number of bends per edge are given, also under the assumption that the edge segments are restricted to be on grid lines. Among their results, they prove that every graph with $n$ vertices and $m$ edges admits a PSRE on any $n \times n$ grid point set with at most three bends per edge in $O((n+m)^2)$ area, which also implies that every planar graph admits a RAC drawing with at most three bends per edge in quadratic area, thus improving a previous result [20] in terms of bends per edge (see Section 7.3). On the negative side, testing whether a graph admits a PSRE without bends is NP-hard [20].

Open problems. Although the study of planar book embeddings has a long tradition in graph drawing (see, e.g., [49, 190, 230]), the study of its beyond-planar counterpart is much more recent. The question can be studied by either considering $k$-page drawings with forbidden crossing configurations (see, e.g., [52]) or by focusing on $k$-page book embeddings of beyond-planar graphs (see, e.g., [11, 41, 127]). For example, we mention the following two problems.

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)$?


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.

Cognitive studies. Early cognitive experiments on beyond-planar graphs estimate the effects of crossing angles on human eye movements and performance through the use of eye-tracking systems [160, 161]. The results show that sharp angles may trigger extra eye movements, causing delays for path search tasks, whereas crossings have usually little impact on node locating tasks. Subsequent experiments confirm the importance of large angle crossings to execute visualization-based analysis tasks [162, 164], thus motivating and stimulating the rich literature about RAC graphs and related graph families [119]. Further studies give some evidence that relevant improvements on graph layout readability derive from finding a good tradeoff between different quality metrics, such as crossing and vertex angles, rather than optimizing only one of them [163].

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].

Algorithms and systems. Several papers describe heuristics that attempt to optimize some desired properties for edge crossings, often in combination with classical graph drawing conventions. For example, to improve the readability of circular layouts, the MAXCIR post-processing algorithm [188] aims to increase crossing angles by using Quadratic Programming; it is fast in practice and yields better results compared to a traditional equal-spacing algorithm. BIGANGLE [163] is a force-directed algorithm that computes drawings of graphs with multiple quality metrics being improved at the same time; these metrics include crossing and vertex angle resolution. Argyriou et al. [26] propose another force-directed algorithm that computes drawings with high crossing and vertex angle resolution. In a recent paper, Bekos et al. [45] present a new algorithm to improve the crossing resolution of a drawing and discuss experiments in which this algorithms outperforms the algorithms in other works [26, 163]. A further contribution in the same direction as BIGANGLE is the topology-driven force-directed framework [121]. It allows the design of graph drawing algorithms that find good tradeoffs between different metrics, such as number of crossings, crossing angle resolution, geodesic edge tendency, and number of edge bends. This approach combines force-directed techniques with the popular topology-shape-metrics approach, originally proposed to compute bend-minimum orthogonal drawings [214]. Examples of drawings computed by topology-driven force-directed algorithms are shown in Figures 9(a)–9(b). As a follow-up of this work, the same authors implement an algorithm that first computes a straight-line drawing with a force-directed technique and then runs a post-processing procedure to improve the crossing angle resolution by representing edges as smoothed curves (see Figure 9(c)); each curve is monotone in the direction of the straight-line segment connecting its end-points. The algorithm is applied to the simultaneous embedding of suitably defined networks in a system for conceptual Web-site traffic analysis [120]. More recently, Demel et al. presented a heuristic to increase the smallest angle between two crossing edges in a given straight-line drawing, together with a speed-up technique to compute the pair of crossing edges with the smallest crossing angle in a straight-line drawing [93].

Fig. 9.
Fig. 9. (a)–(b) Topology-driven force-directed layouts. (c) Straight-line force-directed layout (left) and a subsequent layout with smoothed curves and improved crossing angles (right).

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).

Open problems.

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.


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.

Crossing minimization. Computing drawings of graphs with a minimum number of crossings, as well as determining the crossing number of a graph, are problems with a long tradition (see, e.g., [75, 206] for surveys on the subject). It is well known that the crossing minimization problem is NP-complete, and it remains hard also in very restricted scenarios (for instance, when the graph is bipartite and we look for a straight-line 2-layer drawing of it [144]). However, for 2-layer RAC drawable graphs, the problem can be solved efficiently [98], which suggests that the crossing minimization problem might be polynomial-time solvable also with respect to other forbidden crossing configurations.

Relaxed clustered planarity. In a clustered graph $G$, vertices are grouped into (hierarchical) clusters. In a drawing of $G,$ each cluster should be represented as a closed region containing all (and only) its vertices and all (and only) its subclusters. Also, an edge should not traverse a cluster if both its end vertices are outside it. Many papers study how to efficiently test whether a clustered planar graph admits a crossing-free drawing that meets the aforementioned properties [85, 170], and practical drawing heuristics have also been conceived, even for nonplanar large graphs [60, 94, 122, 123]. In the context of graph drawing beyond planarity, relaxed models of clustered planarity may disallow only some types of crossings. See Angelini et al. [19] for initial steps in this direction.

Hybrid visualizations. The use of matrix-based representations combined with the classical node-link representation has been proposed to diminish the negative effect of visual clutter in large and locally dense networks [37, 151]. More recently, the planarity testing and embedding problem of this type of hybrid visualizations have been further formalized [87, 111], and new families of beyond-planar graphs related to hybrid visualizations have been defined [21, 112].

Edge bundling. The idea of grouping edges to get planar drawings of nonplanar graphs was originally proposed under the name of confluent drawings [114, 137]. Later, practical edge-bundling techniques were used to cope with the visual clutter problem in node-link diagrams of large and dense graphs [153, 154, 232]. The idea is that “similar” edges are deformed and grouped into bundles, thus providing a more abstract and uncluttered view of the original drawing at the expense of possible ambiguities in terms of connections between vertices. Very recently, the use of edge bundling has been proposed in the context of graph drawing beyond planarity, with the introduction of the family of 1-fan-bundle planar graphs, which combines edge bundling with fan-planar graphs [16]. Following this example, other families can be conceived and studied.


We thank the anonymous referees of this article for their useful suggestions.



Research partly supported by the project: “Algoritmi e sistemi di analisi visuale di reti complesse e di grandi dimensioni” - Ricerca di Base 2018, Dip. Eng. Univ. of Perugia.

Authors’ addresses: W. Didimo, Università degli Studi di Perugia, Via G. Duranti 93, Perugia, PG, 06125, Italy; email: walter.didimo@unipg.it; G. Liotta, Università degli Studi di Perugia, Via G. Duranti 93, Perugia, PG, 06125, Italy; email: giuseppe.liotta@unipg.it; F. Montecchiani, Università degli Studi di Perugia, Via G. Duranti 93, Perugia, PG, 06125, Italy; email: fabrizio.montecchiani@unipg.it.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

©2019 Association for Computing Machinery.
0360-0300/2019/02-ART4 $15.00
DOI: https://doi.org/10.1145/3301281

Publication History: Received April 2018; revised September 2018; accepted October 2018