11institutetext: Utrecht University, The Netherlands
11email<EMAIL_ADDRESS>TU Eindhoven, The Netherlands
22email<EMAIL_ADDRESS>
# Saturated $k$-Plane Drawings with Few Edges

Fabian Klute 11 Irene Parada 22

###### Abstract

A drawing of a graph is $k$-plane if no edge is crossed more than $k$ times.
In this paper we study saturated $k$-plane drawings with few edges. These are
$k$-plane drawings in which no edge can be added without violating
$k$-planarity. For every number of vertices $n>k+1$, we present a tight
construction with $\frac{n-1}{k+1}$ edges for the case in which the edges can
self-intersect. If we restrict the drawings to be $\ell$-simple we show that
the number of edges in saturated $k$-plane drawings must be larger. We present
constructions with few edges for different values of $k$ and $\ell$. Finally,
we investigate saturated straight-line $k$-plane drawings.

###### Keywords:

saturated drawings $k$-planarity simple drawings

##  1 Introduction

Given a simple undirected graph $G$ on $n$ vertices, a _drawing_ of $G$ in the
plane maps each vertex of $G$ to a distinct point and each edge to a curve
connecting the two corresponding points. In the literature, it is usually
required that the edges are drawn as Jordan arcs. However, in order to
understand the influence of self-intersections in our study, we also consider
drawings in which the edges are allowed to self-intersect. In all our drawings
we forbid edges to pass through vertices, tangencies, and three edges to
properly cross in the same point.

A drawing is _$k$ -plane_ if no edge is properly crossed more than $k$ times.
These drawings have received a lot of attention in the graph drawing community
[7, 10]. In this paper we study _saturated_ $k$-plane drawings, i.e.,
$k$-plane drawings to which no edge can be added without violating the
$k$-planarity of the drawing.

A drawing is _$\ell$ -simple_ if no edge crosses itself and two edges share at
most $\ell$ points including their endpoints. Kynčl et al. [11] initiated the
study of saturated $\ell$-simple drawings, i.e. $\ell$-simple drawings to
which no edge can be added without violating the $\ell$-simplicity of the
drawing. They presented bounds on the minimum number of edges in saturated
$\ell$-simple drawings. Recently the bounds for simple and 2-simple drawings
were improved by Hajnal et al. [8]. Saturated drawings with few edges have
also been studied by Aichholzer et al. [2] in the context of _thrackles_ ,
that are drawings in which every pair of edges intersects exactly once, either
at a proper crossing or at a common endpoint.

In this paper we study the minimum number of edges in saturated $k$-plane
drawings and put it in relation with different drawing restrictions, including
$\ell$-simplicity. Previously, saturated simple $k$-plane drawings have been
studied for $k=1$ and $2$. Brandenburg et al. [5] showed that every saturated
simple $1$-plane drawing has at least $2.1n$ edges and that there are
arbitrarily large saturated simple $1$-plane drawings with $\frac{7n}{3}$
edges. For this problem, Barát and Tóth [4] recently improved the lower bound
to $\frac{20n}{9}$. Auer et al. [3] gave a saturated simple $2$-plane drawing
with at most $\frac{4n}{3}$ edges. Extending this research to larger values of
$k$ was suggested by Tóth as an interesting question [9, Section $3.2$ Problem
$15$].

Table 1: New and known bounds for the infimum ratio of edges to vertices for
arbitrarily large saturated $k$-plane drawings (disregarding lower order
terms). Numbers in the table are upper bounds while the colors represent the
lower bounds. For straight-line drawings no lower bounds are claimed. Arrows
indicate where the best known bound for higher simplicity coincides with the
one for lower simplicity. Citations and references to theorems point to where
the result is proven.

Upper bounds |  with self- crossings |  $k+1$- simple |  $4$-simple |  $3$-simple |  $2$-simple |  simple |  straight- line
---|---|---|---|---|---|---|---
$1$-plane |  $\frac{1}{2}=0.5$ |  |  |  |  $\frac{3}{2}=1.5$ |  $\frac{7}{3}\approx 2.33$ |  $\frac{11}{5}=2.2$
Thm.3.1 |  $\rightarrow$ |  $\rightarrow$ |  $\rightarrow$ |  Thm.5.1 |  [5];Thm.5.2 |  Thm.6.1
$2$-plane |  $\frac{1}{3}\approx 0.33$ |  |  |  $\frac{2}{3}\approx 0.66$ |  $\frac{4}{5}=0.8$ |  $\frac{4}{3}\approx 1.33$ |  $\frac{3}{2}=1.5$
Thm.3.1 |  $\rightarrow$ |  $\rightarrow$ |  Thm.4.1 |  Thm.5.1 |  [3];Thm.5.2 |  Thm.6.1
$3$-plane |  $\frac{1}{4}=0.25$ |  |  $\frac{2}{3}\approx 0.66$ |  $\frac{3}{4}=0.75$ |  $\frac{4}{5}=0.8$ |  $1$ |  $\frac{7}{6}=1.2$
Thm.3.1 |  $\rightarrow$ |  Thm.4.1 |  Thm.5.3 |  Thm.5.1 |  Thm.5.2 |  Thm.6.1
$4$-plane |  $\frac{1}{5}=0.2$ |  |  $\frac{2}{5}=0.4$ |  $\frac{3}{7}\approx 0.43$ |  $\frac{6}{13}\approx 0.46$ |  $\frac{2}{3}\approx 0.66$ |  $1$
Thm.3.1 |  $\rightarrow$ |  Thm.5.3 |  Thm.5.3 |  Thm.5.1 |  Thm.5.2 |  Thm.6.1
$k$-plane |  $\frac{1}{k+1}$ |  $\frac{1}{\left\lfloor\frac{k}{2}\right\rfloor+\frac{1}{2}}$ |  |  |  $\frac{2}{k+\frac{2}{k+2}}$ |  $\frac{2}{k-1}$ |  $\frac{4k+2}{k^{2}+2}$
Thm.3.1 |  Thm.4.1 |  $\rightarrow$ |  $\rightarrow$ |  Thm.5.1 |  Thm.5.2 |  Thm.6.1

Lower bounds:$\frac{1}{k+1}$ Thm.3.1$\frac{2}{k+2}$
Thm.4.1$\frac{20}{9}\approx 2.22$ [4]

#### Relation to independent similar work.

After submission of the first version of our work, we learned that,
independently, Chaplick et al. [6] had investigated saturated drawings of
sparse $k$-planar (multi-)graphs. The main difference is that their setting
allows for multiple parallel edges and therefore no two vertices can lie in
the same cell regardless of whether they are connected in the graph. This
leads to different results, even though the constructions and proof techniques
are similar.

One of the closest results is for saturated $k$-plane drawings without further
restrictions. Using a similar construction to ours in Section 3, they also
obtain a tight bound in their non-restricted setting. In their conclusion they
describe and illustrate a construction obtaining an $\frac{1}{k+1}(n-1)$ upper
bound for $k$-plane drawings of simple graphs without restricting the
simplicity. Their construction only applies for even values of $k$ and matches
the bound that we obtain in Section 4.

After reading their paper, we included a new section, Section 7, resolving an
open question asked by Chaplick et al. on the existance of saturated simple
$k$-plane drawings of matchings for $k=4$, $5$, and $6$ when inserting
parallel edges is allowed. We show that in this setting no saturated simple
$4$\- and $5$-plane drawings of matchings exist. In contrast, we provide a
construction for saturated simple $6$-plane drawings of arbitrarily large
matchings in which no (parallel) edge can be inserted.

#### Our results.

We study the infimum ratio of edges to vertices for arbitrarily large
saturated $k$-plane drawings. For different restrictions on the drawing, we
present both lower bounds and constructions with few edges that give upper
bounds. Table 1 summarizes our results. In Section 3 we show that if we allow
self-intersecting edges there are saturated $k$-plane drawings with $n$
vertices and $\frac{n-1}{k+1}$ edges. Moreover, we prove that the edge-vertex
ratio in this construction is the smallest possible. We begin our paper by
encapsulating a helpful operation for our constructions, called _stashing_ ,
in Section 2 In Section 4 we show that if we disallow self-intersections we
need at least two times the amount of edges: A saturated $k$-plane drawing
with $n$ vertices has at least $\frac{2(n-1)}{k+1}$ edges. In this setting, we
present a construction with $n$ vertices and $\frac{2(n-1)}{k+2}$ edges.
However, this construction requires a $k+1$-simple drawing. In Section 5 we
focus on drawings with low simplicity. For 2-simple drawings we give a
construction with $n$ vertices and less than $\frac{2(n-1)}{k}$ edges. Then,
adapting a construction by Auer et al. [3], we obtain simple drawings with $n$
vertices and $\frac{2n}{k-1}+O(k)$ edges. In Section 6 we consider straight-
line drawings and present a construction with $n$ vertices and
$\frac{4k+2}{k^{2}+2}(n-1)$ edges. Finally, in Section 7 we study saturated
simple $k$-plane drawings of matchings in the setting in which inserting
parallel edges must also be prevented. Our constructions close the gap left
open by Chaplick et al. [6].

##  2 Stashing

Several proofs throughout the paper use stashing into free cells to construct
upper bounds to the minimum edge-vertex ratio in a saturated $k$-plane
drawing. The next lemma provides a tool to more easily compute this bound when
we stash isolated vertices into free cells; compare Theorem 3.1.

######  Lemma 1 ()

For $k>1$, let $D_{0}$ be a saturated $k$-plane drawing with $n_{0}$ vertices,
$m_{0}$ edges, and $f_{0}>0$ free, non-intersecting cells, then there exist
arbitrarily large saturated $k$-plane drawings on $n$ vertices with
$m=\frac{m_{0}}{n_{0}+f_{0}-1}(n-1)$ edges.

###### Proof

Let $D_{0}$ be the initial saturated $k$-plane drawing. The drawing $D_{1}$ is
defined by stashing $k-1$ isolated vertices into $k-1$ free cells of $D_{0}$.
Note that $D_{1}$ has one free cell. Let $t>1$ be an integer and $D_{t}$ the
drawing obtained by stashing $D_{1}$ into the only free cell of $D_{t-1}$. For
all $t\geq 1$ we define $D^{\prime}_{t}$ to be the drawing resulting from
stashing one vertex into the only free cell of $D_{t}$. Let $n$ be the number
of vertices in $D^{\prime}_{t}$ with $t\geq 1$ and $m$ the number of edges. We
obtain that $m=tm_{0}$ and $n=n_{0}t+(f_{0}-1)t+1=(n_{0}+f_{0}-1)t+1$.
Rearranging gives us that $t=\frac{n-1}{n_{0}+f_{0}-1}$ and consequently
$m=\frac{m_{0}(n-1)}{n_{0}+f_{0}-1}$.

It can also be helpful to not stash isolated vertices, but instead replace
them with two new vertices and a new edge completely drawn inside a free cell.
The following lemma establishes the resulting upper bound and shows that using
new edges instead of isolated vertices leads to a lower edge-vertex ratio if
and only if $m_{0}>n_{0}+f_{0}-1$. In other words if and only if the edge-
vertex ratio resulting from stashing isolated vertices exceeds one.

###### Lemma 2

For $k>1$, let $D_{0}$ be a saturated $k$-plane drawing with $n_{0}$ vertices,
$m_{0}$ edges, and $f_{0}>0$ free cells, there are arbitrarily large saturated
$k$-plane drawings on $n$ vertices with
$m=\frac{m_{0}+f_{0}-1}{n_{0}+2f_{0}-2}(n-1)$ edges and if
$m_{0}>n_{0}+f_{0}-1$ this drawing has less edges than a saturated $k$-plane
drawing obtained from $D_{0}$ with Lemma 1.

###### Proof

Let $D_{0}$ be the initial saturated $k$-plane drawing. The drawing $D_{1}$ is
defined by stashing $k-1$ new edges connecting two new vertices into $k-1$
free cells of $D_{0}$. Note that $D_{1}$ has one free cell. Let $t>1$ be an
integer and $D_{t}$ the drawing obtained by stashing $D_{1}$ into the only
free cell of $D_{t-1}$. For all $t\geq 1$ we define $D^{\prime}_{t}$ to be the
drawing resulting from stashing one vertex into the only free cell of $D_{t}$.
Let $n$ be the number of vertices in $D^{\prime}_{t}$ with $t\geq 1$ and $m$
the number of edges. We obtain that $m=t(m_{0}+f_{0}-1)$ and
$n=n_{0}t+2(f_{0}-1)t+1=(n_{0}+2f_{0}-2)t+1$. Rearranging gives us that
$t=\frac{n-1}{n_{0}+2f_{0}-2}$ and consequently
$m=\frac{m_{0}+f_{0}-1(n-1)}{n_{0}+2f_{0}-2}$.

For the second part of the lemma let $D_{S}$ be a saturated $k$-plane drawing
on $n$ vertices with $m_{S}$ edges obtained from $D_{0}$ with Lemma 1 and
$D_{I}$ a saturated $k$-plane drawing obtained as above with $n$ vertices and
$m_{I}$ edges. We are interested when $m_{I}>m_{S}$:

$\displaystyle\frac{m_{0}}{n_{0}+f_{0}-1}(n-1)$ $\displaystyle>$
$\displaystyle\frac{m_{0}+f_{0}-1}{n_{0}+2f_{0}-2}(n-1)$ $\displaystyle
m_{0}(n_{0}+2f_{0}-2)$ $\displaystyle>$
$\displaystyle(n_{0}+f_{0}-1)(m_{0}+f_{0}-1)$ $\displaystyle m_{0}f_{0}-m_{0}$
$\displaystyle>$ $\displaystyle f_{0}n_{0}-n_{0}+f_{0}^{2}-2f_{0}+1$
$\displaystyle m_{0}$ $\displaystyle>$ $\displaystyle n_{0}+f_{0}-1.$

##  3 Allowing Self-Intersections

In this section we consider $k$-plane drawings without any additional
restrictions. In particular, we allow edges to self-intersect. As a
consequence, the boundary of one cell may consist of only one crossing and one
edge segment. If the edge to which this edge segment belongs has $k$
crossings, we can use such a cell to place a vertex in it. In general, in a
$k$-plane drawing we say that an edge is _saturated_ if it is crossed $k$
times. A cell without vertices on its boundary and bounded only by segments of
saturated edges is called _free_. In a saturated $k$-plane drawing a vertex in
a free cell will be isolated. In this way we can produce a $k$-plane drawing
with low edge-vertex ratio: making an edge self-intersect $k$ times and
placing an isolated vertex in every free cell we obtain a saturated $k$-plane
drawing with one single edge and $k+2$ vertices.

To be able to produce arbitrarily large drawings, we can use one free cell
and, instead of placing a vertex, recursively place the construction. In
general, given a saturated $k$-plane drawing $D$ with a free cell $c$,
_stashing_ a drawing $D^{\prime}$ into $c$ refers to producing a new drawing
that consists of the union of the two drawings, with $D^{\prime}$ drawn inside
$c$.

Figure 1: One edge with self-intersections. Gray squares represent isolated
vertices that we stash and the green cell is used for recursively stashing the
construction.

###### Theorem 3.1

There are arbitrarily large drawings on $n$ vertices with $\frac{n-1}{k+1}$
edges, which are saturated $k$-plane. Moreover, this bound is tight.

###### Proof

Let $D_{0}$ be the initial drawing consisting of one edge with $k$ self-
intersections defining $k$ non-intersecting free cells. The drawing $D_{1}$ is
defined by stashing $k-1$ isolated vertices into $k-1$ free cells of $D_{0}$;
see Fig. 1. Note that $D_{1}$ has one free cell. Let $t>1$ be an integer and
$D_{t}$ the drawing obtained by stashing $D_{1}$ into the only free cell of
$D_{t-1}$. For all $t\geq 1$ we define $D^{\prime}_{t}$ to be the drawing
resulting from stashing one vertex into the only free cell of $D_{t}$. Let $n$
be the number of vertices in $D^{\prime}_{t}$ with $t\geq 1$ and $m$ the
number of edges. We obtain that $m=t$ and $n=2t+(k-1)t+1=(k+1)t+1$.
Rearranging the equation we get that $t=\frac{n-1}{k+1}$ and consequently
$m=\frac{n-1}{k+1}$.

Let $D=D(G)$ be a saturated $k$-plane drawing of a graph $G$ on $n$ vertices
and let $x$ be the number of crossings in $D$. Since $G$ might not be
connected, we denote with $\gamma$ the number of connected components of $G$.
Consider the planarization $\mathcal{D}=(P,C)$ obtained from $D$ by replacing
every crossing in $D$ with a vertex and every edge segment with an edge.
Observe that $\mathcal{D}$ has at most one self-loop per vertex and at most
one pair of parallel edges between each two vertices. In the following let
$\gamma^{\prime}\leq\gamma$.

To prove the desired lower bound we make use of Euler’s formula, accounting
also for the connected components: $|P|-|C|+f=\gamma^{\prime}+1,$ where $f$
includes the number of faces defined by self-loops and multiple edges in
$\mathcal{D}$. Since the formula is usually stated for connected, simple
planar graphs we include the easy details on how this version can be derived
in Appendix 0.A.

Next, we count the number of vertices in $P$ and edges in $C$. Since we added
one vertex to $P$ for every vertex and crossing in $D$ we get that $|P|=n+x$.
To count the edges in $C$, traverse every edge in $D$ from one of its
endpoints to the other one. For each crossing we see along this traversal
there is one edge in $C$ plus one additional edge for the last edge segment.
Since every crossing, also a self-intersection, was seen twice during this
traversal we obtain that $|C|=m+2x$. As a result we get from Euler’s formula
that $n-m-x+f=\gamma^{\prime}+1$.

Using that there are at most $k\cdot m$ many crossings we get that
$f+n\leq\gamma^{\prime}+1+(k+1)m$. Observe, that two non-adjacent vertices
cannot share a cell in $D$ without contradicting the assumption that $D$ is
saturated. Hence, we find $f\geq\gamma^{\prime}$: Each connected component of
$\mathcal{D}$ has at least one vertex and no two vertices of different
components can lie on the same face. Consequently, $\gamma^{\prime}+n\leq
f+n\leq\gamma^{\prime}+1+(k+1)m$, which yields $m\geq\frac{n-1}{k+1}$ as
desired.

##  4 Disallowing Self-Intersections

In Section 3 we saw that allowing self-intersections leads to very few edges
being necessary to create saturated $k$-plane drawings. In this and all
following sections we consider only $k$-plane drawings without self-
intersections. The price we pay is that the number of edges we need is roughly
doubled.

For the best construction that we have without self-intersections, the drawing
that we use for stashing has two edges forming a spiral; see Fig. 2. We then
can use one free cell to recursively stash the drawing and the rest to stash
vertices. Intuitively, in our drawing we form almost one free cell for every
crossing and every edge is crossed $k$ times. However, an essential difference
with the previous section is that here each crossing counts for two edges.

(a) Construction for $k$ even

(b) Construction for $k$ odd

Figure 2: Construction used in Theorem 4.1. Gray squares represent isolated
vertices that we stash and green cells are used for recursively stashing the
construction.

We split the proof into three lemmas. Lemmas 3 and 4 establish the upper bound
on the edge-vertex ratio for the cases of $k$ even and odd, respectively. In
Lemma 5 we prove the lower bound.

###### Lemma 3

For even $k>1$ there are arbitrarily large drawings on $n$ vertices with
$m=\frac{2(n-1)}{k+1}$ edges, which are saturated, $k$-plane, and in which no
edge self-intersect.

###### Proof

We construct a drawing $D_{0}$ as follows. Take a path on three vertices and
let $e=uv,f=vw$ be the two edges and $u,v,w$ the three vertices. Draw $e$ as a
straight line in the plane. Then we draw $f$ as a spiral, intersecting $e$
exactly $k$ times as shown in Fig. 2. Crucially, since $k$ is even we can
cross such that $u$ and $v$ are incident to the outer cell, while $w$ is
placed in the other cell which is incident to $v$. As $e$ and $f$ share $k$
crossings we cannot add the edge between $u$ and $w$ without crossing $e$ or
$f$ the $k+1$-st time. Hence, the drawing is saturated, $k$-plane, and has no
edge self-intersect. Furthermore, there are $k-1$ free cells. Using Lemma 1 we
get that for any number of vertices $n\geq 3$ the number of edges $m$ is
$\frac{2(n-1)}{3+k-1-1}=\frac{2(n-1)}{k+1}$.

######  Lemma 4 ()

For odd $k>1$ there are arbitrarily large drawings on $n$ vertices with
$m=\frac{2(n-1)}{k}$ edges, which are saturated, $k$-plane, and in which no
edge self-intersect.

###### Proof

We construct a drawing $D_{0}$ nearly as in the proof of Lemma 3. An
illustration is shown in Fig. 2. The only difference is that, since $k$ is
odd, the $k-1$-th crossing of $e$ and $f$ is such that $f$ is on the lower
side of the supporting line through $e$, while the last crossing of $f$ with
$e$ is from the upper side. Consequently, $f$ has to be drawn such that it
creates a cell in which we either enclose $u$ or $w$. As a result there are
only $k-2$ free cells and for $n$ vertices we obtain
$\frac{2(n-1)}{3+k-2-1}(n-1)=\frac{2(n-1)}{k}$ as the number of edges.

######  Lemma 5 ()

Any saturated $k$-plane drawing on $n$ vertices in which no edge self-
intersects has at least $\left\lfloor\frac{2n-1}{k+2}\right\rfloor$ edges.

###### Proof

Given some saturated $k$-plane drawing $D(G)$ of a graph $G$ with $n$
vertices, $m$ edges, and $x$ crossings in which no edge self-intersects, let
$\mathcal{D}=(P,C)$ be the planarization of $D$. Furthermore, let $\gamma$ be
the number of connected components in $G$ and $\gamma^{\prime}$ the number of
connected components in $\mathcal{D}$. Observe that
$\gamma^{\prime}\leq\gamma$.

In the following we proceed as in the the proof of the lower bound in Theorem
3.1. Note that since in $D$ no edge self-intersects, we find that
$\mathcal{D}$ has not self-loops. Nonetheless, arguing as before we again
obtain that $|P|=n+x$ and $|C|=m+2x$. Using Euler’s formula as derived in
Appendix 0.A we obtain that

$\displaystyle n-m-x+f$ $\displaystyle=$ $\displaystyle\gamma^{\prime}+1$
$\displaystyle f+n$ $\displaystyle=$ $\displaystyle\gamma^{\prime}+1+m+x.$

Since no edge has self-intersections in $D$ the number of crossings is upper
bounded by $\frac{km}{2}$. Consequently we get that

$\displaystyle f+n$ $\displaystyle\leq$
$\displaystyle\gamma^{\prime}+1+\frac{k+2}{2}m.$

Again we can argue that no two non-adjacent vertices share a cell and hence
$f\geq\gamma^{\prime}$ holds. Finally, we obtain

$\displaystyle\gamma^{\prime}+n\leq f+n$ $\displaystyle\leq$
$\displaystyle\gamma^{\prime}+1+\frac{k+2}{2}m$

which yields $m\geq\frac{2n-1}{k+2}$.

Lemmas 3, 4 and 5 proof Theorem 4.1.

######  Theorem 4.1 ()

For every $k>1$ there are arbitrarily large drawings on $n$ vertices with
$\frac{n-1}{\left\lfloor\frac{k}{2}\right\rfloor+\frac{1}{2}}$ edges, which
are saturated $k$-plane and in which no edge self-intersects. Moreover, any
saturated $k$-plane drawing in which no edge self-intersects has at least
$\left\lfloor\frac{2n-1}{k+2}\right\rfloor$ edges.

##  5 Restricting the Simplicity

The construction in Section 4 of families of saturated $k$-plane drawings
requires two adjacent edges to cross $k$ times. Thus, the resulting drawings
are $k+1$-simple but not $k$-simple. In fact, any $k$-plane drawing is
$k+1$-simple. However, the best studied $k$-plane drawings are the simple
ones. By slightly increasing the edge-vertex ratio, in this section we present
families of saturated $k$-plane drawings with few edges that are $2$-simple
and simple.

###  5.1 $2$-Simple Drawings

Our construction of families of saturated $2$-simple $1$-plane drawings is
illustrated in Fig. 3. As in the previous sections, it is based on recursive
stashing. However, in this case it is done by repeatedly making a copy of the
drawing in Fig. 3 and identifying the bottommost edge with the green edge of
the previous copy.

For $2$\- and $3$-planarity our $2$-simple construction is illustrated in Fig.
3. For the $2$-plane construction we use the orange solid sub-arcs while for
$3$-plane construction we use the orange dotted sub-arcs. The final drawings
are obtained by stashing as in the previous sections. To construct arbitrarily
large saturated $2$-simple $k$-plane drawings we start from the drawing in
Fig. 3 with the orange solid sub-arcs. We then insert two sets of
$\frac{k-2}{2}$ independent edges crossing the two free cells of the drawing
as in Fig. 3.

We first prove the case of saturated $2$-simple $1$-plane drawings in Lemma 6
and then for saturated $2$-simple $2$\- and $3$-plane drawings in Lemma 7.
Then we describe our construction for saturated $2$-simple $k$-plane drawings
with $k>3$ and prove in Lemma 8 that the drawing has these properties as well
as determine the number of vertices, edges, and free cells.

######  Lemma 6 ()

There are arbitrarily large drawings on $n$ vertices with $\frac{3(n-2)}{2}$
edges, which are saturated, $2$-simple, and $1$-plane

###### Proof

Consider the drawing in Fig. 3. The depicted graph consists of two triangles
that share a vertex. Let $u,v,w,x,y$ be the five vertices and $u,v,w$ and
$w,x,y$ the two triangles. The depicted drawing is obtained by introducing a
crossing between $uv$ and $vw$ and $wx$ and $wy$. The edges $uv$ and $xy$ are
drawn plane and no further crossings are allowed in this drawing. Let $p$ be
the crossing point between $uw$ and $vw$ and $q$ the crossing point between
$wx$ and $wy$. We draw the edge $xy$ into the cell completely bounded by the
two edge segments between $q$ and $w$. The edge $uv$ is drawn into the outer
cell. Let $D_{0}$ be this drawing. Clearly, $D_{0}$ is $2$-simple and
$1$-plane as there are only two independent crossings. Furthermore, every pair
of non-adjacent vertices is separated from each other by the edge segments
between $q$ and $w$. Hence, $D_{0}$ is also saturated.

Next, observe that there is one cell completely bounded by the edge segments
between $p$ and $w$ that is empty and has only one vertex, namely $w$,
incident to its boundary. We draw a vertex into that cell and connect it with
an edge to $w$ that is drawn inside of the cell; see the gray vertex in Fig.
3. Let the resulting drawing be $D_{1}$.

Similarly to when we stash an isolated vertex into a free cell, we now
recursively add copies of $D_{1}$. To obtain $D_{2}$ consider two copies of
$D_{1}$, $D_{1}$ and $D^{\prime}_{1}$. We identify the edge $xy$ in $D_{1}$
with the edge $uv$ in $D^{\prime}_{1}$ and draw the remainder of
$D^{\prime}_{1}$ completely inside the cell bounded by the edge segments
between $u$, $v$, and $w$. Finally, rename the vertices such that the vertices
$u$, $v$, $w$, $x$, and $y$ in $D_{2}$ correspond to the ones of
$D^{\prime}_{1}$ with the same name. Let $t>1$ be an integer and $D_{t}$ the
drawing obtained by identifying the edge $uv$ in a copy of $D_{1}$ with the
edge $xy$ in $D_{t-1}$ and drawing the remainder of $D_{1}$ completely inside
the cell bounded by the edge segments between $x$, $y$, and $w$ in $D_{t-1}$.

It remains to compute the number of edges in $D_{t}$. For each added copy of
$D_{1}$ we find four vertices in $D_{t}$. Adding the two additional vertices
of the last edge $xy$ in $D_{t}$ which we do not identify with a copy of
$D_{1}$ we get that $D_{t}$ has $n=4t+2$ vertices in total. Similarly, $D_{t}$
has six edges for every added copy of $D_{1}$, hence $m=6t$ edges in total.
Hence, with $t=\frac{n-2}{4}$ we get that
$m=6\frac{(n-2)}{4}=\frac{3(n-2)}{2}$.

(a) Construction for $k=1$

(b) Construction for $k=2$ and $k=3$ (dotted)

(c) Edges added to the free cells of (b) for $k>3$

Figure 3: The drawings used in Theorem 5.1. Gray squares represent vertices
that we stash and green cells are used for recursively stashing the
construction.

###### Lemma 7

For $k=2,3$ there are arbitrarily large drawings on $n$ vertices with
$\frac{4(n-1)}{5}$ edges, which are saturated, $2$-simple, and $k$-plane .

###### Proof

First we show the lemma for $k=2$ Consider the drawing shown in Fig. 3
ignoring the dotted variation. It consists of a cycle on four vertices. Let
$u,v,w,x$ be those vertices and $uv$, $vw$, $wx$, and $ux$ the edges. We draw
the edges such that $uv$ and $wx$ and $vw$ and $ux$ each cross twice. Let
$D_{0}$ be the resulting drawing Clearly $D_{0}$ is $2$-plane and $2$-simple.
Consequently non of the four edges can be crossed. Observe that the non-
adjacent pairs of vertices, namely $u$ and $w$ and $v$ and $x$, are incident
to different cells. Hence, the drawing is saturated. Finally, we observe that
there are two free cells formed by the crossings between $uv$ and $wx$ and
$vw$ and $ux$. Consequently, the number of vertices in $D_{0}$ is $n_{0}=4$,
the number of edges $m_{0}=4$, and the number of free cells $f_{0}=2$ Using
Lemma 1 we obtain that there are arbitrarily large saturated $2$-simple
$2$-plane drawings on $n$ vertices with $m=\frac{4n}{4+2-1}=\frac{4n}{5}$
edges.

For the case of $k=3$ we modify the previous drawing $D_{0}$. The modification
is illustrated in Fig. 3 with the dotted variation. It consists of adding a
crossing between the edges $uv$ and $vw$ and $wx$ and $ux$ close to $v$ and
$x$, respectively. Let $D^{\prime}_{0}$ be the resulting drawing. Clearly the
drawing is $3$-plane. It is also $2$-simple as no edge shares more than $2$
points with any other edge. Furthermore, the non-adjacent vertices $u$ and $w$
and $v$ and $x$ are still incident to different cells. Hence, $D^{\prime}_{0}$
is a saturated $2$-simple $3$-plane drawing. Again, observe that therer are
two free cells formed by $uv$ and $wx$ and $vw$ and $ux$ which yields that
$D^{\prime}_{0}$ has the same number of vertices, edges, and free cells as
$D_{0}$. Consequently, we obtain the same bound on the number of edges in
arbitrarily large saturated $2$-simple $3$-plane drawings as for the case of
saturated $2$-simple $2$-plane drawings.

To proof our bounds for $2$-simple $k$-plane drawings we require an additional
construction. It is a drawing consisting of $z$ independent edges that we draw
in a certain way, such that it can be inserted into the drawing used in Lemma
7. The construction will result in a drawing with $2z+2$ crossings, hence the
final drawing always has even planarity.

Let $G_{z}$ be a graph consisting of $z>0$ independent edges. In the following
we describe how to construct the drawing $M_{z}$ from $G_{z}$; Fig. 3 depicts
$M_{4}$. Let $\gamma$ and $\kappa$ be two curves crossing each other in points
$s_{1}$ and $s_{2}$, forming an empty cell as shown in Fig. 3. We denote that
cell with $c$. Furthermore, we extend $\gamma$ and $\kappa$ to infinity, such
that each splits the plane into two areas. We denote the area above $\kappa$
with $c_{\kappa}$ and the area below $\gamma$ with $c_{\gamma}$.

To construct the drawing $M_{z}$ of $G_{z}$ we begin by drawing $z$
pseudocircles $\omega_{i}$, $1\leq i\leq z$. Each $\omega_{i}$ is drawn such
that it intersects $\gamma$ and $\kappa$ twice in between $s_{1}$ and $s_{2}$.
Furthermore, we require the crossings of the $\omega_{i}$s to appear on
$\gamma$ and $\kappa$ as we traverse them from $s_{1}$ to $s_{2}$ as follows:
the first crossing is with $\omega_{1}$, the second with $\omega_{2}$ and so
on until $\omega_{z}$, then the $z+1$-st crossing is again with $\omega_{1}$,
the $z+2$-nd one with $\omega_{2}$, and the $2z$-th crossing is with
$\omega_{z}$. Since this order is the same along $\gamma$ and $\kappa$ we get
that all crossings between the $\omega_{i}$s lie outside $c$. Furthermore, all
pseudocircles pairwise intersect, once in $c_{\gamma}$ and once in
$c_{\kappa}$. Also, by the imposed ordering there exists a point on each
$\omega_{i}$ that lies inside the cell $c$ and not in the interior of or on
any $\omega_{j}$ with $j>i$. Starting from such a point in $c$ on $\omega_{i}$
and traversing $\omega_{i}$ such that $\kappa$ is crossed first we require the
crossings with the other $\omega_{i}$ to appear in the same order of the
indices. Consequently, for every $\omega_{i}$ with $2<i<z$ there exists a cell
lying inside $c_{\gamma}$ that is bounded by $\omega_{i-2}$, $\omega_{i-1}$,
and $\omega_{i+1}$ let $c_{i}$ be that cell for $\omega_{i}$. For
$\omega_{1}$, $\omega_{2}$, and $\omega_{3}$ we choose the cells bounded by
$\gamma$, $\kappa$, and $\omega_{i+1}$; $\kappa$, $\omega_{i-1}$, and
$\omega_{i+1}$; and $\omega_{i-2}$, $\omega_{i-1}$, and $\kappa$,
respectively. For each $\omega_{i}$ cut the pseudocircle inside $c_{i}$ and
replace the endpoints with the vertices $u_{i}$ and $v_{i}$ in $G_{z}$. Draw
the edge $u_{i}v_{i}$ by following the non-plane segment of $\omega_{i}$ with
endpoints at the positions of $u_{i}$ and $v_{i}$. Let $M_{z}$ be the such
obtained drawing of edges $u_{i}v_{i}$ from $G_{z}$.

To construct the drawing used in Theorem 5.1 we combine the drawings from
Lemma 7 with two copies $M^{1}_{z}$ and $M^{2}_{z}$ of the drawing $M_{z}$ for
$z>0$ as follows. Let $u$, $v$, $w$, and $x$ be the four vertices of the four
cycle and $uv$, $vw$, $wx$, and $ux$ the edges. Then, $uv$ crosses with $wx$
and $vw$ crosses with $ux$. Identify $uv$ with $\gamma$ and $wx$ with $\kappa$
in $M^{1}_{z}$ and $vw$ with $\gamma$ and $ux$ with $\kappa$ in $M^{2}_{z}$.
Furthermore, we can draw the curves in each of $M^{1}_{z}$ and $M^{2}_{z}$
such that no edge in $M^{1}_{z}$ intersects $vw$ or $ux$ and no edge in
$M^{2}_{z}$ intersects $uv$ or $wx$. Let $R_{z}$ be the resulting drawing.

###### Lemma 8

For $z>0$ the drawing $R_{z}$ is saturated, $2$-simple, and $2z+2$-plane and
$R_{z}$ has $4z+4$ vertices, $2z+4$ edges, and $2(z^{2}+z+1)$ free cells.

###### Proof

Let $R_{z}$ for $z>0$ be a drawing obtained as described above. We begin by
showing that $R_{z}$ is a saturated $2$-simple $2z+2$-plane drawing. It is
easy to see that $R_{z}$ is in fact $2$-simple and $2z+2$-plane since the
drawing of the four cycle is $2$-simple and $2$-plane and further the edges
added by $M^{1}_{z}$ and $M^{2}_{z}$ each have $2z$ crossings with other edges
in $M^{1}_{z}$ and $M^{2}_{z}$ respectively. Additionally, each edge in
$M^{1}_{z}$ crosses the edges $uv$ and $wx$ twice and each edge in $M^{2}_{z}$
crosses the edges $vw$ and $ux$ twice, meaning that each of these four edges
is crossed a total of $2z+2$ times. Now since the drawing is $2z+2$-plane and
each edge is also crossed precisely this number of times, no edge can be
crossed again. Furthermore, no two non-adjacent vertices lie inside the same
cell. Consequently, no edge can be added to $R_{z}$ and the drawing is also
saturated.

It remains to count the number of vertices, edges, and free cells. The former
two are straight-froward as the four cycle contributes exactly four vertices
and four edges, and the two copies of $M_{z}$ each contribute $2z$ vertices
and $z$ edges. Hence, $R_{z}$ has $n_{0}=4z+4$ vertices and $m_{0}=2z+4$
edges. To count the free cells $f_{0}$ we to count the free cells introduced
by $M^{1}_{z}$ and $M^{2}_{z}$.

Since they are symmetric we consider here the free cells added by $M^{1}_{z}$.
The free cells incident to edge segments added to $R_{z}$ by $M^{2}_{z}$ can
be counted in the same manner. We use that the edges were constructed from
pseudocircles, where each two pseudocircles intersect twice, we find that
there are a total of $z^{2}$ intersection points between the pseudocircles
hence $z^{2}+z$ cells. The edges $uv$ and $wx$ subdivide $2z-1$ cells into
three cells and add two more cells which are incident to the crossings between
$uv$ and $wx$. In total we obtain $z^{2}+z+2z-1+2=z^{2}+3z+1$ many free cells.
Finally, we have to subtract the $2z$ cells in which we placed vertices and
get that edge segments added by $M^{1}_{z}$ are incident to $z^{2}+z+1$ free
cells in $R_{z}$. Consequently, there are $2(z^{2}+z+1)$ free cells incident
to edge segments added by $M^{1}_{z}$ and $M^{2}_{z}$. Since the two free
cells of the four cycle were already counted and no other free cells exist
this is also the total number of free cells in $R_{z}$.

With Lemmas 6, 7 and 8 we are ready to prove the main theorem of this section.

######  Theorem 5.1 ()

For $k>0$ there are arbitrarily large saturated drawings on $n$ vertices with
$\frac{3(n-2)}{2}$ edges if $k=1$, $\frac{4(n-1)}{5}$ edges if $k=2$ or $k=3$,
and with $\frac{2(n-1)}{k+\frac{2}{k+2}}$ edges if $k>3$, which are saturated,
$2$-simple, and $k$-plane.

###### Proof

Lemmas 6 and 7 proof the cases of $k=1$, $2$, and $3$.

For the case of $k>3$ we consider the drawing $R_{z}$ with $z>0$. From Lemma 8
we know that $R_{z}$ is a saturated $2$-simple $2z+2$-plane drawing.
Consequently, if we choose $z=\frac{k-2}{2}$ the resulting drawing is in
particular $k$-plane. Furthermore, by the same lemma, we know that $R_{z}$ has
$n_{0}=4z+4$ vertices, $m_{0}=2z+4$ edges, and $f_{0}=2(z^{2}+z+1)$ free
cells. Using Lemma 1 we obtain a bound on the edge-vertex ratio in terms of
$z$

$\displaystyle\frac{m_{0}}{n_{0}+f_{0}-1}=\frac{2z+4}{4z+4+2z^{2}+2z+2-1}=\frac{2z+4}{2z^{2}+6z+5}=\frac{z+2}{z^{2}+3z+\frac{5}{2}}.$

Substituting $\frac{k-2}{2}$ for $z$ in the above equation yields

$\displaystyle\frac{z+2}{z^{2}+3z+\frac{5}{2}}$ $\displaystyle=$
$\displaystyle\frac{\frac{k-2}{2}+2}{(\frac{k-2}{2})^{2}+3\frac{k-2}{2}+\frac{5}{2}}$
$\displaystyle=$
$\displaystyle\frac{\frac{k-2+4}{2}}{\frac{k^{2}-4k+4}{4}+\frac{6k-12}{4}+\frac{10}{4}}$
$\displaystyle=$ $\displaystyle\frac{\frac{k+2}{2}}{\frac{k^{2}+2k+2}{4}}$
$\displaystyle=$ $\displaystyle\frac{2k+4}{k^{2}+2k+2}$ $\displaystyle=$
$\displaystyle\frac{2(k+2)}{k(k+2)+2}$

as desired.

Remark. The construction for $k>3$ in Theorem 5.1 works for every even value
of $k$. For odd values we can begin with a saturated $2$-simple $k$-plane
drawing $D$ for $k>3$ and even. We add one new edge $ab$ between new vertices
$a$ and $b$ which we place inside the two free cells and inside all edges of
two $M_{z}$ copies. We draw $ab$ such that it crosses the edges $ux$ and $wx$
as well as all edges in the two copies of $M_{z}$ in $D$. Then, by adding the
dotted variation for $uv$ (see Fig. 3) we obtain a drawing $D^{\prime}$ in
which all edges but $ab$ are crossed $k+1$ times. In fact, $ab$ itself has
only $k$ crossings. This is not a problem though, as the vertices $a$ and $b$
are placed in free cells. Consequently, by adding one edge and two vertices as
well as subtracting two free cells we obtain that $D^{\prime}$ is saturated
$2$-simple $k$-plane drawing with $k>3$ and $k$ odd and if $D^{\prime}$ has
$n$ vertices it has

$\displaystyle\frac{2}{k+\frac{15}{k+3}-1}$

edges.

###  5.2 Simple drawings

Auer et al. [3] presented an elegant construction for saturated simple
$2$-plane drawings. In this section we generalize their construction to all
values $k>0$. The resulting drawings are also reminiscent of the ones in [11].
The construction for $k=1$ achieves the same edge-vertex ratio as the
construction by Brandenburg et al. [5] for saturated simple $1$-plane
drawings.

The constructions proving Theorem 5.2 are illustrated in Fig. 4. In the
figure, all the vertices on the left and on the right are identified. Thus, it
is more easily visualized on a vertical cylinder.

We first describe the general construction and proof that for all $k>0$ it
yields a saturated simple $k$-plane drawing. Let $k>1$ and $t\geq 0$. Consider
$z=t+k+3$ vertices $u_{i}$ which we draw sorted from $i=1$ to $z$ along a
vertical line on the surface of the cylinder from top to bottom. We then add
all edges $u_{i}u_{i+1}$ and $u_{i}u_{j}$ with $j=i+k+2$ for all $1\leq i\leq
z$, ignoring non-existent entries. We also add all missing edges $u_{1}u_{i}$
for $i=1,\ldots,k+2$ and $u_{z}u_{j}$ for $j=t+1,\ldots,z$.

For $k=1$ we modify the above construction slightly. We consider $z=t+6$
vertices $u_{i}$ and add the same edges as above. Additionally, we also add
all possible edges $u_{i}u_{i+2}$ for $1\leq i\leq z$. Let $S_{k,t}$ be the
resulting construction.

######  Lemma 9 ()

For every $k>0$ and $t\geq 0$, $S_{k,t}$ is a saturated simple $k$-plane
drawing.

###### Proof

Clearly, the construction is simple and $k$-plane for any value of $k$ and
$t$. Let $z$ be the number of vertices in $S_{k,t}$. Regardless of the values
of $k$ and $t$ we find the path $u_{1},u_{2},\ldots,u_{z}$ in $S_{k,t}$.
Furthermore, every edge in the path $u_{i}u_{i+1}$ for $1<i<z-1$ is crossed
$k$ times, hence these edges are saturated. Additionally, each edge
$u_{i}u_{j}$ for $j=i+k+2$ crosses $k$ edges $u_{a}u_{b}$ with $i+1\leq a\leq
i+k$ and $i+2\leq b\leq i+k+1$, consequently these edges are saturated.
Finally, we added all the edges incident to $u_{1}$ and $u_{z}$ to vertices
with indices lower than $k+3$. For $k>1$ This means, that any edge that is
could potentially be added has to either cross an edge $u_{i}u_{i+1}$ or
$u_{i}u_{j}$ with $j=i+k+2$. Moreover, for $k=1$ the same holds after adding
the edges $u_{i}u_{i+2}$. Consequently, no edge can be added without violating
$k$-planarity of the drawing and the $S_{k,t}$ is saturated.

(a) Construction for $k=1$

(b) Construction for $k=2$

(c) Construction for $k>2$

Figure 4: Construction for saturated simple $k$-plane drawings. The dashed
left and right sides of the drawings are identified.

We divide the proof of Theorem 5.2 into several lemmas. Lemma 10 proves the
result for saturated simple $1$-plane drawings, in Lemma 12 we show the bound
for saturated simple $2$-plane drawings, and in Lemma 13 we give the proof for
saturated simple $3$-plane drawings. The latter two lemmas also make use of
the intermediate lemma Lemma 11, which shows how many vertices and edges our
construction has for $k>1$.

###### Lemma 10

There are arbitrarily large drawings on $n$ vertices with $\frac{7n-9}{3}$
edges, which are saturated, simple, and $1$-plane.

###### Proof

Let $S_{1,t}$ be a drawing constructed as above for $t\geq 0$. By Lemma 9 we
know that $S_{1,t}$ is saturated, simple, and $1$-plane. Finally, consider
$k=1$ and $t\geq 0$ and let $S_{1,t}$ be the resulting construction. For the
number of vertices we get $z=t+6$. Again counting the sum of degrees $d$ we
get that $u_{1}$ and $u_{t}$ have degree $3$, $u_{2}$ and $u_{z-1}$ have
degree $4$, $u_{3}$ and $u_{z-2}$ have degree $5$, and every other vertex has
degree $6$. Hence, $d=2(3+4+5)+6t=6t+24$ and consequently there are
$m_{z}=3t+12$ edges.

As $S_{1,t}$ is simple and $1$-plane there are no cells with zero or only one
vertex on its boundary. Hence, we consider cells with two vertices on their
boundary. Stashing vertices incident to these two vertices into the cells then
improves the edge-vertex ratio. This was also used in [5] and [4]. We find
that every vertex $u_{i}$ for $i=4,\ldots,z-3$ is on the boundary of four such
cells. Hence, accounting for the cells that are also incident to $u_{3}$ and
$u_{z-2}$, there are $2(z-5)+1=2t+3$ cells with only two vertices on their
boundaries. Stashing all these degree two vertices into $S_{1,t}$ we obtain
the drawing $H_{1,t}$ with

$\displaystyle n=t+6+2t+3=3t+9$

vertices and

$\displaystyle m=m_{z}+2(2t+3)=3t+12+4t+6=7t+18$

edges. Rearranging for $t$ we get that

$\displaystyle t=\frac{n-9}{3}$

and hence there are

$\displaystyle m=7t+18=7\frac{(n-9)}{3}+18=\frac{7n-63+54}{3}=\frac{7n-9}{3}$

edges.

For $k>1$ we compute the number of vertices and edges in the following lemma.

###### Lemma 11

For $k>1$ and $t\geq 0$ $S_{k,t}$ has $z=k+t+3$ vertices and $m_{z}=3k+2t+3$
edges.

###### Proof

Let $S_{k,t}$ be as above for some $k>1$ and $t\geq 0$ we get that there are
$z=t+k+3$ vertices. To compute the number of edges we look at the degrees of
all vertices $u_{i}$ in $S_{k,t}$. For $u_{1}$ and $u_{z}$ we find that both
vertices have degree $k+2$, for $u_{2}$ and $u_{z-1}$ we get degree $3$, and
all remaining vertices have degree four. In total the sum $d$ of degrees in
dependence on $t$ and $k$ is

$\displaystyle d=2\cdot(k+2)+2\cdot 3+4\cdot(t+k-1).$

Hence, there are

$\displaystyle m_{z}=(k+2)+3+2\cdot(t+k-1)=3k+2t+3$

edges in $S_{k,t}$ if $k>1$.

###### Lemma 12

There are arbitrarily large drawings on $n$ vertices with $\frac{4n+7}{3}$
edges, which are saturated, simple, and $2$-plane.

###### Proof

Let $S_{2,t}$ be a drawing constructed as above with $t\geq 0$. By Lemma 9 we
know that $S_{2,t}$ is saturated, simple, and $2$-plane. We also know by Lemma
11that it has $z=t+5$ vertices and $m_{z}=2t+9$ edges. We see that the number
of free cells per edge is clearly zero. Furthermore, the number of edges in
$S_{2,t}$ is approximately $2n$. It turns out that in this situation the edge-
vertex ratio can be lowered by stashing a pendant vertex into each cell that
is bounded by edges with $k$ crossings and has only one vertex on its
boundary.

Let $S_{2,t}$ be a construction as above for $t\geq 0$. Then there are two
cells with only one vertex on their boundary per vertex $u_{i}$ with $5\leq
i\leq z-4$, one such cell per vertex $u_{i}$ with
$i\in\\{2,3,4,z-3,z-2,z-1\\}$, and $u_{1}$ and $u_{z}$ are not incident to any
such cell. Hence, we can stash $2(z-8)+6=2(t+5-8)+6=2t$ pendant vertices. Let
$H_{2,t}$ be the drawing obtained by stashing these $2t$ pendant vertices into
$S_{2,t}$ and let $n$ be the number of vertices and $m$ the number of edges in
$S_{2,t}$. Then, we have $n=z+2t=3t+5$ and $m=m_{z}+2t$. Rearranging for $t$
we get that

$\displaystyle t=\frac{n-5}{3}$

and hence we obtain that there are

$\displaystyle m$ $\displaystyle=$ $\displaystyle
2t+9+2t=4t+9=4\frac{n-5}{3}+9=\frac{4n+7}{3}$

edges.

Remark. Before proving the case for $k>2$ we note that adding pendant vertices
would not decrease the edge-vertex ratio in the following proof. This can be
shown similarly to the argument in Lemma 2.

###### Lemma 13

For $k>2$ there are arbitrarily large drawings on $n$ vertices with
$\frac{2n}{k-1}+\frac{3k-2-\frac{9}{k}}{1-\frac{1}{k}}$ edges, which are
saturated, simple, and $k$-plane.

###### Proof

Let $S_{k,t}$ be a drawing constructed as above for $k>2$ and $t\geq 0$. By
Lemma 9 we know that $S_{k,t}$ is saturated, simple, and $k$-plane. We also
know by Lemma 11 that it has $z=k+t+3$ vertices and $m_{z}=3k+2t+3$ edges.
Consider the edges $u_{i}u_{i+1}$ for $i=k,\ldots,z-k-1$, each of these edges
forms the upper boundary of $k-2$ free cells. Furthermore, for $k>3$ the edges
$u_{i}u_{i+1}$ for $i=3,\ldots,k-1$ and $z-4,\ldots,z-k$ bound each
$1,\ldots,k-3$ free cells. Hence, there are

$\displaystyle(k-2)(z-2k)+2\cdot\sum_{i=1}^{k-3}i$ $\displaystyle=$
$\displaystyle(k-2)(z-2k)+(k-3)(k-2)$ $\displaystyle=$
$\displaystyle(k-2)z-k^{2}-k+6$

free cells. By placing one isolated vertex into each free cell of $S_{k,t}$ we
obtain the construction $H_{k,t}$ with

$\displaystyle n$ $\displaystyle=$ $\displaystyle z+(k-2)z-k^{2}-k+6$
$\displaystyle=$ $\displaystyle(k-1)z-k^{2}-k+6$ $\displaystyle=$
$\displaystyle(k-1)(t+k+3)-k^{2}-k+6$ $\displaystyle=$ $\displaystyle
kt+k^{2}+3k-t-k-3-k^{2}-k+6$ $\displaystyle=$ $\displaystyle(k-1)t+k+3$

vertices and $m=m_{z}$ edges. Rearranging the number of vertices for $t$ gives

$\displaystyle t=\frac{n-k-3}{k-1}$

and hence we obtain that there are

$\displaystyle m$ $\displaystyle=$ $\displaystyle 3k+2t+3$ $\displaystyle=$
$\displaystyle 3k+2\frac{n-k-3}{k-1}+3$ $\displaystyle=$
$\displaystyle\frac{3k(k-1)+2(n-k-3)+3(k-1)}{k-1}$ $\displaystyle=$
$\displaystyle\frac{3k^{2}-3k+2n-2k-6+3k-3}{k-1}$ $\displaystyle=$
$\displaystyle\frac{2n}{k-1}+\frac{3k^{2}-2k-9}{k-1}$ $\displaystyle=$
$\displaystyle\frac{2n}{k-1}+\frac{3k-2-\frac{9}{k}}{1-\frac{1}{k}}.$

edges.

Combining Lemmas 10, 12 and 13 we obtain the desired theorem.

######  Theorem 5.2 ()

There are arbitrarily large saturated simple $k$-plane drawings on $n$
vertices with: $\frac{7n-9}{3}$ edges if $k=1$, $\frac{4n+7}{3}$ edges if
$k=2$, and $\frac{2n}{k-1}+\frac{3k-2-\frac{9}{k}}{1-\frac{1}{k}}$ edges if
$k>2$.

###  5.3 Other drawings with few edges

The following result completes the picture for saturated 3- and 4-simple 3-
and 4-plane drawings. The proof is based on the constructions depicted in Fig.
5.

In this section we give the formal proofs for the constructions shown in
Section 5.3. All three are applications of Lemma 1.

###### Lemma 14

There are arbitrarily large saturated $3$-simple $3$-plane drawings with
$m=\frac{3(n-1)}{4}$ edges.

###### Proof

Consider the drawing shown in Fig. 5. It is a $K_{4}$ drawn with an idea
similar to the one used in Lemma 7. Each edge is crossed three times. Two
crossings are with adjacent edges and one with the independent edge relative
to that edge. This creates five free cells. Applying Lemma 1 with $n_{0}=4$,
$f_{0}=5$, and $m_{0}=6$ gives the result.

(a) $3$-simple $3$-plane: $\frac{3(n-1)}{4}$

(b) $3$-simple $4$-plane: $\frac{3(n-1)}{7}$

(c) $4$-simple $4$-plane: $\frac{2(n-1)}{5}$

Figure 5: Constructions for Theorem 5.3. Gray squares represent isolated
vertices that we stash and green cells are used for recursively stashing the
construction.

###### Lemma 15

There are arbitrarily large saturated $3$-simple $4$-plane drawings with
$m=\frac{3(n-1)}{7}$ edges.

###### Proof

Consider the drawing shown in Fig. 5. It is a path on three vertices $u$, $v$,
$w$, and $x$ drawn such that $uv$ and $wx$ each cross the edge $vw$ and each
other twice as shown in Fig. 5. This creates four free cells. Applying Lemma 1
with $n_{0}=4$, $f_{0}=4$, and $m_{0}=3$ gives the result.

###### Lemma 16

There are arbitrarily large saturated $4$-simple $4$-plane drawings with
$m=\frac{2(n-1)}{5}$ edges.

###### Proof

Consider the drawing shown in Fig. 5. It consists of two independent edges
$uv$ and $wx$ with vertices $u$, $v$, $w$, and $x$. The drawing is such that
the two edges cross each other four times and the vertices $w$ and $x$ are
placed in one cell bounded by the two edges. This leaves two free cells.
Applying Lemma 1 with $n_{0}=4$, $f_{0}=2$, and $m_{0}=2$ gives the result.

Lemmas 14, 15 and 16 proof Theorem 5.3.

######  Theorem 5.3 ()

There are arbitrarily large saturated $3$-simple $3$\- and $4$-plane drawings
on $n$ vertices with $\frac{3(n-1)}{4}$ and $\frac{3(n-1)}{7}$ edges,
respectively, and also arbitrarily large saturated $4$-simple $4$-plane
drawings on $n$ vertices with $\frac{2(n-1)}{5}$ edges.

##  6 Straight-Line Drawings

Finally, we consider $k$-plane drawings in which edges are drawn as straight-
lines. We construct a family of saturated straight-line $1$-plane drawings
with $n$ vertices and $\frac{11n-12}{5}$ edges by gluing $K_{4}$s together and
placing three vertices of degree two for each $K_{4}$, as shown in Fig. 6.
Note that this edge-vertex ratio of $\frac{11}{5}=2.2$ is lower than the lower
bound on the edge-vertex ratio for saturated simple $1$-plane drawings, that
is $\frac{20}{9}\approx 2.22$ [4]. For $k=2$, $3$, and $4$ we take a convex
$4k$-gon and by adding $2k$ chords as shown in Fig. 6 for $k=3$ we obtain a
grid of free cells. For $k>4$ we contract two neighboring groups into one
vertex each as shown in Fig. 6. This creates two fans of $k$ edges that form a
grid of free cells. Stashing into the free cells yields a family of drawings
on $n$ vertices obtaining the desired bounds. For $k=3$ the above construction
gives an edge-vertex ratio of $\frac{6}{5}$, but if instead of stashing
isolated vertices we stash isolated edges we can improve the ratio to
$\frac{7}{6}$; see Fig. 6.

For $k=1$, $2$, and $3$ and up to eight vertices we tested all possible
saturated straight-line $k$-plane drawings using the order type database [1],
confirming for these small values that our constructions are the best
possible.

(a) Construction for $k=1$

(b) Construction for $k>1$

(c) Construction for $k=3$

Figure 6: Constructions used in Theorem 6.1. Gray squares represent vertices
that we stash and green cells are used for recursively stashing the
construction.

We begin by considering the case of $k=1$ in the following lemma and then give
the proof of Theorem 6.1.

###### Lemma 17

There are arbitrarily large drawings on $n$ vertices with $\frac{11n-12}{5}$
edges, which are saturated, straight-line, and $1$-plane

###### Proof

Consider the construction shown in Fig. 6. Let $t>1$ be an integer and place
$2t+2$ vertices on an ellipse as shown in Fig. 6. We add the following edges.
Split the vertices into an upper and lower set and let $u_{i}$ bet the
vertices in the upper and $v_{i}$ be the vertices in the lower set. We assume
the vertices in either set to be labeled from zero to one as we traverse the
upper or lower arc of the ellipse. Then we add the edges $u_{i}u_{i+1}$,
$v_{i}v_{i+1}$,$u_{i}v_{i}$, $u_{i}v_{i+1}$, and $v_{i}u_{i+1}$ for all $0\leq
i\leq t$. The resulting drawing $D_{t}$ is clearly straight-line and
$1$-plane. Note that for all $i$ the four vertices
$u_{i}$,$u_{i+1}$,$v_{i+1}$, and $v_{i}$ form a $K_{4}$ with one crossing
between the edges $u_{i}v_{i+1}$ and $v_{i}u_{i+1}$. Then, $D_{t}$ is
saturated as adding any edge $u_{i}v_{i+j}$ with $j>1$ has to cross the edge
$u_{i+1}v_{i}$ which is already crossed by the edge $u_{i}v_{i+1}$. Moreover,
we cannot add any edge $u_{i}u_{i+j}$ for $j>1$ as it would again cross the
edge $u_{i+1}v_{i}$. The same holds for $j<1$ using edge $u_{i-1}v_{i}$ and
for $v_{i}u_{i+j}$ and $v_{i}v_{i+j}$.

To obtain the bound we add vertices of degree two to $D_{t}$. More precisely,
we add for each $K_{4}$ three vertices of degree two, namely, if $c$ is the
crossing point of the considered $K_{4}$ in the cells bounded by $u_{i}$,
$u_{i+1}$, and $c$, $u_{i+1}$,$v_{i+1}$, and $c$, and $v_{i}$,$v_{i+1}$, and
$c$. Then $D_{t}$ has $n=2t+2+3t=5t+2$ vertices and $m=5t+1+6t=11t+2$ edges.
With $t=\frac{n-2}{5}$ this yields $m=11\frac{n-2}{5}+2=\frac{11n-12}{5}$ for
the number of edges.

######  Theorem 6.1 ()

For every $k>0$ there are arbitrarily large drawings on $n$ vertices with
$\frac{11n-12}{5}$ if $k=1$, $\frac{3(n-1)}{2}$ if $k=2$, $\frac{7(n-1)}{6}$
if $k=3$, $n-1$ if $k=4$, and $\frac{4k+2}{k^{2}+2}(n-1)$ if $k>4$ edges,
which are saturated, straight-line, and $k$-plane.

###### Proof

The case of $k=1$ is proven in Lemma 17. Next, we show how to derive a bound
for $k>1$. Let $s=4k$. Take a cycle $C_{s}$ on $s$ vertices and divide the
vertices into four equally large sets $A_{1}$,$A_{2}$ and $B_{1}$,$B_{2}$,
such that their vertices are consecutive in $C_{t}$. Furthermore, we choose
the sets such that as we traverse the cycle starting from the first vertex of
$A_{1}$ we encounter first all vertices of $A_{1}$, then of $B_{1}$, followed
by vertices in $A_{2}$ and finally the ones in $B_{2}$. We label the vertices
such that we encounter them in each group from index $1$ to $t$. Then, we draw
$C_{s}$ into the plane such that the drawing is plane and the vertices lie all
on a unit circle. Finally, add all edges, we call them _chords_ below,
$a_{i}^{1}a_{i}^{2}$ with $a^{1}_{i}\in A_{1}$ and $a_{i}^{2}\in A_{2}$ and
all edges $b_{i}^{1}b_{i}^{2}$ with $b^{1}_{i}\in B_{1}$ and $b_{i}^{2}\in
B_{2}$; see Fig. 6. Let $D_{0}$ be the resulting drawing. Clearly, $D_{0}$ is
$k$-plane. It is also saturated: No edge between vertices in the same group
can be added as it would require that there exists another vertex in the same
group between them, but this vertex has a neighbor in the group opposite of
the considered one. In the same way, no edge can be added between vertices in
different groups without crossing a chord.

The crossings of the chords in $D_{0}$ create a grid-like set of free cells in
the center of the circle; compare also Fig. 6. This grid has $(k-1)^{2}$ many
cells and all of them are free as they are only bounded by edge segments of
the chords. Using one free cell to stash the whole construction we obtain with
Lemma 1 and $n_{0}=4k$, $f_{0}=(k-1)^{2}$, and $m_{0}=4k+2k=6k$ that

$\displaystyle
m=\frac{6k(n-1)}{4k+(k-1)^{2}-1}=\frac{6k(n-1)}{4k+k^{2}-2k}=\frac{6k(n-1)}{k^{2}+2k}=\frac{6(n-1)}{k+2}.$

For $k=2$ and $k=4$ this yields the claimed bounds. However, for $k=3$ we find
that the resultant bound would be $\frac{6(n-1)}{3+2}=\frac{6(n-1)}{5}$.
Hence, by Lemma 2 we can obtain a better edge-vertex ratio by stashing new
edges instead of isolated vertices; see Fig. 6 for an illustration. Doing so,
we obtain by Lemma 2 and with $n_{0}=4\cdot 3=12$, $f_{0}=(3-1)^{2}=4$, and
$m_{0}=6\cdot 3=18$ that for $k=3$ there are saturated straigth-line $3$-plane
drawings on $n$ vertices with

$\displaystyle\frac{(18+4-1)(n-1)}{12+2\cdot
4-2}=\frac{21(n-1)}{18}=\frac{7(n-1)}{6}$

edges as desired.

To obtain the bound for $k>4$ we modify the construction by contracting the
vertices in $A_{1}$ and $B_{1}$ into one vertex each. Let $a_{1}$ and $b_{1}$
be the resulting vertices and $D^{\prime}_{0}$ the modified drawing. The
vertices $a_{1}$ and $b_{1}$ are incident to $k$ edges each that were
previously inserted between vertices in $A_{1}$ and $A_{2}$ and $B_{1}$ and
$B_{2}$. Since we did not change the groups $A_{2}$ and $B_{2}$ these edges
still cross and hence there are also $(k-1)^{2}$ free cells in
$D^{\prime}_{0}$. With the number of vertices as $n^{\prime}_{0}=2k+2$ and the
number of edges in $D^{\prime}_{0}$ as $m^{\prime}_{0}=2k+2+2k=4k+2$ we obtain
that there are arbitrary large saturated straight-line $k$-plane drawings with

$\displaystyle\frac{(4k+2)(n-1)}{2k+2+(k-1)^{2}-1}=\frac{(4k+2)(n-1)}{2k+2+k^{2}-2k}=\frac{4k+2}{k^{2}+2}(n-1)$

edges as desired.

##  7 Saturated $k$-Plane Drawings of Matchings

Throughout this section we consider multi-graphs, i.e., two vertices can be
connected with more than one edge and we disallow self-intersecting edges. To
clearly distinguish this setting from the previous sections, we call saturated
drawings in which inserting parallel edges is allowed _multi-saturated_.

Chaplick et al. [6] presented multi-saturated simple $k$-plane drawings of
arbitrarily large matchings for $k\geq 7$. They also rule out the existance of
such drawings for any $k\leq 3$. In this section we resolve the remaining open
cases of $k=4$, $5$, and $6$. We prove that for $k=4$ there are no multi-
saturated $k$-plane drawings of arbitrarily large matchings, regardless of the
simplicity, i.e., only self-intersecting edges are not allowed. For the case
of $k=5$ we show that multi-saturated $k+1$-simple $k$-plane drawings of
arbitrarily large matchings exist, but no multi-saturated simple $k$-plane
drawings. Finally, we present a construction for multi-saturated simple
$6$-plane drawings.

###### Lemma 18

There are no multi-saturated $4$-plane drawings of arbitrarily large matchings
without self-intersecting edges.

###### Proof

Let $G=(V,E)$ be a matching on $n$ vertices and $m$ edges, $D(G)$ a multi-
saturated $4$-plane drawing of $G$ without self-intersecting edges, $f$ the
number of cells in $D(G)$ and $x_{i}$ the number of edges that have
$i\in\mathbb{N}_{0}$ crossings in $D(G)$. Consider the planarization
$\mathcal{D}=(P,C)$ of $D(G)$. To simplify the following argumentation we
remove each vertex in $V$ and its unique incident edge from $\mathcal{D}$.
Note that this does not change the number of cells $f$. We know that
$|P|=(4x_{4}+3x_{3}+2x_{2}+x_{1})/2$ and $|C|=3x_{4}+2x_{3}+x_{2}$. With
Euler’s formula it now follows that

$\displaystyle f$ $\displaystyle=$ $\displaystyle
3x_{4}+2x_{3}+x_{2}-(4x_{4}+3x_{3}+2x_{2}+x_{1})/2+2$ $\displaystyle=$
$\displaystyle x_{4}+\frac{1}{2}(x_{3}-x_{1})+2.$

Moreover, we know that $f\geq 2\sum_{i=0}^{4}x_{i}$ since every vertex in $V$
has to be part of a distinct cell in $D(G)$. Consquently, we obtain that

$\displaystyle 2(x_{4}+x_{3}+x_{2}+x_{1}+x_{0})$ $\displaystyle\leq$
$\displaystyle x_{4}+\frac{1}{2}(x_{3}-x_{1})+2$ $\displaystyle
4x_{4}+4x_{3}+4x_{2}+4x_{1}+4x_{0}$ $\displaystyle\leq$ $\displaystyle
2x_{4}+x_{3}-x_{1}+4$ (1) $\displaystyle 2x_{4}+3x_{3}+4x_{2}+5x_{1}+4x_{0}$
$\displaystyle\leq$ $\displaystyle 4.$

The only solution to this equation that do not result in an empty graph or a
graph containing only one edge is

$\displaystyle x_{4}$ $\displaystyle=$ $\displaystyle 2\text{ and
}x_{i}=0\text{ for }i=0,1,2,3.$

This solution leads to an equality between the left-hand and right-hand side
in Equation 7, which implies that the only possible connected multi-saturated
$4$-plane drawings of a matching have two edges and as many cells as there are
endpoints of edges, see Figure 8 for an example. Stashing into such a drawing
is not possible and hence the lemma follows.

Figure 7: A multi-saturated $4$-plane drawing of a matching with two edges.
Since no cell is free the drawing cannot be stashed.

Figure 8: A multi-saturated $5$-plane drawing of a matching with two edges.
Stashing is possible in the outer cell.

Figure 9: A multi-saturated $5$-plane drawing of a matching with three edges.
Since no cell is free the drawing cannot be stashed.

Figure 10: A multi-saturated $5$-plane drawing of a matching with four edges.
Since no cell is free the drawing cannot be stashed.

###### Lemma 19

There are no multi-saturated $\ell$-simple $5$-plane drawings of arbitrarily
large matchings for $\ell<6$.

###### Proof

The proof follows the same idea as the one for Lemma 18. Let $G=(V,E)$ be a
matching, $D(G)$ a multi-saturated $5$-plane drawing of it, $f$ the number of
cells in $D(G)$, and $x_{i}$ the number of edges that have
$i\in\mathbb{N}_{0}$ crossings in $D(G)$. Again, we consider the planarization
$\mathcal{D}=(P,C)$ of $D(G)$ with the vertices from $V$ and their incident
edge removed. We know that $|P|=(5x_{5}+4x_{4}+3x_{3}+2x_{2}+x_{1})/2$ and
$|C|=4x_{5}+3x_{4}+2x_{3}+x_{2}$. Using Euler’s formula in the same manner as
above we obtain that

$\displaystyle x_{5}+2x_{4}+3x_{3}+4x_{2}+5x_{1}+4x_{0}$ $\displaystyle\leq$
$\displaystyle 4.$

The only solutions to this equation not resulting in an empty graph, a graph
with only one edge, or a non-integer number of crossings are

$\displaystyle x_{i}$ $\displaystyle=$ $\displaystyle 1\text{ for }i=3,5\text{
and }x_{j}=0\text{ for }j=0,1,2,4$ (1) $\displaystyle x_{4}$ $\displaystyle=$
$\displaystyle 1\text{ and }x_{5}=2\text{ and }x_{i}=0\text{ for }i=0,1,2,3$
(2) $\displaystyle x_{4}$ $\displaystyle=$ $\displaystyle 2\text{ and
}x_{i}=0\text{ for }i=0,1,2,3,5$ (3) $\displaystyle x_{5}$ $\displaystyle=$
$\displaystyle 2\text{ and }x_{i}=0\text{ for }i=0,1,2,3,4$ (4) $\displaystyle
x_{5}$ $\displaystyle=$ $\displaystyle 4\text{ and }x_{i}=0\text{ for
}i=0,1,2,3,4.$ (5)

Solution (1) implies that at least one edge has to self-intersect, which is
not allowed in our present setting. Any drawing realizing Solution (3), i.e.,
two edges with four crossings each, is not multi-saturated as either edge can
be crossed another time while every cell of the drawing must contain a vertex.
Solutions (2) and (5) imply connected drawings with as many cells as there are
endpoints of edges. Hence, stashing in them is not possible. Drawings
realizing Solutions (2) and (5) can be seen in Figure 10 and 10 respectively.
Finally, Solution (4) leads to a drawing with five crossings and two edges per
connected component. In Figure 8 we give an example of a multi-saturated
$6$-simple $5$-plane drawing realizing this solution. As two edges with five
crossings each can never result in a $5$-simple drawing the lemma follows.

Figure 11: A multi-saturated simple $6$-plane drawing of a matching with only
seven edges.

Figure 12: A multi-saturated simple $6$-plane drawing of a matching with nine
edges. The edge colors indicate edges that behave symmetrically.

###### Theorem 7.1

There are no multi-saturated simple $k$-plane drawings of matchings for
$k\in\\{4,5\\}$ on $n$ vertices, while such drawings exist for $k=6$.
Moreover, for $k=6$ we can construct such drawings of arbitrarily large
matchings.

###### Proof

The claims for $k=4$ and $5$ follow directly from Lemmas 18 and 19.

Figure 12 shows an example of a matching of seven edges drawn with exactly six
crossings per edge. Clearly, the drawing is also simple as no two edges cross
each other more than once. Moreover, every vertex lies in a distinct cell and
no two lie in the same cell. Let $u$ be an arbitrary vertex of the drawing,
then we cannot add an edge between $u$ and any other vertex in the drawing
without crossing the cell boundaries of the cell containing $u$. Yet, each
edge on that boundary is already crossed six times.

The matching in Figure 12 is also as sparse as possible, matching the lower
bound by Chaplick et al. [6]. In Figure 12 we show a fully symmetric saturated
simple $6$-plane drawing of a matching with nine edges. Exploiting its
symmetry one can generate saturated simple $6$-plane drawings of arbitrarily
large matchings without relying on stashing (i.e. the planarization is a
connected graph).

##  8 Conclusion

With this paper we initiated the study of saturated drawings in the context of
$k$-planarity. We presented constructions depending on the simplicity of the
drawing and translated results from the study of maximal $1$\- and $2$-planar
graphs. The, in our opinion, the most interesting open problems are tightening
the bounds for saturated $k+1$-simple and simple $k$-plane drawings. In
particular, achieving a tight bound for saturated simple $1$-plane drawings.
Our results show that as we reduce the simplicity the number of edges we
require to construct saturated $k$-plane drawings seems to increase.

## References

  * [1] Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19(3), 265–281 (2002). https://doi.org/10.1023/A:1021231927255
  * [2] Aichholzer, O., Kleist, L., Klemz, B., Schröder, F., Vogtenhuber, B.: On the edge-vertex ratio of maximal thrackles. In: Archambault, D., Tóth, C.D. (eds.) Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD’19). LNCS, vol. 11904, pp. 482–495. Springer (2019). https://doi.org/10.1007/978-3-030-35802-0_37
  * [3] Auer, C., Brandenburg, F.J., Gleiß ner, A., Hanauer, K.: On sparse maximal 2-planar graphs. In: Didimo, W., Patrignani, M. (eds.) Proceedings of the 20th International Symposium on Graph Drawing (GD’12). LNCS, vol. 7704, pp. 555–556. Springer (2013). https://doi.org/10.1007/978-3-642-36763-2_50
  * [4] Barát, J., Tóth, G.: Improvements on the density of maximal 1-planar graphs. Journal of Graph Theory 88(1), 101–109 (2018). https://doi.org/10.1002/jgt.22187
  * [5] Brandenburg, F.J., Eppstein, D., Gleißner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: Didimo, W., Patrignani, M. (eds.) Proceedings of the 20th International Symposium on Graph Drawing (GD’12). LNCS, vol. 7704, pp. 327–338. Springer (2013). https://doi.org/10.1007/978-3-642-36763-2_29
  * [6] Chaplick, S., Rollin, J., Ueckerdt, T.: Edge-minimum saturated k-planar drawings. CoRR abs/2012.08631 (2020), https://arxiv.org/abs/2012.08631
  * [7] Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Computing Surveys 52(1), 4:1–4:37 (2019). https://doi.org/10.1145/3301281
  * [8] Hajnal, P., Igamberdiev, A., Rote, G., Schulz, A.: Saturated simple and 2-simple topological graphs with few edges. Journal of Graph Algorithms and Applications 22(1), 117–138 (2018). https://doi.org/10.7155/jgaa.00460
  * [9] Hong, S.H., Kaufmann, M., Kobourov, S.G., Pach, J.: Beyond-planar graphs: Algorithmics and combinatorics (Dagstuhl seminar 16452). Dagstuhl Reports 6(11), 35–62 (2017). https://doi.org/10.4230/DagRep.6.11.35
  * [10] Kobourov, S.G., Liotta, G., Montecchiani, F.: An annotated bibliography on 1-planarity. Computer Science Review 25, 49–67 (2017). https://doi.org/10.1016/j.cosrev.2017.06.002
  * [11] Kynčl, J., Pach, J., Radoičić, R., Tóth, G.: Saturated simple and k-simple topological graphs. Computational Geometry: Theory and Applications 48(4), 295–310 (2015). https://doi.org/10.1016/j.comgeo.2014.10.008

##  Appendix 0.A Deriving Euler’s formula for disconnected plane graphs

For completeness, we show in this section how to derive the version of Euler’s
formula used in the proof of the lower bound of Theorem 3.1. Let
$\mathcal{G}=(P,C)$ be an embedded planar graph with $\gamma^{\prime}>0$ many
connected components and $f$ the number of faces in $\mathcal{G}$. Usually
Euler’s formula is stated as

$\displaystyle|P|-|C|+f=2$

and it is assumed that the given graph is simple and connected. In our case
$\mathcal{G}$ might be neither simple nor connected. More precisely, we allow
a vertex in $\mathcal{G}$ to have at most one self-loop or be involved in one
pair of multi-edges. We count these self-loops and multiple edges by adding
one to the number of faces for each occurrence of either. As a result, the
number of edges introduced per self-loop and multiple edge just cancels with
the additionally added faces.

To handle the connected components of $\mathcal{G}$ note that every such
component is itself a connected embedded planar graph. Let $P_{i}$, $C_{i}$,
and $f_{i}$ be the vertices, edges, and the number of faces for the $i$-th
connected component of $\mathcal{G}$, then $|P_{i}|-|C_{i}|+f_{i}=2$ holds for
each $1\leq i\leq\gamma^{\prime}$. Summing over all $i$ we get

$\displaystyle\sum_{i=1}^{\gamma^{\prime}}|P_{i}|-\sum_{i=1}^{\gamma^{\prime}}|C_{i}|+\sum_{i=1}^{\gamma^{\prime}}f_{i}=2\gamma^{\prime}.$

Note that since we count the outer face for each component we have

$\displaystyle\sum_{i=1}^{\gamma^{\prime}}f_{i}=f+(\gamma^{\prime}-1).$

Consequently we obtain

$\displaystyle\sum_{i=1}^{\gamma^{\prime}}|P_{i}|-\sum_{i=1}^{\gamma^{\prime}}|C_{i}|+\sum_{i=1}^{\gamma^{\prime}}f_{i}$
$\displaystyle=$ $\displaystyle 2\gamma^{\prime}$
$\displaystyle|P|-|C|+f+(\gamma^{\prime}-1)$ $\displaystyle=$ $\displaystyle
2\gamma^{\prime}$ $\displaystyle|P|-|C|+f$ $\displaystyle=$
$\displaystyle\gamma^{\prime}+1.$