# A Survey on Graph Drawing Beyond PlanarityA 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

## 1 INTRODUCTION

In the mid-1980s, the early pioneers of graph drawing had the intuition that a drawing with too many edge crossings is harder to read than a drawing of the same graph with fewer edge crossings (see, e.g., [38, 39, 79, 211]). This intuition was later confirmed by a series of cognitive experimental studies (see, e.g., [200, 201, 225]). As a result, a large part of the existing literature on graph drawing showcases elegant algorithms and sophisticated data structures under the assumption that the input graph is planar (i.e., it admits a drawing without edge crossings). When the input graph is nonplanar, crossing minimization heuristics are used to insert a small number of dummy vertices corresponding to the edge crossings to obtain a planarization of the input graph. A crossing-free drawing of the planarization can be computed using one of the algorithms for planar graphs, and then the crossings are reinserted by removing the dummy vertices. This approach is commonly adopted and works well for graphs of relatively small size, up to a few hundred vertices and edges (see, e.g., [95, 166]). However, the technological advances of the past 20 years have generated torrents of relational data that are typically modeled as large graphs with thousands of vertices (or more). These graphs are often hard to visually analyze due, mainly, to their large size, which typically implies that a high number of edge crossings is unavoidable even by the most sophisticated planarization approaches. As a consequence, a strong consensus has developed that a new theory of nonplanar graph drawing is needed.

In this context, in the early 2000s, Mutzel ran an informal experiment with computer scientists at a Dagstuhl workshop where she presented two different drawings of the same bipartite graph: One has the minimum number of edge crossings, the second has $41\%$ more edge crossings, but it has a skewness of four, which means that all crossings can be removed by deleting four edges in the drawing. All computer scientists found the drawing with skewness four more readable than the one with fewer edge crossings. This is reported  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.

• What are the forbidden crossing configurations and the main research directions that have been studied so far?
• For each such direction, what are the main combinatorial results, and which algorithms have been designed, implemented, and experimentally evaluated?
• What are the most relevant open problems and the least explored research directions in this area?

To answer Question Q1, in Section 3 we define graph families that avoid forbidden crossing configurations, and we present a taxonomy of the main research directions in graph drawing beyond planarity. Sections 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.

## 2 BASIC DEFINITIONS ON GRAPH DRAWING

Let $G=(V,E)$ be a (finite) graph. If not otherwise specified, we assume that $G$ may contain multiple edges but no self-loops. A drawing $\Gamma$ of $G$ maps each vertex $v \in V$ to a distinct point $p_v$ of the plane and each edge $(u,v) \in E$ to a simple Jordan arc with endpoints $p_u$ and $p_v$. In notation and terminology, we make no distinction between the vertices and edges of a graph and the points and arcs representing them, respectively. Two edges of $\Gamma$ cross if they have a point in common distinct from their endpoints; this point is a crossing. We assume that an edge does not contain a vertex other than its endpoints, no two edges meet tangentially, and no three edges share a crossing. $\Gamma$ is simple if any two edges intersect in at most one point, which is either a common endpoint or an interior point where the two edges properly cross. Thus, in a simple drawing, two adjacent edges do not cross and two nonadjacent edges cross at most once.

A drawing $\Gamma$ of $G$ divides the plane into topologically connected regions, called faces, separated by edges or fragments of edges. The infinite region is called the external face; the other regions are the internal faces. Note that the boundary of a face may contain both vertices of the graph and crossings. An embedding of $G$ is an equivalence class of drawings of $G$ under homeomorphism of the plane (i.e., is a class of drawings of $G$ that define the same set of [external and internal] faces). A graph with a fixed embedding is called an embedded graph. A drawing without crossings is planar. A graph is planar if it admits a planar drawing. A planar embedding is the embedding of a planar drawing. A graph with a fixed planar embedding is an embedded planar graph, or, briefly, a plane graph. An embedding of a graph $G$ defines, for each vertex $v$ and for each crossing $c$, the clockwise order of the edges incident to $v$ and to $c$. A rotation system of $G$ is a relaxation of an embedding of $G$ in which the clockwise order of the edges is fixed only for each vertex, while no information is given about which pairs of edges cross or their order of intersection. If $G$ is planar, a planar embedding of $G$ corresponds to a rotation system plus the choice of the external face (see Figure 1).

In a polyline drawing of a graph, each edge is a chain of segments; a bend is a point where two segments of the same edge meet. A $k$-bend drawing is a polyline drawing with at most $k$ bends per edge. A 0-bend drawing is also called a straight-line drawing.

We remark that, in the literature, a drawing of a graph is sometimes called a topological graph and a straight-line drawing is sometimes called a geometric graph (see, e.g., Chapter 10 in ). In the remainder of this article, we use the pair of terms “drawing” and “topological graph” and the pair “straight-line drawing” and “geometric graph” interchangeably.

## 3 FORBIDDEN CONFIGURATIONS AND MAIN RESEARCH DIRECTIONS

In Section 3.1, we survey forbidden crossing configurations; in Section 3.2, we present a taxonomy of the most explored research directions in graph drawing beyond planarity.

### 3.1 Graph Families

The beyond-planar graph families considered in this survey are defined as graphs that admit drawings without specific forbidden configurations (i.e., sets of edges that violate some desired topological or geometric property of the edge crossings). Table 1 provides a schematic illustration of some beyond-planar graph families, among the most studied. For each family $X$, we define what a drawing of type $X$ is. A graph belongs to family $X$ if it admits a drawing of type $X$. Definitions based on first-order logic formulas have been recently proposed for many of these types of drawings .

$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 . 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  (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$ .

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

$(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 .

$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$ ; 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” . 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  (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$.

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. , 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.  they are called LAC$_\alpha$ drawings, and in Dujmovic et al.  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 . 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  and has inspired both theoretical  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 .

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

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

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

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

## 4 EDGE DENSITY

The problem of establishing the maximum number of edges in a given type of beyond-planar graph has been extensively studied in the literature. We recall some basic definitions needed to describe the main results in this research direction. Let $\mathcal {F}$ be a beyond-planar graph family and let $G$ be an $n$-vertex graph in $\mathcal {F}$. $G$ is maximal (in $\mathcal {F}$) if adding any edge to $G$ leads to a graph that is not in $\mathcal {F}$. $G$ is maximally dense if it has the maximum number of edges over all $n$-vertex graphs in $\mathcal {F}$. The edge density of $G$ is the ratio between its number of edges and its number of vertices. $G$ is optimal if it has the maximum edge density over all graphs of $\mathcal {F}$. Note that an optimal graph is also maximally dense, while the converse may not be true; similarly, a maximally dense graph is maximal, but there are maximal graphs that are not maximally dense; Figure 4(a) shows a maximally dense 1-planar graph with 5 vertices that is not optimal; Figure 4(b) shows a 1-planar graph with 12 vertices that is maximal but not optimal, and Figure 4(c) shows an optimal 1-planar graph with 12 vertices.

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 , 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$  and $6n-12$ , respectively. For $k \gt 4$, the best known upper bound is $3,81\sqrt {k}\,n$ , which improves a previous bound of $4.108\sqrt {k}\,n$ . Lower bounds on the edge density of maximal 1-planar graphs are given in Brandenburg et al. . 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 . 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. .

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$ $3n-9$ otherwise
IC-planar $3.25n - 6$ NIC-planar $3.6n - 7.2$ 2-planar $5n - 10$ 3-planar $5.5(n - 2)$ $+$ 
4-planar $6n - 12$ $+$ 
$k$-planar $(k \ge 5)$ $3.81\sqrt {k}\,n$ $\times$ 
3-quasi planar $6.5n-20$ $+$ 
4-quasi planar $72(n-2)$ $\times$ 
$k$-quasi planar $(k \ge 5)$ $c_k n \log n$ $\bigcirc$ 
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$ 
radial-$(k,l)$-grid-free $8 \cdot 24^lkn$ $\times$ 
natural-$k$-grid-free $O(n \log ^{4k-6} n)$ $\bigcirc$ 
straight-line natural-$k$-grid-free $O(kn \log ^2 n)$ $\bigcirc$ 
fan-crossing-free $4n-8$ straight-line fan-crossing-free $4n-9$ $k$-fan-crossing-free ($k \ge 3$) $3(k-1)(n-2)$ $\times$ 
fan-planar $5n-10$ straight-line RAC $4n - 10$ straight-line ACE$\alpha$ $3(3n-6)$ $\times$ 
straight-line ACL$\alpha$ $\frac{\pi }{\alpha }(3n-6)$ $\times$ 
1-gap-planar $5n-10$ $k$-gap-planar ($k\gt 1$) $O(\sqrt {k}n)$ $\times$ 
straight-line (3-length-path)-sif $O(n \log n)$ $\bigcirc$ 
straight-line (5-length-path)-sif $O(n\log n/\log \log n)$ $\bigcirc$ 
straight-line (4-length-cycle)-sif $O(n^{8/5}$) $\bigcirc$ 
planarly-connected $c\,n$ $\times$ 

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$  and $72(n-2)$ , 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$ . 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 . A fan-crossing-free graph has at most $4n-8$ edges, and at most $4n-9$ if the edges are drawn as straight lines . 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 .

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$ , 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 . Dujmovic et al. provide an alternative proof of this bound, based on charging techniques . 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 . 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 , while natural-$k$-grid-free graphs have $O(n \log ^{4k-6} n)$ edges . 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 , while straight-line (4-length-cycle)-sif graphs have $O(n^{8/5})$ edges . Finally, planarly connected graphs have $c \, n$ edges, where $c$ is a constant . 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 . Concerning Problem 2, recent papers discuss the edge density of (not necessarily simple) 3-planar graphs [46, 47].

Another research direction is concerned with providing lower bounds on the number of edges of maximal beyond-planar graphs. This type of question is mostly unexplored; results are known for 1- and 2-planar graphs [30, 62]. We suggest the following.

Find a lower bound on the edge density of maximal straight-line RAC graphs.

## 5 RECOGNITION

Given a graph $G$ and a family $\mathcal {F}$ of beyond-planar graphs, the recognition problem studies the complexity of deciding whether a graph $G$ belongs to $\mathcal {F}$. As we have seen in Section 4, several families of beyond-planar graphs are sparse, and this may suggest a correspondence with planar graphs, which can be recognized in linear time . 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 . 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 . Recognizing 1-planar graphs remains NP-complete also when the input graph comes with a fixed rotation system, which must be preserved . 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 ; the testing algorithm exploits a structural characterization of optimal 1-planar graphs . Recently, a similar structural characterization has been proved for optimal 2-planar and optimal 3-planar graphs , 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., ). We refer the reader to the annotated bibliography by Kobourov et al. for further references . 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 , $O(\sqrt {kn})$ treewidth and $O(k)$ layered treewidth , and bounded expansion  (see  for more results).

Recognizing skewness-$k$ graphs is NP-complete in the general case , but the problem can be solved in $O(n)$ time for any fixed value of $k$ (i.e., it is FPT with parameter $k$) .

The set of 1-apex graphs is closed under the operation of taking minors , hence these graphs have a forbidden graph characterization by the Robertson-Seymour theorem . However, the set of obstructions for these graphs has only been partially discovered . Recognizing $n$-vertex $k$-apex graphs is NP-complete , but there is an $O(n)$-time algorithm if $k$ is a fixed constant .

Recognizing fan-planar graphs is NP-complete , even for a fixed rotation system . The same holds for 1-gap-planar graphs .

Recognizing straight-line RAC drawable graphs is NP-hard in general , but can be solved in linear time for complete bipartite graphs . 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 . 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 . 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 . 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 
1-planar bounded cyclomatic number or treedepth $O(n)$ 
1-planar fixed rotation system NP-complete 
1-planar skewness-1 NP-complete 
optimal 1-planar $O(n)$ 
skewness-$k$ NP-complete 
skewness-$k$ bounded $k$ $O(n)$ 
$k$-apex NP-complete 
$k$-apex bounded $k$ $O(n)$ 
fan-planar NP-complete 
fan-planar fixed rotation system NP-complete 
straight-line RAC NP-hard 
staight-line 1-planar RAC NP-hard 
1-gap-planar NP-complete 
1-gap-planar fixed rotation system NP-complete 

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  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 , but the following question is still open.

What is the complexity of recognizing $k$-bend RAC drawable graphs, for $k \in \lbrace 1,2\rbrace$?

A characterization of the graphs that admit an $\alpha$-SHPED is unknown.

What is the complexity of deciding whether a graph admits an $\alpha$-SHPED? In particular, what is the complexity for $\alpha = \frac{1}{4}$?

## 6 RELATIONSHIPS BETWEEN GRAPH FAMILIES

Some families of beyond-planar graphs have similar edge densities or exhibit similar structural and topological properties. In these cases, it is natural to ask whether they have some inclusion relationships. In what follows, we survey the main results concerning this research direction.

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

Brandenburg et al. study the RAC drawability of the 1-planar graphs with independent pairs of crossing edges (the IC-planar graphs) . 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 .

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 : 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 : 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$ . 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 . 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 .

$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 . 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 . 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 , the following questions on the combinatorial relationships between $k$-planarity and $h$-quasi planarity remain unanswered.

Is a $k$-planar graph also $k$-quasi planar? For sufficiently large values of $k$, is every $k$-planar graph $f(k)$-quasi planar, for some function $f(k)=o(k)$?

Finally, the relationships between some pairs of beyond-planar graph families have not yet been studied. For example:

What is the relationship between $k$-gap planar and fan-planar graphs, for $k \ge 1$?

## 7 QUALITY METRICS

While beyond-planar graphs focus on properties of edge crossings, other quality metrics have been extensively used in the literature to produce geometric representations of graphs that are clear and pleasing for the reader. For example, in a polyline drawing, the vertices of the graph are points and the edges are polylines whose complexity should be kept as low as possible to assist the reader. A common measure to capture the edge complexity of a polyline drawing is the number of bends per edge. Results concerning the edge complexity of beyond-planar graphs are presented in Section 7.1. Other drawing paradigms, like visibility representations and contact representations, convey edges as horizontal or vertical segments and shift the complexity to the vertices, which are drawn using more general shapes such as bars, rectangles, or polygons. We survey work related to the vertex complexity of beyond-planar graphs in Section 7.2. Finally, a common goal for polyline drawings is to use integer coordinates for vertices and bend points and to fit the drawing into a small bounding box, in order to display the drawing onto a screen with finite resolution. In particular, the area of a polyline drawing is the area occupied by its bounding box (i.e., by the minimum axis-aligned box containing the drawing). If the bounding box has side lengths $X-1$ and $Y-1$, we say that the drawing has area $X \times Y$. Results concerning the area requirement of beyond-planar graphs in combination with edge/vertex complexity requirements are considered in Sections 7.1 $-$ 7.2. Section 7.3 discusses area-crossings tradeoffs for beyond-planar drawings of planar graphs.

### 7.1 Edge Complexity

Stretchability. The famous Fáry's theorem states that every plane graph is stretchable; that is, it has an embedding-preserving straight-line drawing  (this result was also independently proved by Wagner  and Stein ). So far, little effort has been made to extend this result to beyond-planar graphs. In 1988, Thomassen initiated the study of the stretchability problem for 1-plane graphs . 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  (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 . 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 . 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 . 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.

Table 5. Stretchability
Graph Family Restrictions Complexity of testing Refs
1-planar fixed embedding $O(n)$ 
1-planar fixed pairs of crossing edges $O(n)$ 
maximal skewness-1 fixed embedding $O(n)$ 

Polyline drawings. As reported in the paragraph about stretchability, the class of 1-plane graphs admitting a straight-line drawing has been characterized , and there exist 1-plane graphs such that every embedding-preserving straight-line drawing requires an exponential area . 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 ; 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)$ ; 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 . 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 , 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 . 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. . In recent papers, Argyriou et al.  and Kindermann et al.  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).

The edge complexity of RAC drawings has also been studied regardless of the number of crossings per edge. Every $n$-vertex graph has a 3-bend RAC drawing in $O(n^4)$ area , while 1-bend and 2-bend RAC drawable graphs have at most $5.5n-11$ edges  or $74.2n$ edges , respectively. If we allow up to four bends per edge, every graph can be drawn RAC in $O(n^3)$ area . For graphs with bounded vertex degree, we have the following results : $(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 .

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)$ 
NIC-plane RAC ? $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(n^2)$ 
1-planar $\Omega (2^n)$ ? $O(n^4)$ $O(n^4)$ $O(n^4)$ , 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)$ 

$\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 . 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 . The algorithm is based on a characterization that extends the set of obstructions used by Thomassen to characterize the stretchable 1-plane graphs . 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 . Di Giacomo et al. prove that every 1-plane graph admits an embedding-preserving ortho-polygon visibility representation . 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 .

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 .

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 . 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 . 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
Graph Family RVR B1VR OPVR LVR ZPR BCR LCR Refs
IC-planar     ? ?  


 
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 . 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.,  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 . 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 , 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 . Analogous results hold for other quality metrics such as uniform edge length and angular resolution . In addition, every planar graph admits an ACL$\alpha$ drawing with two bends per edge in $O(n^\frac{5}{3})$ area , and every planar graph with vertex-degree at most $\Delta$ admits a 4-bend RAC drawing in $O(n \sqrt {\Delta n})$ area . 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 . 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 ). 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 .

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.  with results on the track number of planar graphs , 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 . 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 . 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) . 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 . 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 .

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 .

## 8 CONSTRAINTS

Several papers concentrate on beyond-planar drawings where the vertices and/or the edges have additional geometric constraints. We discuss the main scenarios studied in the literature.

### 8.1 Vertices on Lines, Circles, and External Boundary

The study of graph layouts in which vertices are placed on a given set of horizontal lines, often called layers, or on a set of concentric circles, has a well-established tradition in graph drawing [95, 102].

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  used to draw graphs on multiple horizontal layers.

Characterizations for those graphs that admit either 2-layer RAC drawings , or 2-layer 1-planar drawings , or 2-layer fan-planar drawings  are known; all of them can be regarded as generalizations of caterpillars, the class of 2-layer planar drawable graphs . The upper bounds on the edge density of these graph families are reported in Table 9. In particular, the optimal 2-layer 1-planar graphs coincide with the optimal 2-layer RAC graphs and have $1.5n - 2$ edges, where $n$ is the number of vertices of the graph. They are called ladders and consist of two paths of the same length $\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}$ .

Table 9. Density for Constrained Families
Graph Family Max. Num. Edges Tight Refs
2-layer 1-planar $1.5n-2$ 2-layer RAC $1.5n-2$ 2-layer fan-planar $2n-4$ outer 1-planar $2.5n-4$ [29, 115]
outer fan-planar $3n-5$ 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$ Table 10. Recognition for Constrained Families
Graph Family Complexity Refs
2-layer RAC $O(n)$ 
2-connected 2-layer fan-planar $O(n)$ 
outer 1-planar $O(n)$ [29, 155]
full outer 2-planar $O(n)$ 
maximal outer fan-planar $O(n)$ 
circular RAC $O(n)$ 
upward RAC NP-hard 
simultaneous RAC NP-hard 
$k$-SEFE NP-complete 
straight-line point-set RAC NP-hard 

From the algorithmic point of view, there exist linear-time testing and drawing algorithms for 2-layer RAC graphs  and for 2-connected 2-layer fan-planar graphs , while the complexity of recognizing 2-layer fan-planar graphs when the graph is only 1-connected is still open. For 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 . 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 .

$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., ); also, a 2-page drawing is sometimes called a permutation representation (see, e.g., ) or linear drawing (see, e.g., ), while a 1-page drawing is also called an arc diagram (see, e.g., ). 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 ).

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 . 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 , 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})$ ), then the same is true for $k$-planar graphs .

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 . 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 ). 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 . 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 . 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 . 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]  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. , it is also proved that planar graphs and outer quasi planar graphs are incomparable classes under containment, while in Geneson et al.  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. . 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 . Di Giacomo et al. study how to draw outer 1-planar graphs with a small number of edge slopes . They prove that every outer 1-planar graph admits an outer 1-planar straight-line drawing that uses $O(\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., ). 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  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 . Also, although a planar digraph has an upward planar drawing if and only if it has a straight-line upward planar drawing , 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$ .

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 , and since then it has been widely studied (see, e.g.,  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 , 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 , while every pair of planar graphs has an SRE with at most six bends per edge . 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 . 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 . 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 .

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., ) or not (see, e.g., ). 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 . 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  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 .

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

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 . One may wonder whether a beyond-planar version of this problem is more likely to have a positive answer. In particular, we ask the following.

Is there a set $S$ of $n$ points in the plane such that every planar graph with $n$ vertices admits an $f(n)$-planar point-set embedding on $S$ with straight-line edges such that $f(n) \in o(n)$?

## 9 IMPLEMENTATIONS AND EXPERIMENTS

The applied research in graph drawing beyond planarity has been mainly pursued along two directions: $(i)$ Cognitive experiments aimed to better understand the impact of some types of forbidden configurations on the capability of a user to execute visualization-based analysis tasks. $(ii)$ The implementation and experimentation of algorithms to compute beyond-planar graph drawings and the development of visualization systems for real-world application domains. We briefly discuss the contributions in these two directions.

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

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 . An $\alpha$-SHPED of a straight-line drawing is immediately defined for a fixed value of $\alpha$ . 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 . 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 . 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 .

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  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  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.  propose another force-directed algorithm that computes drawings with high crossing and vertex angle resolution. In a recent paper, Bekos et al.  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 . 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 . 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 . 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 .

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 . 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 . 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.  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 . We propose to study the following problem, for which some efforts have been limited so far to RAC drawings .

Design heuristics that reduce the number of forbidden crossing configurations in 2-layered drawings of bipartite graphs and perform a user study to compare the obtained drawings with those computed by means of 2-layer crossing minimization heuristics.

It would be interesting to analyze the practical impact that the various forbidden edge crossing configurations have in real-world drawings. For example, one could consider a large benchmark of real-world graphs with various sizes, draw these graphs by using different algorithms (e.g., force-directed algorithms), and then analyze the frequency of occurrence of each forbidden edge crossing configuration in these drawings. We summarize this problem as follows.

Analyze the impact of various forbidden edge crossing configurations in a large set of real-world drawings.

Finally, a very promising research direction is to perform new experiments and develop new theories on graph drawing beyond planarity based on the following user-centered approach: (i) Develop theories on how people read drawings based on HCI experiments; (ii) define optimization criteria on the edge crossings and their configurations; (iii) design combinatorial models and efficient algorithms; and (iv) experimentally verify the efficiency and effectiveness of the algorithms with new experiments that may lead to refining the model and/or the optimization goals.

## 10 CONCLUSION

The treatment of edge crossings in graph visualization embraces other topics that have not been discussed in the previous sections. Although these topics are not properly recognized as part of the literature on graph drawing beyond planarity, recent works have established connections with beyond-planar graph families, which highlight new and interesting research directions.

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 ). However, for 2-layer RAC drawable graphs, the problem can be solved efficiently , 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.  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 . Following this example, other families can be conceived and studied.

## ACKNOWLEDGMENTS

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

## REFERENCES

• Eyal Ackerman. 2009. On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discr. Comput. Geom. 41, 3 (2009), 365–375.
• Eyal Ackerman. 2014. A note on 1-planar graphs. Discr. Appl. Math. 175 (2014), 104–108.
• Eyal Ackerman. 2015. On topological graphs with at most four crossings per edge. CoRR abs/1509.01932 (2015).
• Eyal Ackerman, Jacob Fox, János Pach, and Andrew Suk. 2014. On grids in topological graphs. Comput. Geom. 47, 7 (2014), 710–723.
• Eyal Ackerman, Radoslav Fulek, and Csaba D. Tóth. 2010. On the size of graphs that admit polyline drawings with few bends and crossing angles. In Proceedings of the GD 2010 (LNCS), Vol. 6502. Springer, 1–12. https://link.springer.com/chapter/10.1007/978-3-642-18469-7_1.
• Eyal Ackerman, Radoslav Fulek, and Csaba D. Tóth. 2012. Graphs that admit polyline drawings with few crossing angles. SIAM J. Discr. Math. 26, 1 (2012), 305–320.
• Eyal Ackerman, Bal&acedil;zs Keszegh, and Mate Vizer. 2018. On the size of planarly connected crossing graphs. J. Graph Algorithms Appl. 22, 1 (2018), 11–22.
• Eyal Ackerman and Gábor Tardos. 2007. On the maximum number of edges in quasi-planar graphs. J. Comb. Theory, Ser. A 114, 3 (2007), 563–571.
• Jin Akiyama and Noga Alon. 1989. Disjoint simplices and geometric hypergraphs. Ann. New York Acad. Sci. 555, 1 (1989), 1–3.
• Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. 2013. Straight-line grid drawings of 3-connected 1-planar graphs. In Proceedings of the GD 2013 (LNCS), Vol. 8242. Springer, 83–94. https://link.springer.com/chapter/10.1007/978-3-319-03841-4_8.
• Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. 2015. On the book thickness of 1-planar graphs. CoRR abs/1510.05891 (2015).
• Md. Jawaherul Alam, William S. Evans, Stephen G. Kobourov, Sergey Pupyrev, Jackson Toeniskoetter, and Torsten Ueckerdt. 2015. Contact representations of graphs in 3D. In Proceedings of the WADS 2015 (LNCS), Vol. 9214. Springer, 14–27. https://link.springer.com/chapter/10.1007%2F978-3-319-21840-3_2.
• Noga Alon and Paul Erdös. 1989. Disjoint edges in geometric graphs. Discr. Comput. Geom. 4 (1989), 287–290.
• Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, and Ignaz Rutter. 2017. On the relationship between $k$-planar and $k$-quasi-planar graphs. In Proceedings of theWG 2017 (LNCS), Vol. 10520. Springer, 59–74. https://link.springer.com/chapter/10.1007%2F978-3-319-68705-6_5.
• Patrizio Angelini, Michael A. Bekos, Henry Förster, and Michael Kaufmann. 2018. On RAC drawings of graphs with one bend per edge. CoRR abs/1808.10470 (2018). Accepted at GD 2018. https://link.springer.com/chapter/10.1007%2F978-3-030-04414-5_9.
• Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, and Thomas Schneck. 2018. 1-fan-bundle-planar drawings of graphs. Theor. Comput. Sci. 723 (2018), 23–50.
• Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, and Fabrizio Montecchiani. 2017. 3D visibility representations of 1-planar graphs. In Proceedings of the GD 2017 (LNCS), Vol. 10692. Springer, 102–109. https://link.springer.com/chapter/10.1007%2F978-3-319-73915-1_9.
• Patrizio Angelini, Luca Cittadini, Walter Didimo, Fabrizio Frati, Giuseppe Di Battista, Michael Kaufmann, and Antonios Symvonis. 2011. On the perspectives opened by right angle crossing drawings. J. Graph Algorithms Appl. 15, 1 (2011), 53–78.
• Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli. 2015. Relaxing the constraints of clustered planarity. Comput. Geom. 48, 2 (2015), 42–75.
• Patrizio Angelini, Giuseppe Di Battista, Walter Didimo, Fabrizio Frati, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, and Anna Lubiw. 2012. Large angle crossing drawings of planar graphs in subquadratic area. In Proceedings of the EGC 2011 (LNCS), Vol. 7579. Springer, 200–209. https://link.springer.com/chapter/10.1007%2F978-3-642-34191-5_19.
• Patrizio Angelini, Peter Eades, Seok-Hee Hong, Karsten Klein, Stephen G. Kobourov, Giuseppe Liotta, Alfredo Navarra, and Alessandra Tappini. 2018. Turning cliques into paths to achieve planarity. CoRR abs/1808.08925 (2018). Accepted at GD 2018. https://link.springer.com/chapter/10.1007%2F978-3-030-04414-5_5.
• Patrizio Angelini, Markus Geyer, Michael Kaufmann, and Daniel Neuwirth. 2012. On a tree and a path with no geometric simultaneous embedding. J. Graph Algorithms Appl. 16, 1 (2012), 37–83.
• Arthur Appel, F. James Rohlf, and Arthur J. Stein. 1979. The haloed line effect for hidden line elimination. In Proceedings of the SIGGRAPH 1979. ACM, 151–157. https://dl.acm.org/citation.cfm?doid=800249.807437.
• Evmorfia N. Argyriou, Michael A. Bekos, Michael Kaufmann, and Antonios Symvonis. 2013. Geometric RAC simultaneous drawings of graphs. J. Graph Algorithms Appl. 17, 1 (2013), 11–34.
• Evmorfia N. Argyriou, Michael A. Bekos, and Antonios Symvonis. 2012. The straight-line RAC drawing problem is NP-hard. J. Graph Algorithms Appl. 16, 2 (2012), 569–597.
• Evmorfia N. Argyriou, Michael A. Bekos, and Antonios Symvonis. 2013. Maximizing the total resolution of graphs. Comput. J. 56, 7 (2013), 887–900.
• Evmorfia N. Argyriou, Sabine Cornelsen, Henry Förster, Michael Kaufmann, Martin Nöllenburg, Yoshio Okamoto, Chrysanthi N. Raftopoulou, and Alexander Wolff. 2018. Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity. CoRR abs/1808.10536 (2018). Accepted at GD 2018. https://link.springer.com/chapter/10.1007%2F978-3-030-04414-5_36.
• Karin Arikushi, Radoslav Fulek, Balázs Keszegh, Filip Moric, and Csaba D. Tóth. 2012. Graphs that admit right angle crossing drawings. Comput. Geom. 45, 4 (2012), 169–177.
• Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. 2016. Outer 1-planar graphs. Algorithmica 74, 4 (2016), 1293–1320.
• Christopher Auer, Franz-Josef Brandenburg, Andreas Gleißner, and Kathrin Hanauer. 2012. On sparse maximal 2-planar graphs. In Graph Drawing (LNCS), Vol. 7704. Springer, 555–556. https://link.springer.com/chapter/10.1007%2F978-3-642-36763-2_50.
• Christopher Auer, Franz J. Brandenburg, Andreas Gleißner, and Josef Reislhuber. 2015. 1-planarity of graphs with a rotation system. J. Graph Algorithms Appl. 19, 1 (2015), 67–86.
• S. Avital and H. Hanani. 1966. Graphs. Gilyonot Lematematika 3 (1966), 2–8.
• Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. 2017. NIC-planar graphs. Discr. Appl. Math. 232 (2017), 23–40.
• Sang Won Bae, Jean-François Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth. 2018. Gap-planar graphs. Theor. Comput. Sci. 745 (2018), 36–52.
• Michael J. Bannister, Sergio Cabello, and David Eppstein. 2018. Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 22, 1 (2018), 23–49.
• Imre Bárány and Günter Rote. 2005. Strictly convex drawings of planar graphs. CoRR abs/cs/0507030 (2005).
• Vladimir Batagelj, Franz-Josef Brandenburg, Walter Didimo, Giuseppe Liotta, Pietro Palladino, and Maurizio Patrignani. 2011. Visual analysis of large graphs using (X, Y)-clustering and hybrid visualizations. IEEE Trans. Vis. Comput. Graph. 17, 11 (2011), 1587–1598.
• Carlo Batini, L. Furlani, and Enrico Nardelli. 1985. What is a good diagram? A pragmatic approach. In Proceedings of the Fourth International Conference on Entity-Relationship Approach: The Use of {ER} Concept in Knowledge Representation. IEEE Computer Society and North-Holland, 312--319.
• Carlo Batini, Enrico Nardelli, and Roberto Tamassia. 1986. A layout algorithm for data flow diagrams. IEEE Trans. Software Eng. 12, 4 (1986), 538–546.
• Richard A. Becker, Stephen G. Eick, and Allan R. Wilks. 1995. Visualizing network data. IEEE Trans. Vis. Comput. Graph. 1, 1 (1995), 16–28.
• Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann, and Chrysanthi N. Raftopoulou. 2017. The book thickness of 1-planar graphs is constant. Algorithmica 79, 2 (2017), 444–465.
• Michael A. Bekos, Sabine Cornelsen, Luca Grilli, Seok-Hee Hong, and Michael Kaufmann. 2017. On the recognition of fan-planar and maximal outer-fan-planar graphs. Algorithmica 79, 2 (2017), 401–427.
• Michael A. Bekos, Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, and Chrysanthi N. Raftopoulou. 2018. Edge partitions of optimal 2-plane and 3-plane graphs. In Proceedings of the WG 2018 (LNCS), Vol. 11159. Springer, 27–39. https://link.springer.com/chapter/10.1007%2F978-3-030-00256-5_3.
• Michael A. Bekos, Walter Didimo, Giuseppe Liotta, Saeed Mehrabi, and Fabrizio Montecchiani. 2017. On RAC drawings of 1-planar graphs. Theor. Comput. Sci. 689 (2017), 48–57.
• Michael A. Bekos, Henry Förster, Christian Geckeler, Lukas Holländer, Michael Kaufmann, Amadäus M. Spallek, and Jan Splett. 2018. A heuristic approach towards drawings of graphs with high crossing resolution. CoRR abs/1808.10519 (2018). Accepted at GD 2018. https://link.springer.com/chapter/10.1007%2F978-3-030-04414-5_19.
• Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou. 2016. On the density of non-simple 3-planar graphs. In Proceedings of the GD 2016 (LNCS), Vol. 9801. Springer, 344–356. https://link.springer.com/chapter/10.1007%2F978-3-319-50106-2_27.
• Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou. 2017. On optimal 2- and 3-planar graphs. In Proceedings of the SoCG 2017 (LIPIcs), Vol. 77. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 16:1–16:16. http://drops.dagstuhl.de/opus/volltexte/2017/7230/.
• Michael A. Bekos, Thomas C. van Dijk, Philipp Kindermann, and Alexander Wolff. 2016. Simultaneous drawing of planar graphs with right-angle crossings and few bends. J. Graph Algorithms Appl. 20, 1 (2016), 133–158.
• F. Bernhart and P. C. Kainen. 1979. The book thickness of a graph. J. Combin. Theory Ser. B 27 (1979), 320–331.
• Paola Bertolazzi, Giuseppe Di Battista, and Walter Didimo. 2002. Quasi-upward planarity. Algorithmica 32, 3 (2002), 474–506.
• Therese C. Biedl, Giuseppe Liotta, and Fabrizio Montecchiani. 2018. Embedding-preserving rectangle visibility representations of nonplanar graphs. Discrete and Computational Geometry 60, 2 (2018), 345--380. https://doi.org/10.1007/s00454-017-9939-y.
• Carla Binucci, Markus Chimani, Walter Didimo, Martin Gronemann, Karsten Klein, Jan Kratochvíl, Fabrizio Montecchiani, and Ioannis G. Tollis. 2017. Algorithms and characterizations for 2-layer fan-planarity: From caterpillar to stegosaurus. J. Graph Algorithms Appl. 21, 1 (2017), 81–102.
• Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Antonios Symvonis, and Ioannis G. Tollis. 2015. Fan-planarity: Properties and complexity. Theor. Comput. Sci. 589 (2015), 76–86.
• Carla Binucci, Emilio Di Giacomo, Md. Iqbal Hossain, and Giuseppe Liotta. 2018. 1-page and 2-page drawings with bounded number of crossings per edge. Eur. J. Comb. 68 (2018), 24–37.
• Carla Binucci, Walter Didimo, and Maurizio Patrignani. 2014. Upward and quasi-upward planarity testing of embedded mixed graphs. Theor. Comput. Sci. 526 (2014), 75–89.
• Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, and Alessandra Tappini. 2016. Partial edge drawing: Homogeneity is more important than crossings and ink. In Proceedings of the IISA. IEEE, 1–6. https://ieeexplore.ieee.org/document/7785427.
• Thomas Bläsius, Stephen G. Kobourov, and Ignaz Rutter. 2013. Simultaneous embedding of planar graphs. In Handbook on Graph Drawing and Visualization., Roberto Tamassia (Ed.). Chapman and Hall/CRC, 349–381.
• R Bodendiek, H Schumacher, and K Wagner. 1983. Bemerkungen zu einem Sechsfarbenproblem von G. Ringel. Abhandlungen Aus Dem Mathematischen Seminar Der Universitaet Hamburg 53, 1 (1983), 41–52.
• Béla Bollobás. 1978. Extremal Graph Theory. Academic Press, New York.
• Romain Bourqui, David Auber, and Patrick Mary. 2007. How to draw clustered weighted graphs using a multilevel force-directed graph drawing algorithm. In Proceedings of the 11th International Conference on Information Visualisation (IV'07). IEEE, 757–764. https://doi.org/10.1109/IV.2007.65.
• Franz Brandenburg. 2018. Recognizing IC-planar and NIC-planar graphs. J. Graph Algorithms Appl. 22, 2 (2018), 239–271.
• Franz-Josef Brandenburg, David Eppstein, Andreas Gleißner, Michael T. Goodrich, Kathrin Hanauer, and Josef Reislhuber. 2012. On the density of maximal 1-planar graphs. In Proceedings of the GD 2012 (LNCS), Vol. 7704. Springer, 327–338. https://link.springer.com/chapter/10.1007%2F978-3-642-36763-2_29.
• Franz J. Brandenburg. 2014. 1-visibility representations of 1-planar graphs. J. Graph Algorithms Appl. 18, 3 (2014), 421–438.
• Franz J. Brandenburg. 2018. A first order logic definition of beyond-planar graphs. J. Graph Algorithms Appl. 22, 1 (2018), 51–66.
• Franz J. Brandenburg. 2018. On fan-crossing and fan-crossing free graphs. Inf. Process. Lett. 138 (2018), 67–71.
• Franz J. Brandenburg. 2018. Recognizing optimal 1-planar graphs in linear time. Algorithmica 80, 1 (2018), 1–28.
• Franz J. Brandenburg, Walter Didimo, William S. Evans, Philipp Kindermann, Giuseppe Liotta, and Fabrizio Montecchiani. 2016. Recognizing and drawing IC-planar graphs. Theor. Comput. Sci. 636 (2016), 1–16.
• Peter Braß, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan Ismailescu, Stephen G. Kobourov, Anna Lubiw, and Joseph S. B. Mitchell. 2007. On simultaneous planar graph embeddings. Comput. Geom. 36, 2 (2007), 117–130.
• Peter Brass, Gyula Károlyi, and Pavel Valtr. 2003. A Turán-type extremal theorey of convex geometric graphs. Discr. Comput. Geom. 25 (2003), 275–300.
• Peter Braß, William O. J. Moser, and János Pach. 2005. Research Problems in Discrete Geometry. Springer.
• Till Bruckdorfer, Sabine Cornelsen, Carsten Gutwenger, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg, and Alexander Wolff. 2017. Progress on partial edge drawings. J. Graph Algorithms Appl. 21, 4 (2017), 757–786.
• Till Bruckdorfer and Michael Kaufmann. 2012. Mad at edge crossings? Break the edges!. In Proceedings of the FUN 2012 (LNCS), Vol. 7288. Springer, 40–50. https://link.springer.com/chapter/10.1007%2F978-3-642-30347-0_7.
• Till Bruckdorfer, Michael Kaufmann, and Andreas Lauer. 2015. A practical approach for $1/4$-SHPEDs. In Proceedings of the IISA 2015. IEEE, 1–6. https://ieeexplore.ieee.org/document/7387994?arnumber=7387994.
• Till Bruckdorfer, Michael Kaufmann, and Fabrizio Montecchiani. 2014. 1-bend orthogonal partial edge drawing. J. Graph Algorithms Appl. 18, 1 (2014), 111–131.
• Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel. 2013. Crossings and planarization. In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall/CRC, 43–85.
• Sergio Cabello and Bojan Mohar. 2011. Crossing number and weighted crossing number of near-planar graphs. Algorithmica 60, 3 (2011), 484–504.
• Sergio Cabello and Bojan Mohar. 2013. Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput. 42, 5 (2013), 1803–1829.
• Vasilis Capoyleas and János Pach. 1992. A turán-type theorem on chords of a convex polygon. J. Comb. Theory, Ser. B 56, 1 (1992), 9–15.
• Marie-Jose Carpano. 1980. Automatic display of hierarchized graphs for computer-aided decision analysis. IEEE Trans. Systems, Man, and Cybernetics 10, 11 (1980), 705–715.
• Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler, and Alexander Wolff. 2017. Beyond outerplanarity. In Proceedings of the GD 2017 (LNCS), Vol. 10692. Springer, 546–559. https://link.springer.com/chapter/10.1007%2F978-3-319-73915-1_42.
• Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. 2018. Compact drawings of 1-planar graphs with right-angle crossings and few bends. CoRR abs/1806.10044 (2018). Accepted at GD 2018.
• Otfried Cheong, Sariel Har-Peled, Heuna Kim, and Hyo-Sil Kim. 2015. On the number of edges of fan-crossing free graphs. Algorithmica 73, 4 (2015), 673–695.
• Markus Chimani, Carsten Gutwenger, Petra Mutzel, and Christian Wolf. 2009. Inserting a vertex into a planar graph. In Proceedings of the ACM-SIAM SoDA 2009. SIAM, 375–383. https://dl.acm.org/citation.cfm?id=1496770.1496812.
• Markus Chimani and Petr Hlinený. 2016. Inserting multiple edges into a planar graph. In Proceedings of the SoCG 2016 (LIPIcs), Vol. 51. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1–30:15. http://drops.dagstuhl.de/opus/volltexte/2016/5922/.
• Pier Francesco Cortese and Giuseppe Di Battista. 2005. Clustered planarity. In Proceedings of the ACM SoCG 2005. ACM, 32–34. https://dl.acm.org/citation.cfm?doid=1064092.1064093.
• J. Czap and P. Šugerek. 2017. Drawing graph joins in the plane with restrictions on crossings. Filomat 31, 2 (2017), 363–370.
• Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani. 2018. Computing NodeTrix representations of clustered graphs. J. Graph Algorithms Appl. 22, 2 (2018), 139–176.
• Hubert de Fraysseix, János Pach, and Richard Pollack. 1990. How to draw a planar graph on a grid. Combinatorica 10, 1 (1990), 41–51.
• Alice M. Dean, William S. Evans, Ellen Gethner, Joshua D. Laison, Mohammad Ali Safari, and William T. Trotter. 2007. Bar $k$-visibility graphs. J. Graph Algorithms Appl. 11, 1 (2007), 45–59.
• Hooman Reisi Dehkordi and Peter Eades. 2012. Every outer-1-plane graph has a right angle crossing drawing. Int. J. Comput. Geometry Appl. 22, 6 (2012), 543–558.
• Hooman Reisi Dehkordi, Peter Eades, Seok-Hee Hong, and Quan Hoang Nguyen. 2016. Circular right-angle crossing drawings in linear time. Theor. Comput. Sci. 639 (2016), 26–41.
• Erik D. Demaine and Mohammad Taghi Hajiaghayi. 2004. Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40, 3 (2004), 211–215.
• Almut Demel, Dominik Dürrschnabel, Tamara Mchedlidze, Marcel Radermacher, and Lasse Wulf. 2018. A greedy heuristic for crossing-angle maximization. CoRR abs/1807.09483 (2018). Accepted at GD 2018. https://link.springer.com/chapter/10.1007%2F978-3-030-04414-5_20.
• Giuseppe Di Battista, Walter Didimo, and A. Marcandalli. 2002. Planarization of clustered graphs. In Proceedings of the GD 2001 (LNCS), Vol. 2265. Springer, 60–74. https://link.springer.com/chapter/10.1007%2F3-540-45848-4_5.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. 1999. Graph Drawing. Prentice Hall, Upper Saddle River, NJ.
• Giuseppe Di Battista and Roberto Tamassia. 1988. Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61 (1988), 175–198.
• Giuseppe Di Battista, Roberto Tamassia, and Ioannis G. Tollis. 1992. Area requirement and symmetry display of planar upward drawings. Discr. Comput. Geom. 7 (1992), 381–401.
• Emilio Di Giacomo, Walter Didimo, Peter Eades, and Giuseppe Liotta. 2014. 2-layer right angle crossing drawings. Algorithmica 68, 4 (2014), 954–997.
• Emilio Di Giacomo, Walter Didimo, William S. Evans, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani, and Stephen K. Wismath. 2018. Ortho-polygon visibility representations of embedded graphs. Algorithmica 80, 8 (2018), 2345–2383.
• Emilio Di Giacomo, Walter Didimo, William S. Evans, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani, and Stephen K. Wismath. 2018. New results on edge partitions of 1-plane graphs. Theor. Comput. Sci. 713 (2018), 78–84.
• Emilio Di Giacomo, Walter Didimo, Luca Grilli, Giuseppe Liotta, and Salvatore Agostino Romeo. 2015. Heuristics for the maximum 2-layer RAC subgraph problem. Comput. J. 58, 5 (2015), 1085–1098.
• Emilio Di Giacomo, Walter Didimo, and Giuseppe Liotta. 2013. Spine and radial drawings. In Handbook on Graph Drawing and Visualization., Roberto Tamassia (Ed.). Chapman and Hall/CRC, 247–284.
• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Henk Meijer. 2011. Area, curve complexity, and crossing resolution of non-planar graph drawings. Theory Comput. Syst. 49, 3 (2011), 565–575.
• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer, and Stephen K. Wismath. 2015. Planar and quasi-planar simultaneous geometric embedding. Comput. J. 58, 11 (2015), 3126–3140.
• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. 2012. $h$-quasi planar drawings of bounded treewidth graphs in linear area. In Proceedings of the WG 2012 (LNCS), Vol. 7551. Springer, 91–102. https://link.springer.com/chapter/10.1007%2F978-3-642-34611-8_12.
• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. 2013. Area requirement of graph drawings with few crossings per edge. Comput. Geom. 46, 8 (2013), 909–916.
• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. 2017. Area-thickness trade-offs for straight-line drawings of planar graphs. Comput. J. 60, 1 (2017), 135–142.
• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, and Ioannis G. Tollis. 2014. Techniques for edge stratification of complex graph drawings. J. Vis. Lang. Comput. 25, 4 (2014), 533–543.
• Emilio Di Giacomo and Giuseppe Liotta. 2007. Simultaneous embedding of outerplanar graphs, paths, and cycles. Int. J. Comput. Geometry Appl. 17, 2 (2007), 139–160.
• Emilio Di Giacomo, Giuseppe Liotta, and Fabrizio Montecchiani. 2015. Drawing outer 1-planar graphs with few slopes. J. Graph Algorithms Appl. 19, 2 (2015), 707–741.
• Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani, and Alessandra Tappini. 2018. NodeTrix planarity testing with small clusters. In Proceedings of the GD 2017 (LNCS), Vol. 10692. Springer, 479–491. https://link.springer.com/chapter/10.1007%2F978-3-319-73915-1_37.
• Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani, and Alessandra Tappini. 2018. Planar k-NodeTrix graphs a new family of beyond planar graphs. In Proceedings of the GD 2017 (LNCS), Vol. 10692. Springer, 609–611. https://link.springer.com/book/10.1007/978-3-319-73915-1?page=2#toc.
• Josep Díaz, Jordi Petit, and Maria J. Serna. 2002. A survey of graph layout problems. ACM Comput. Surv. 34, 3 (2002), 313–356.
• Matthew Dickerson, David Eppstein, Michael T. Goodrich, and Jeremy Yu Meng. 2005. Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl. 9, 1 (2005), 31–52.
• Walter Didimo. 2013. Density of straight-line 1-planar graph drawings. Inf. Process. Lett. 113, 7 (2013), 236–240.
• Walter Didimo. 2016. Upward graph drawing. In Encyclopedia of Algorithms. 2308–2312. DOI: 10.1007/978-1-4939-2864-4_653
• Walter Didimo, Peter Eades, and Giuseppe Liotta. 2010. A characterization of complete bipartite RAC graphs. Inf. Process. Lett. 110, 16 (2010), 687–691.
• Walter Didimo, Peter Eades, and Giuseppe Liotta. 2011. Drawing graphs with right angle crossings. Theor. Comput. Sci. 412, 39 (2011), 5156–5166.
• Walter Didimo and Giuseppe Liotta. 2013. The crossing-angle resolution in graph drawing. In Thirty Essays on Geometric Graph Theory, Janos Pach (Ed.). Springer, New York, NY, 167–184.
• Walter Didimo, Giuseppe Liotta, and Salvatore Agostino Romeo. 2011. A graph drawing application to web site traffic analysis. J. Graph Algorithms Appl. 15, 2 (2011), 229–251.
• Walter Didimo, Giuseppe Liotta, and Salvatore Agostino Romeo. 2011. Topology-driven force-directed algorithms. In Proceedings of the GD 2010 (LNCS), Vol. 6502. Springer, 165–176. https://link.springer.com/chapter/10.1007%2F978-3-642-18469-7_15.
• Walter Didimo and Fabrizio Montecchiani. 2014. Fast layout computation of clustered networks: Algorithmic advances and experimental analysis. Inf. Sci. 260 (2014), 185–199.
• U. Dogrusöz, E. Giral, A. Cetintas, A. Civril, and E. Demir. 2009. A layout algorithm for undirected compound graphs. Inf. Sci. 179, 7 (2009), 980–994.
• Andreas W. M. Dress, Jack H. Koolen, and Vincent Moulton. 2002. On line arrangements in the hyperbolic plane. Eur. J. Comb. 23, 5 (2002), 549–557.
• Vida Dujmovic. 2015. Graph layouts via layered separators. J. Comb. Theory, Ser. B 110 (2015), 79–89.
• Vida Dujmovic, David Eppstein, and David R. Wood. 2017. Structure of graphs with locally restricted crossings. SIAM J. Discr. Math. 31, 2 (2017), 805–824.
• Vida Dujmovic and Fabrizio Frati. 2018. Stack and queue layouts via layered separators. J. Graph Algorithms Appl. 22, 1 (2018), 89–99.
• Vida Dujmovic, Joachim Gudmundsson, Pat Morin, and Thomas Wolle. 2011. Notes on large angle crossing graphs. Chicago J. Theor. Comput. Sci. 2011 (2011).
• Vida Dujmovic, Pat Morin, and David R. Wood. 2017. Layered separators in minor-closed graph classes with applications. J. Comb. Theory, Ser. B 127 (2017), 111–147.
• Vida Dujmovic and David R. Wood. 2004. On linear layouts of graphs. Discr. Math. & Theor. Comp. Sci. 6, 2 (2004), 339–358.
• Vida Dujmovic and David R. Wood. 2005. Stacks, queues and tracks: Layouts of graph subdivisions. Discr. Math. & Theor. Comp. Sci. 7, 1 (2005), 155–202.
• Peter Eades, Seok-Hee Hong, Giuseppe Liotta, Naoki Katoh, and Sheung-Hung Poon. 2015. Straight-line drawability of a planar graph plus an edge. In Proceedings of the WADS 2015 (LNCS), Vol. 9214. Springer, 301–313. https://link.springer.com/chapter/10.1007%2F978-3-319-21840-3_25.
• Peter Eades and Giuseppe Liotta. 2013. Right angle crossing graphs and 1-planarity. Discr. Appl. Math. 161, 7–8 (2013), 961–969.
• P. Eades, B. McKay, and N. Wormald. 1986. On an edge crossing problem. In Proceedings of the ACSC 1986. 327–334. http://users.cecs.anu.edu.au/∼bdm/papers/EdgeCrossing.pdf.
• Peter Eades and Nicholas C. Wormald. 1994. Edge crossings in drawings of bipartite graphs. Algorithmica 11, 4 (1994), 379–403.
• David Eppstein. 2000. Diameter and treewidth in minor-closed graph families. Algorithmica 27, 3 (2000), 275–291.
• David Eppstein, Michael T. Goodrich, and Jeremy Yu Meng. 2007. Confluent layered drawings. Algorithmica 47, 4 (2007), 439–452.
• David Eppstein, Marc J. van Kreveld, Elena Mumford, and Bettina Speckmann. 2009. Edges and switches, tunnels and bridges. Comput. Geom. 42, 8 (2009), 790–802.
• William S. Evans, Michael Kaufmann, William Lenhart, Tamara Mchedlidze, and Stephen K. Wismath. 2014. Bar 1-visibility graphs vs. other nearly planar graphs. J. Graph Algorithms Appl. 18, 5 (2014), 721–739.
• William S. Evans, Giuseppe Liotta, and Fabrizio Montecchiani. 2016. Simultaneous visibility representations of plane st-graphs using L-shapes. Theor. Comput. Sci. 645 (2016), 100–111.
• István Fáry. 1948. On straight-line representation of planar graphs. Acta Sci. Math. 11 (1948), 229–233.
• Martin Fink, Jan-Henrik Haunert, Tamara Mchedlidze, Joachim Spoerhase, and Alexander Wolff. 2012. Drawing graphs with vertices at specified positions and crossings at large angles. In Proceedings of the WALCOM (LNCS), Vol. 7157. Springer, 186–197. https://link.springer.com/chapter/10.1007%2F978-3-642-28076-4_19.
• Jacob Fox, János Pach, and Andrew Suk. 2013. The number of edges in $k$-quasi-planar graphs. SIAM J. Discr. Math. 27, 1 (2013), 550–561.
• M. R. Garey and D. S. Johnson. 1983. Crossing number is NP-complete. SIAM J. Alg. Discr. Meth. 4 (1983), 312–316.
• Ashim Garg and Roberto Tamassia. 2001. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31, 2 (2001), 601–625.
• Jesse Geneson, Tanya Khovanova, and Jonathan Tidor. 2014. Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs. Discr. Math. 331 (2014), 83–88.
• Alexander Grigoriev and Hans L. Bodlaender. 2007. Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49, 1 (2007), 1–11.
• Luca Grilli. 2018. On the NP-hardness of GRacSim drawing and $k$-SEFE Problems. J. Graph Algorithms Appl. 22, 1 (2018), 101–116.
• Arvind Gupta and Russell Impagliazzo. 1991. Computing planar intertwines. In Proceedings of the IEEE FoCS 1991. IEEE, 802–811. https://ieeexplore.ieee.org/document/185452.
• Carsten Gutwenger, Petra Mutzel, and René Weiskircher. 2005. Inserting an edge into a planar graph. Algorithmica 41, 4 (2005), 289–308.
• Nathalie Henry, Jean-Daniel Fekete, and Michael J. McGuffin. 2007. NodeTrix: A hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph. 13, 6 (2007), 1302–1309.
• Michael Hoffmann and Csaba D. Tóth. 2017. Two-planar graphs are quasiplanar. In Proceedings of the MFCS 2017 (LIPIcs), Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 47:1–47:14. http://drops.dagstuhl.de/opus/volltexte/2017/8081/.
• Danny Holten. 2006. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Trans. Vis. Comput. Graph. 12, 5 (2006), 741–748.
• Danny Holten and Jarke J. van Wijk. 2009. Force-directed edge bundling for graph visualization. Comput. Graph. Forum 28, 3 (2009), 983–990.
• Seok-Hee Hong, Peter Eades, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer, and Yusuke Suzuki. 2015. A linear-time algorithm for testing outer-1-planarity. Algorithmica 72, 4 (2015), 1033–1054.
• Seok-Hee Hong and Hiroshi Nagamochi. 2016. Re-embedding a 1-plane graph into a straight-line drawing in linear time. In Proceedings of the GD 2016 (LNCS), Vol. 9801. Springer, 321–334. https://link.springer.com/chapter/10.1007%2F978-3-319-50106-2_25.
• Seok-Hee Hong and Hiroshi Nagamochi. 2016. Testing full outer-2-planarity in linear time. In Proceedings of the WG 2015 (LNCS), Vol. 9224. Springer, 406–421. https://link.springer.com/chapter/10.1007%2F978-3-662-53174-7_29.
• Seok-Hee Hong, Peter Eades, Giuseppe Liotta, and Sheung-Hung Poon. 2012. Fáry's theorem for 1-planar graphs. In COCOON 2012 (LNCS), Vol. 7434. Springer, 335–346. https://link.springer.com/chapter/10.1007%2F978-3-642-32241-9_29.
• John E. Hopcroft and Robert Endre Tarjan. 1974. Efficient planarity testing. J. ACM 21, 4 (1974), 549–568.
• Weidong Huang. 2007. Using eye tracking to investigate graph layout effects. In Proceedings of the APVIS 2007. IEEE, 97–100. https://ieeexplore.ieee.org/document/4126225.
• Weidong Huang. 2013. Establishing aesthetics based on human graph reading behavior: Two eye tracking studies. Pers. Ubiquitous Comput. 17, 1 (2013), 93–105.
• Weidong Huang, Peter Eades, and Seok-Hee Hong. 2014. Larger crossing angles make graphs easier to read. J. Vis. Lang. Comput. 25, 4 (2014), 452–465.
• Weidong Huang, Peter Eades, Seok-Hee Hong, and Chun-Cheng Lin. 2013. Improving multiple aesthetics produces better graph drawings. J. Vis. Lang. Comput. 24, 4 (2013), 262–272.
• Weidong Huang, Seok-Hee Hong, and Peter Eades. 2008. Effects of crossing angles. In Proceedings of the PacificVis 2008. IEEE, 41–46. https://ieeexplore.ieee.org/document/4475457.
• Russell Impagliazzo and Ramamohan Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2 (2001), 367–375.
• Michael Jünger and Petra Mutzel (Eds.). 2004. Graph Drawing Software. Springer.
• Paul C. Kainen. 1974. Some recent results in topological graph theory. In Graphs Combin. (LNCS), Vol. 406. Springer, 76–108. https://link.springer.com/chapter/10.1007/BFb0066436.
• Dmitriy V. Karpov. 2014. An upper bound on the number of edges in an almost planar bipartite graph. J. Math. Sci. 196, 6 (2014), 737–746.
• Michael Kaufmann and Torsten Ueckerdt. 2014. The density of fan-planar graphs. CoRR abs/1403.6184 (2014).
• Michael Kaufmann and Dorothea Wagner (Eds.). 2001. Drawing Graphs. Springer.
• Michael Kaufmann and Roland Wiese. 2002. Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl. 6, 1 (2002), 115–129.
• Ken-ichi Kawarabayashi. 2009. Planarity allowing few error vertices in linear time. In Proceedings of the IEEE FoCS 2009. IEEE, 639–648. https://ieeexplore.ieee.org/document/5438591.
• Ken-ichi Kawarabayashi and Buce Reed. 2007. Computing crossing number in linear time. In Proceedings of the SToC 2007. ACM, 382–390. https://dl.acm.org/citation.cfm?doid=1250790.1250848.
• Philipp Kindermann, Fabrizio Montecchiani, Lena Schlipf, and André Schulz. 2018. Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles. CoRR abs/1808.08496 (2018). Accepted at GD 2018. https://link.springer.com/chapter/10.1007%2F978-3-030-04414-5_11.
• Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani. 2017. An annotated bibliography on 1-planarity. Computer Science Review 25 (2017), 49–67.
• Vladimir P. Korzhik and Bojan Mohar. 2013. Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory 72, 1 (2013), 30–71.
• Yaakov S. Kupitz. 1979. Extremal Problems in Combinatorial Geometry. Matematisk institut, Aarhus Universitet.
• Charles E. Leiserson. 1980. Area-efficient graph layouts (for VLSI). In Proceedings of the FOCS. IEEE Computer Society, 270–281. https://ieeexplore.ieee.org/document/4567828.
• William J. Lenhart, Giuseppe Liotta, and Fabrizio Montecchiani. 2017. On partitioning the edges of 1-plane graphs. Theor. Comput. Sci. 662 (2017), 59–65.
• John M. Lewis and Mihalis Yannakakis. 1980. The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20, 2 (1980), 219–230.
• Giuseppe Liotta and Fabrizio Montecchiani. 2016. L-visibility drawings of IC-planar graphs. Inf. Process. Lett. 116, 3 (2016), 217–222.
• Giuseppe Liotta, Fabrizio Montecchiani, and Alessandra Tappini. 2018. Ortho-polygon visibility representations of 3-connected 1-plane graphs. CoRR abs/1807.01247 (2018). Accepted at GD 2018. https://link.springer.com/chapter/10.1007%2F978-3-030-04414-5_37.
• P. C. Liu and R. C. Geldmacher. 1979. On the deletion of nonplanar edges of a graph. In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing. 727–738.
• Pierce Mike. 2014. Searching for and classifying the finite set of minor-minimal non-apex graphs. Master's thesis. California State University.
• Petra Mutzel. 2001. An alternative method to crossing minimization on hierarchical graphs. SIAM J. Optimization 11, 4 (2001), 1065–1080.
• Tomoki Nakamigawa. 2000. A generalization of diagonal flips in a convex polygon. Theor. Comput. Sci. 235, 2 (2000), 271–282.
• Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R. Wood. 2012. Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb. 33, 3 (2012), 350–373.
• Quan Hoang Nguyen, Peter Eades, Seok-Hee Hong, and Weidong Huang. 2011. Large crossing angles in circular layouts. In Proceedings of the GD 2010 (LNCS), Vol. 6502. Springer, 397–399. https://link.springer.com/chapter/10.1007%2F978-3-642-18469-7_40.
• T. A. J. Nicholson. 1968. Permutation procedure for minimising the number of crossings in a network. Proc. IEE 115, 1 (1968), 21–26. http://dx.doi.org/10.1049/piee.1968.0004
• Taylor L. Ollmann. 1974. On the book thicknesses of various graphs. In Proceedings, 4th S.E. Conference on Combinatorics, Graph Theory, and Computing, Frederick Hoffman, Roy B. Levow, and Robert S. D. Thomas (Eds.). Utilitas Mathematics Publ. Inc., 459.
• János Pach. 2018. Geometric graph theory. In Handbook of Discr. and Comp. Geom., Third Edition. 257–279.
• János Pach, Rom Pinchasi, Micha Sharir, and Géza Tóth. 2005. Topological graphs with no large grids. Graphs Combin. 21, 3 (2005), 355–364.
• János Pach, Rom Pinchasi, Gábor Tardos, and Géza Tóth. 2004. Geometric graphs with no self-intersecting path of length three. Eur. J. Comb. 25, 6 (2004), 793–811.
• János Pach, Rados Raddoicic, Gábor Tardos, and Géza Tóth. 2006. Improving the crossing lemma by finding more crossings in sparse graphs. Discr. Comput. Geom. 36, 4 (2006), 527–552.
• János Pach, Farhad Shahrokhi, and Mario Szegedy. 1996. Applications of the crossing number. Algorithmica 16, 1 (1996), 111–117.
• János Pach and Jenö Töröcsik. 1994. Some geometric applications of dilworth's theorem. Discr. Comput. Geom. 12 (1994), 1–7.
• János Pach and Géza Tóth. 1997. Graphs drawn with few crossings per edge. Combinatorica 17, 3 (1997), 427–439.
• János Pach and Rephael Wenger. 2001. Embedding planar graphs at fixed vertex locations. Graphs Combin. 17, 4 (2001), 717–728.
• Rom Pinchasi and Rados Raddoicic. 2003. Topological graphs with no self-intersecting cycle of length 4. In Proceedings of the ACM SoCG 2003. ACM, 98–103. https://dl.acm.org/citation.cfm?doid=777792.777807.
• Helen C. Purchase. 2000. Effective information visualisation: A study of graph drawing aesthetics and algorithms. Interacting with Computers 13, 2 (2000), 147–162.
• Helen C. Purchase, David A. Carrington, and Jo-Anne Allder. 2002. Empirical evaluation of aesthetics-based graph layout. Empirical Software Engineering 7, 3 (2002), 233–255.
• Gerhard Ringel. 1965. Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universitaet Hamburg 29, 1–2 (1965), 107–117.
• Maxwell J. Roberts. 2012. Underground Maps Unravelled: Explorations in Information Design. Maxwell J Roberts.
• Neil Robertson and Paul D. Seymour. 2004. Graph minors. XX. wagner's conjecture. J. Comb. Theory, Ser. B 92, 2 (2004), 325–357.
• Neil Robertson, Paul D. Seymour, and Robin Thomas. 1993. Hadwiger's conjecture for K ${}_{\mbox{6}}$-free graphs. Combinatorica 13, 3 (1993), 279–361.
• Marcus Schaefer. 2013. The graph crossing number and its variants: A survey. Electron. J. Combin. 20 (2013).
• Walter Schnyder. 1990. Embedding planar graphs on the grid. In Proceedings of the ACM-SIAM SoDA 1990. SIAM, 138–148. https://dl.acm.org/citation.cfm?id=320176.320191.
• Thomas C. Shermer. 1996. On rectangle visibility graphs. III. external visibility and complexity. In Proceedings of the CCCG 1996. Carleton University Press, 234–239. http://www.cccg.ca/proceedings/1996/cccg1996_0039.pdf.
• Janet M. Six and Ioannis G. Tollis. 2013. Circular drawing algorithms. In Handbook on Graph Drawing and Visualization., Roberto Tamassia (Ed.). Chapman and Hall/CRC, 285–315.
• S. K. Stein. 1951. Convex maps. In Proc. Am. Math. Soc., Vol. 2. 464–466.
• Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. 1981. Methods for visual understanding of hierarchical system structures. IEEE Trans. Systems, Man, and Cybernetics 11, 2 (1981), 109–125.
• Andrew Suk and Bartosz Walczak. 2015. New bounds on the maximum number of edges in k-quasi-planar graphs. Comput. Geom. 50 (2015), 24–33.
• Yusuke Suzuki. 2010. Optimal 1-planar graphs which triangulate other surfaces. Discr. Math. 310, 1 (2010), 6–11.
• Roberto Tamassia. 1987. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16, 3 (1987), 421–444.
• Roberto Tamassia and Ioannis G. Tollis. 1986. A unified approach to visibility representations of planar graphs. Discr. Comput. Geom. 1, 1 (1986), 321–341.
• Carsten Thomassen. 1988. Rectilinear drawings of graphs. J. Graph Theory 12, 3 (1988), 335–341.
• C. D. Toth, J. O'Rourke, and J. E. Goodman. 2017. Handbook of Discrete and Computional Geometry, Third Edition. CRC Press.
• Klaus Truemper. 1992. Matroid Decomposition. Academic Press.
• Leslie G. Valiant. 1981. Universality considerations in VLSI circuits. IEEE Trans. Computers 30, 2 (1981), 135–140.
• Pavel Valtr. 1997. Graph drawings with no $k$ pairwise crossing edges. In Proceedings of the GD 1997 (LNCS), Vol. 1353. Springer, 205–218. https://link.springer.com/chapter/10.1007%2F3-540-63938-1_63.
• Pavel Valtr. 1998. On geometric graphs with no $k$ pairwise parallel edges. Discr. Comput. Geom. 19, 3 (1998), 461–469.
• Marc J. van Kreveld. 2010. The quality ratio of RAC drawings and planar drawings of planar graphs. In Proceedings of the GD 2010 (LNCS), Vol. 6502. Springer, 371–376. https://link.springer.com/chapter/10.1007%2F978-3-642-18469-7_34.
• Massimo Vignelli. 2008. New York Subway Map, http://secondavenuesagas.com/2008/05/02/mens-vogue-calls-on-vignelli-for-a-long-awaited-update/.
• Klaus Wagner. 1936. Bemerkungen zum vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung 46 (1936), 26–32.
• Colin Ware, Helen C. Purchase, Linda Colpoys, and Matthew McGill. 2002. Cognitive measurements of graph aesthetics. Inf. Vis. 1, 2 (2002), 103–110.
• Martin Wattenberg. 2002. Arc diagrams: Visualizing structure in strings. In Proceedings of the INFOVIS. IEEE, 110–116. https://ieeexplore.ieee.org/document/1173155.
• Stephen K. Wismath. 1985. Characterizing bar line-of-sight graphs. In Proceedings of the ACM SoCG 1985. ACM, 147–152. https://dl.acm.org/citation.cfm?doid=323233.323253.
• Stephen K. Wismath. 1989. Bar-representable visibility graphs and a related network flow problem. https://open.library.ubc.ca/cIRcle/collections/ubctheses/831/items/1.0051983.
• David R. Wood. 2005. Grid drawings of k-colourable graphs. Comput. Geom. 30, 1 (2005), 25–28.
• Mihalis Yannakakis. 1989. Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38, 1 (1989), 36–67.
• Xin Zhang and Guizhen Liu. 2013. The structure of plane graphs with independent crossings and its applications to coloring problems. Open Math. 11, 2 (2013), 308–321.
• H. Zhou, Panpan Xu, X. Yuan, and H. Qu. 2013. Edge bundling in information visualization. Tsinghua Science and Technology 18, 2 (2013), 145–156.

## Footnotes

• 1We remark that, despite the fact that the use of the term “graph drawing beyond planarity” is relatively recent, the study of nonplanar topological and geometric graphs started much earlier (see, e.g., [167, 191]).
• 2The table only shows a subset of the graph families described in this article.
• 3Here we refer to the so-called weak model, in which the existence of a visibility between a pair of bars does not necessarily imply the existence of an edge in the graph between the two corresponding vertices.

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.