Beyond-Planar Graphs: Models, Structures and Geometric Representations

A drawing of a graph is a mapping of each vertex to a point in the plane and of each edge to a Jordan arc between its endvertices. A drawing is straight-line if each edge is represented by a straight-line segment and it is planar if no two edges intersect, except at common endvertices. A planar graph is a graph that admits a planar drawing. An embedding of a graph is a planar straight-line drawing of it. Every planar graph admits an embedding [15, 23].

A geometric graph is a graph whose vertices are points and whose edges are straight-line segments. A geometric graph is planar if it defines an embedding of the underlying (abstract) graph. A geometric graph is universal for a family $ℱ$ of planar graphs if it contains an embedding of every graph in $ℱ$. That is, for every graph $G\in ℱ$, there exists a subgraph of the universal graph which is isomorphic to $G$ and is planar.

The question we study is the following.

Universality has long been studied from a graph-theoretic perspective, starting from a paper by Rado in the 1960s [21]. An (abstract) graph is universal for a family $ℱ$ of graphs if it contains every graph in $ℱ$ as a subgraph. Clearly, the complete graph $K_n$ with $n$ vertices is universal for any family $\mathscr{H}$ of $n$-vertex graphs. Henceforth, research has been conducted on determining upper and lower bounds on the number of edges that universal graphs for notable families of $n$-vertex sparse graphs must have. Babai et al. [4] proved that a universal graph with $O(m^2\log \log m/\log m)$ edges exists for the family of all graphs with $m$ edges, whereas any such a universal graph has $\mathrm{\Omega }(m^2/{\log }^{2}m)$ edges. Alon et al. [1, 2] proved that there exists a universal graph with $O(n^{2-2/k})$ edges for the $n$-vertex graphs with maximum degree $k$; such a bound is tight in the worst case.

A special attention has been devoted to planar graphs and their subclasses. It has long been known [4] that there exists a graph with $O(n^{3/2})$ edges that is universal for the family of the $n$-vertex planar graphs. This bound was recently improved to $n\cdot 2^{O(\sqrt{\log n\cdot \log \log n})}$ by Esperet et al. [14]. For bounded-degree planar graphs, there exists an (optimal) $O(n)$ bound, due to Capalbo [9]. Böttcher et al. [7, 8] proved that every $n$-vertex graph with minimum degree $\mathrm{\Omega }(n)$ is universal for the $n$-vertex planar graphs of bounded degree. Chung and Graham [11, 12] constructed a universal graph with $O(n\log n)$ edges for the $n$-vertex trees. This bound is the best possible, apart from constant factors.

Universal geometric graphs were first defined and studied by Frati, Hoffmann, and Tóth [17]. They strengthened Chung and Graham result [11, 12] by proving that there exists an $n$-vertex geometric graph with $O(n\log n)$ edges that is universal for the $n$-vertex trees. They also proved that every $n$-vertex convex geometric graph that is universal for the $n$-vertex outerplanar graphs has ${\mathrm{\Omega }}_h(n^{2-1/h})$ edges, for every positive integer $h$, which almost matches the trivial $O(n^2)$ upper bound given by a convex complete geometric graph.

The study of universal geometric graphs has a strong relationship with the study of universal point sets. A set $𝒫$ of points is universal for a family $ℱ$ of planar graphs if every graph in $ℱ$ has an embedding in which the vertex set is mapped to a subset of $𝒫$. The question is then, for a family $ℱ$ of $n$-vertex planar graphs, what is the asymptotic growth of the function representing the minimum number of points of a universal point set for the graphs in $ℱ$. Answering such a question for the family of all $n$-vertex planar graphs is perhaps the most famous graph drawing open problem. It is has been known for a long time that there exists a universal point set for the $n$-vertex planar graphs with $O(n^2)$ points [13], see also [5], while the currently best known lower bound is only linear, namely $(1.293-o(1))n$ [22]; see also [10, 20]. Universal point sets with sub-quadratic size are known for the $2$-outerplanar graphs and the simply nested graphs [3], and for the $n$-vertex stacked triangulations [18]. Linear-size universal point sets are known for the $n$-vertex outerplanar graphs [6, 19], as well as for the cubic planar graphs and the bipartite planar graphs [16].

Consider a point set $𝒫$ which is universal for a family $ℱ$ of planar graphs. Then the complete geometric graph with vertex set $𝒫$ is universal for $ℱ$. This connection, together with the existence of a quadratic-size universal point set for the $n$-vertex planar graphs, gives us an $O(n^4)$ upper bound on the number of edges of a universal geometric graph for the $n$-vertex planar graphs, which is the best known upper bound we are aware of for Problem 1. On the other hand, the best known lower bound is only $\mathrm{\Omega }(n\log n)$, which comes from the described graph-theoretic setting [11, 12].

Our research aimed at finding an upper bound better than $O(n^4)$ for Problem 1. We now explain the strategy we pursued in order to achieve such a goal.

As already mentioned, de Fraysseix, Pach, and Pollack proved the existence of a universal point set $𝒫$ with $O(n^2)$ points (in fact, a $2n\times n$ section of the integer lattice) for the $n$-vertex planar graphs [13]. The embedding of any $n$-vertex planar graph $G$ on $𝒫$ can be constructed incrementally as follows. First, one can assume without loss of generality that $G$ is a maximal plane graph. Indeed, maximality can be guaranteed by an initial edge-augmentation. Furthermore, a maximal planar graph has a unique combinatorial embedding (this is the circular order of the incident edges in an embedding); this, together with a choice of the outer face, enhances $G$ to a maximal plane graph. Second, every maximal plane graph $G$ with $n\ge 3$ vertices and with outer face $(u,v,z)$ admits a canonical ordering. This is a labeling of the vertices $v_1=u,v_2=v,v_3,\mathrm{\dots },v_{n-1},v_n=z$ meeting the following requirements for every $k=3,\mathrm{\dots },n$:

• $\mathrm{■}$

  The plane subgraph $G_k\subseteq G$ induced by $v_1,v_2,\mathrm{\dots },v_k$ is $2$-connected; let $C_k$ be the cycle bounding its outer face;

• $\mathrm{■}$

  $v_k$ is in the outer face of $G_{k-1}$, and its neighbors in $G_{k-1}$ form an (at least $2$-element) subinterval of the path $C_{k-1}-(u,v)$.

A canonical drawing of $G$ can be constructed from a canonical ordering of $G$ in $n-2$ steps. At step $1$, a planar straight-line drawing ${\mathrm{\Gamma }}_3$ of $G_3$ is constructed with $v_1$ at $(0,0)$, with $v_2$ at $(2,0)$, and with $v_3$ at $(1,1)$. Auxiliary sets $M_3(v_1):=\{v_1,v_2,v_3\}$, $M_3(v_3):=\{v_2,v_3\}$, and $M_3(v_2):=\{v_2\}$ are also defined. For $k=4,\mathrm{\dots },n$, at step $k-2$, a planar straight-line drawing ${\mathrm{\Gamma }}_k$ of $G_k$ is constructed from ${\mathrm{\Gamma }}_{k-1}$, as follows. Let $w_1=u,w_2,\mathrm{\dots },w_r=v$ be the clockwise order of the vertices along the outer face of $G_{k-1}$, where $w_p,w_{p+1},\mathrm{\dots },w_q$ are the neighbors of $v_k$ in $G_{k-1}$, for some . Then ${\mathrm{\Gamma }}_k$ is constructed from ${\mathrm{\Gamma }}_{k-1}$ by “shifting” the vertices in $M_{k-1}(w_{p+1})$ by one unit to the right, by shifting the vertices in $M_{k-1}(w_q)$ by one additional unit to the right, and by placing $v_k$ at the intersection point of the line through $w_p$ with slope $+1$ and of the line through $w_q$ with slope $-1$. Step $k-2$ is completed by defining the sets:

• $\mathrm{■}$

  $M_k(w_i)=M_{k-1}(w_i)\cup \{v_k\}$, for $i=1,\mathrm{\dots },p$;

• $\mathrm{■}$

  $M_k(v_k)=M_{k-1}(w_{p+1})\cup \{v_k\}$; and

• $\mathrm{■}$

  $M_k(w_i)=M_{k-1}(w_i)$, for $i=q,\mathrm{\dots },r$.

Note that the above described construction maintains the $x$-monotonicity of the boundary of the drawing at every step. The shifting of the vertices in the sets $M_{k-1}(w_{p+1})$ and $M_{k-1}(w_q)$ makes room for drawing the edges incident to the newly inserted vertex $v_k$ in a planar way.

The starting observation of our approach is that a canonical ordering of $G$ can be used in a much simpler way to obtain a planar straight-line drawing of $G$, entirely avoiding the shifting phase and the definition of the sets $M_{\cdot }(\cdot )$. Indeed, because of the $x$-monotonicity of the boundary of the drawing, one can simply place $v_k$ at a “sufficiently high” point in the interior of the $x$-interval spanned by its neighbors $w_p,w_{p+1},\mathrm{\dots },w_q$. This ensures planarity and maintains the $x$-monotonicity of the boundary of the drawing. We call generalized canonical drawing a drawing constructed in this way.

Now, consider an $n\times n$ stretched grid. This is a point set obtained from an $n\times n$ section of the integer lattice by translating grid rows upwards, in such a way that each point is above the line through any two points in lower rows that are not vertically aligned. Stretched grids were used in [18]. It can be proved that every $n$-vertex maximal plane graph $G$ has a generalized canonical drawing in which the vertex set is mapped to a subset of any $n\times n$ stretched grid $𝒮$; thus, $𝒮$ is a universal point set for the $n$-vertex planar graphs. This can be proved as follows. First, compute a canonical ordering $v_1,v_2,\mathrm{\dots },v_n$ of $G$. Second, define a partial order $Y$ of the vertices of $G$ iteratively, so that each vertex $v_k$ follows all its neighbors $w_p,w_{p+1},\mathrm{\dots },w_q$ in $G_{k-1}$. Third, define a partial order $X$ of the vertices of $G$ iteratively, so that each vertex $v_k$ follows its first neighbor $w_p$ and precedes its last neighbor $w_q$ in $G_{k-1}$. It is easy to see that any assignment of the vertices of $G$ to the points of $𝒮$ such that:

• $\mathrm{■}$

  if a vertex $u$ precedes a vertex $v$ in $Y$, then $u$ is assigned to a lower row than $v$; and

• $\mathrm{■}$

  if a vertex $u$ precedes a vertex $v$ in $X$, then $u$ is assigned to a column to the left of the one of $v$

results in a generalized canonical drawing of $G$ whose vertex set lies at $𝒮$.

Our intuition is that a universal geometric graph $𝒢$ with $o(n^4)$ edges that is universal for the $n$-vertex planar graphs can be constructed so that its vertex set is an $n\times n$ stretched grid $𝒮$, possibly slightly perturbed so that each row defines a convex point set. Our approach for defining $𝒢$ consists of connecting the points on each column of $𝒮$ to all the points on a number of adjacent columns which depends on the index of the column. More specifically, consider the sequence ${\pi }_i$ which is inductively defined as follows: (i) ${\pi }_0:=1$; (ii) ${\pi }_i:={\pi }_{i-1}\circ 2^i\circ {\pi }_{i-1}$. For example, ${\pi }_3=1,2,1,4,1,2,1,8,1,2,1,4,1,2,1$. Let $i$ be sufficiently large so that ${\pi }_i$ has at least $n$ elements. For $j=1,\mathrm{\dots },n$, assign the $j$-th element of ${\pi }_i$ to the $j$-th column of $𝒮$. Then the points on the $j$-th column of $𝒮$ are connected to all the points on a number of adjacent columns which is equal to the element of ${\pi }_i$ assigned to the column times some integer constant $c>0$. Since the sum of the elements assigned to the columns of $𝒮$ is in $O(n\log n)$, the number of edges of the resulting geometric graph $𝒢$ is in $O(n^3\log n)$. Whether $𝒢$ is actually a universal geometric graph for the $n$-vertex planar graphs however remains to be proved.

The study of $k^{+}$-real face drawings of (nonplanar) graphs started in a recent paper by Binucci et al. [1]. In a $k^{+}$-real face drawing, the boundary of each face contains at least $k$ vertices of the graph, where $k\ge 1$ is a given integer. In particular, for any positive integer $k$, a $k^{+}$-real face drawing forbids faces formed only by crossing points and edges. From the practical side, the interest in $k^{+}$-real face graphs is motivated by the intuition that faces mostly consisting of crossing points make the graph layout less readable. From the theoretical side, $k^{+}$-real face drawings can be regarded as a generalization of planar drawings whose face sizes are above a desired threshold [2, 3, 4].

During the seminar we investigated the complexity of recognizing $k^{+}$-real face graphs, that is, the complexity of testing whether, given a graph $G$ and a positive integer $k$, there exists a $k^{+}$-real face drawing of $G$. We studied both the general (unconstrained) scenario and the 2-layer drawing scenario. A summary of the main contributions is given below.

• $\mathrm{■}$

  In the general case, we are able to show that recognizing $k^{+}$-real face graphs for values of $k\in \{1,2\}$ is NP-complete. For the hardness proof we exploit a reduction from the well-known 3-Partition problem. Note that, for $k\ge 3$, optimal $k^{+}$-real face graphs (i.e., $k^{+}$-real face graphs with the maximum possible edge density) are always planar graphs with all faces of degree $k$ (see [1]). Hence, recognizing optimal $k^{+}$-real face graphs when $k\ge 3$ is equivalent to testing whether the graph admits a planar embedding where all faces have size at least $k$, a problem studied in [5].

• $\mathrm{■}$

  We proved tights upper bounds on the maximum number of edges in a 2-layer $k^{+}$-real face graph, for every value of $k$. These types of results can help in the design of recognition algorithms. Specifically, we established that $1^{+}$-real face and $2^{+}$-real face graphs with $n$ vertices have at most $2n-4$ and $1.5n-2$ edges, respectively. Also, for $k\ge 3$, optimal 2-layer $k^{+}$-real face graphs are caterpillar graphs, and therefore have $n-1$ edges.

• $\mathrm{■}$

  We believe that it is possible to efficiently recognize 2-layer $2^{+}$-real face graphs. In particular, during the seminar we designed a testing algorithm that seems to work in linear time in the size of the graph. We plan to give a formal description and a proof of correctness of this algorithm in a near future article.

• $\mathrm{■}$

  For 2-layer $1^{+}$-real face graphs, we characterized the structure of optimal graphs (i.e., 2-layer $1^{+}$-real face graphs with exactly $2n-4$ edges) and of biconncted graphs. These characterizations should lead to efficient recognition algorithms. Recognizing 2-layer $1^{+}$-real face graphs that are not biconnected seems to be more difficult; we are still working on establishing whether a polynomial-time algorithm exists in this case, even if the graph is a tree.

The crossing number of a graph $G$, $\text{cr}(G)$ is the minimum number of edge crossings of $G$ over all its drawings on the plane. $G$ is called $k$-crossing-critical if $\text{cr}(G)\ge k$, but for any edge $e$ of $G$, . Richter and Thomassen [6] proved that the crossing number of a $k$-crossing-critical graph cannot be arbitrarily large, if $G$ is a $k$-crossing-critical graph, then $\text{cr}(G)\le 5k/2+16$. It was improved by Barát and Tóth [2], [4] to $\text{cr}(G)\le 2k+6\sqrt{k}+47$. It is conjectured that for any such graph $G$ we have $\text{cr}(G)\le k+c\sqrt{k}$.

We worked on the following related problem. The local crossing number of a graph $G$, $\text{lcr}(G)$ is the minimum number $l$ with the property that $G$ can be drawn in the plane with at most $l$ crossings on each edge. In other words, $\text{lcr}(G)$ is the minimum number $l$ such that $G$ is $l$-planar. A graph $G$ is $k$-local-crossing-critical if $\text{lcr}(G)\ge k$, but for any edge $e$ of $G$, .

Is there a function $f(k)$ with the property that for any $k$-local-crossing-critical graph $G$, $\text{lcr}(G)\le f(k)$?

$1$-local-crossing critical graphs are easy to describe, removing any edge we get a planar graph, but the graph itself is not planar. It follows from Kuratowski’s theorem, that these graphs are the topological $K_5$ and $K_{3,3}$ graphs, therefore, $f(1)=1$.

We study the problem of reconfiguring graph embeddings on an orientable surface, where the vertices are fixed and each reconfiguration step redraws one edge curve. Consider a set of points $𝒮$ on an orientable surface $\mathrm{\Sigma }$, and two embeddings $𝒫$ and $𝒬$ of the same graph $G$ on vertices $𝒮$. Here an embedding means that each edge is drawn as a curve, which we call an edge curve, on the surface and no two edge curves intersect except at a common endpoint. Note that the edge curves of $𝒫$ may cross the edge curves of $𝒬$. We assume that the correspondence between edge curves of $𝒫$ and $𝒬$ is given. A reconfiguration step or move replaces one edge curve $\gamma$ of an embedded graph $G$ by a new curve ${\gamma }^{\prime }$ to obtain a new embedding of $G$ – in other words, ${\gamma }^{\prime }$ may not cross any of the other edge curves of the embedded graph, though we allow $\gamma$ and ${\gamma }^{\prime }$ to intersect. The question we address is whether $𝒫$ can be reconfigured to $𝒬$ via a sequence of moves.

The special case where the graph is a matching consisting of two disjoint edges was considered by Ito, Iwamasa, Kakimura, Kobayashi, Maezawa, Nozaki, Okamoto, and Ozeki [8]. In this restricted situation, they showed that reconfiguration is not always possible in the plane (see Fig. 4), but is always possible on a surface $\mathrm{\Sigma }$ of genus $g\ge 1$. (Note that their paper is primarily about reconfiguration in a more discrete setting where $𝒫$ and $𝒬$ consist of disjoint paths in a fixed graph.)

Our main result is that if the graph $G$ is a matching and the surface $\mathrm{\Sigma }$ is a torus, then reconfiguration is always possible. This immediately extends to any orientable surface of genus $g\ge 1$ and nonorientable surface of genus $g\ge 2$. The only open case remains the projective plane. We extend the result to the case where $G$ is a tree. The result does not extend to general embeddings of a graph on the torus, as we show by an example. However, we conjecture that reconfiguration is possible if we restrict to plane embeddings, and we prove this for the special case of series-parallel graphs.

The problem of morphing graph drawings on a torus [1, 7] is different in that the vertices are allowed to move but the edges must remain straight segments on the flat torus. The problem of tightening or untangling curves on a surface [2, 3, 4, 6] is also different in that they consider drawings with possible crossings (i.e., immersions rather than embeddings), and deform the edge curves continuously via so-called homotopy moves (local moves that modify the topology of the immersion). We also point the interested reader to Colin de Verdière’s survey [5] on graphs on surfaces.

We have a set $𝒫$ of $n$ non-crossing blue paths on the torus that form a matching of $2n$ points, and we have a set $𝒬$ of $n$ non-crossing red paths that form the same matching of the points. Our algorithm consists of the following three steps:

1. 1.

   Draw the torus as a flat torus with all the red paths inside (i.e., none of them cross the torus boundary).

2. 2.

   Re-draw the blue paths so that none of them cross the torus boundary.

3. 3.

   Use the top/bottom boundary of the flat torus which now forms a clean handle (i.e., a closed non-separating curve not crossed by any red or blue path) to solve the problem.

We remark that for the third step, it would be enough to re-draw the blue paths so that none of them cross the top/bottom boundary. Curiously, however, our proof for the second step will establish the stronger property of clearing the entire boundary.

Following our previous positive result, one may wonder if it is always possible to reconfigure a given toric embedding $𝒫$ with a sequence of moves into another given toric embedding $𝒬$. Unfortunately, this is not always possible as the example in Fig. 8 demonstrates.

For this example, it can be easily verified that a single curve of $𝒫$ can only be replaced by a topologically equivalent curve, i.e., it is impossible to change the embedding by replacing a single edge per move. Moreover, observe that both embeddings correspond to a quadrangulation of the torus where the embedding $𝒬$ differs from $𝒫$ by a twist of the torus. This observation implies that we can generalize this result easily to a surface $\mathrm{\Sigma }$ of higher genus, i.e., one can use a suitably rigid tessellation of $\mathrm{\Sigma }$ for $𝒫$ and then perform a twist along a non-separating curve to obtain another embedding $𝒬$ into which $𝒫$ cannot be reconfigured.

While we showed that not all toric graphs can be reconfigured on the torus one may still wonder what happens if we restrict the embeddings $𝒫$ and $𝒬$ of the graph to be plane. We remark that one may ask the same question for a surface $\mathrm{\Sigma }$ of higher genus $g$ by requiring embeddings $𝒫$ and $𝒬$ to be embeddable on a surface of genus $g-1$.

In particular, we can show that a plane embedding $𝒫$ can be reconfigured into another plane embedding $𝒬$ on the torus if the input graph $G$ is series-parallel. To this end, recall that the family of series-parallel graphs can be defined recursively as follows:

1. 1.

   The graph consisting of a single edge $st$ is a series-parallel graph with poles $s$ and $t$.

2. 2.

   Given two series-parallel graphs $G_1$ with poles $s_1$ and $t_1$ and $G_2$ with poles $s_2$ and $t_2$, the series composition obtained by identifying $t_1$ and $s_2$ is a series-parallel graph with poles $s_1$ and $t_2$.

3. 3.

   Given two series-parallel graphs $G_1$ with poles $s_1$ and $t_1$ and $G_2$ with poles $s_2$ and $t_2$, the parallel composition obtained by identifying $s_1$ and $s_2$ as well as $t_1$ and $t_2$ is a series-parallel graph with poles $s_1=s_2$ and $t_1=t_2$.

Notably, all plane embeddings of series-parallel graphs differ only in the order in which parallel subgraphs are sorted at their common poles. We schematically show in Fig. 9 how two consecutive parallel components can be resorted at their common poles. Transforming $𝒫$ into $𝒬$ then reduces to a sequence of such reorderings.

As a follow-up to the above results found at the Dagstuhl Seminar, we intend to work on the following aspects:

1. 1.

   Most importantly, we want to formalize our approaches further and provide reasonable bounds on their run times.

2. 2.

   Our result on plane embeddings on series-parallel may be generalizable to plane embeddings of general planar graphs on the torus. The missing link is the analysis of triconnected planar graph whose embedding we have to be able to mirror.

3. 3.

   Finally, we want to consider additional types of surfaces. With respect to our results on matchings, we want to attempt to achieve a similar result on the projective plane. Moreover, our results on plane embeddings motivates to study embeddings embeddable on surfaces of genus $g-1$ on a surface of genus $g$.

It is known that not every directed acyclic graph whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity. We investigate the “price of upwardness” for drawing planar directed acyclic graphs upwards – in terms of the maximum number of crossings per edge. More formally, we say that the drawing of a directed graph is upward $k$-planar if each edge is a y-monotone curve that is crossed at most $k$ times by other edges. Our aim is to give good bounds on this parameter $k$ for classes of planar directed acyclic graphs. For example, it is easy to see that every tree, no matter how its edges are directed, admits a planar upward drawing. On the other hand, Papakostas [2] showed that there is a directed acyclic 8-vertex outerpath that does not admit a planar upward drawing. (An outerpath is an outerplanar graph whose weak dual is a path.)

We have studied the problem both from a combinatorial and an algorithmic perspective. While this is still work in progress, we briefly summarize our results below. Let a fan be an outerpath in which there is a vertex, the apex of the fan, that is adjacent to all other vertices. We first show that every directed fan has an upward 2-planar drawing with specific properties (see Lemma 1). We then use this to show that every outerpath has an upward 2-planar drawing (see Theorem 2).

The edges incident to the apex are the inner edges of the fan. The other edges are the outer edges of the fan. Observe that the outer edges of a fan induce a path.

We use Lemma 1 to prove the following.

We assume that the given outerpath is maximal. If the outerpath has interior faces that are not triangles, we triangulate them using additional edges, which we direct such that they do not induce directed cycles. After drawing the resulting maximal outerpath, we remove the additional edges.

Let $G^{\prime }$ be such a graph; see Figure 10(a). Let $c_1,c_2,\mathrm{\dots },c_k$ be the vertices of degree at least 4 in $G^{\prime }$ (marked red in Figure 10(b)). These vertices form a path (light red in Figure 10(b)); let them be numbered along this path, which we call the backbone of $G^{\prime }$. We draw the backbone in an x-monotone fashion, with very small slopes, going up and down as needed; see Figure 10(b). For $i\in \{1,2,\mathrm{\dots },k-1\}$, we set $x(c_{i+1})$ to $x(c_i)$ plus the number of inner edges incident to $c_{i+1}$. For $i\in \{1,2,\mathrm{\dots },k\}$, we place the vertices incident to backbone vertex $c_i$ using the algorithm for drawing a fan as detailed in the proof of Lemma 1. The vertices above (below) $c_i$ are placed above (below) the backbone. If , then the last vertex in the fan of $c_i$ is connected to $c_{i+1}$ and $c_i$ is connected to the first vertex $v_i$ in the fan of $c_{i+1}$. These two edges may cross each other. If the edge $c_i{v}_i$ goes, say, up but the following outer edges go down until a vertex $v_k$ below $c_{i+1}$ is reached, then the edge $e_i$ between $c_i$ and $v_i$ may be crossed a second time by the edge $e$ between $v_{k-1}$ and $v_k$ – as the crossing labeled $x$ on the edge $c_3{v}_3$ in Figure 10(b) – but, due to our invariant for drawing fans, $e$ had been crossed only once within its fan. Also, the edge $e_i$ cannot have a third crossing. Thus, in total no edge is crossed three times. ∎

Theorem 2 naturally raises the question about whether we can extend the proof to any graph having pathwidth 2. This is not the case, as we can prove the following.

Another research direction motivated by Theorem 2 is whether the result about outerpaths can be extended to any outerplanar graph. Also this question has a negative answer. Namely, we can prove the following.

We have also studied the complexity of testing upward $k$-planarity of directed acyclic graphs. An st-graph is a directed acyclic graph with only one source and only one sink. Every planar st-graph with the source and the sink on the same face is upward planar, that is, it admits an upward drawing where no edge is crossed [1]. Leaving the domain of planar st-graphs, we can prove the following.

On the positive side, we are working on proving the following recognition result concerning outer upward 1-planar graphs, that is, graphs that admit an upward 1-planar drawing where all vertices lie on the outer face.

The research activity in Dagstuhl has also identified a list of related problems that can be the subject of future studies. Among them are the following questions.

1. 1.

   Is there a directed outerpath that does not admit an upward 1-planar drawing?

2. 2.

   Consider the class ${𝒪}_{\mathrm{\Delta }}$ of outerplanar graphs (or even 2-trees) of maximum degree $\mathrm{\Delta }$. Is there a function $f$ such that every graph in ${𝒪}_{\mathrm{\Delta }}$ admits an upward $f(\mathrm{\Delta })$-planar drawing?

3. 3.

   For which families of biconnected directed acyclic graphs is testing upward 1-planarity tractable?