ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.05
https://doi.org/10.26493/1855-3974.2805.b49
(Also available at http://amc-journal.eu)
Saturated 2-plane drawings with few edges
János Barát *
Department of Mathematics, University of Pannonia and
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Géza Tóth †
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Received 12 January 2022, accepted 24 May 2023, published online 18 August 2023
Abstract
A drawing of a graph is k-plane if every edge contains at most k crossings. A k-plane
drawing is saturated if we cannot add any edge so that the drawing remains k-plane. It is
well-known that saturated 0-plane drawings, that is, maximal plane graphs, of n vertices
have exactly 3n−6 edges. For k > 0, the number of edges of saturated n-vertex k-plane
graphs can take many different values. In this note, we establish some bounds on the
minimum number of edges of saturated 2-plane graphs under various conditions.
Keywords: Saturated drawing, 2-planar, graphs, discharging.
Math. Subj. Class. (2020): 05C10, 05C35
1 Preliminaries
In a drawing of a graph in the plane, vertices are represented by points, edges are repre-
sented by curves connecting the points, which correspond to adjacent vertices. The points
(curves) are also called vertices (edges). We assume that an edge does not go through any
vertex, and three edges do not cross at the same point. A graph together with its drawing
is a topological graph. A drawing or a topological graph is simple if any two edges have at
most one point in common, that is either a common endpoint or a crossing. In particular,
there is no self-crossing. In this paper, we assume the underlying graph has neither loops
nor multiple edges.
For any k ≥ 0, a topological graph is k-plane if each edge contains at most k crossings.
A graph G is k-planar if it has a k-plane drawing in the plane.
*Corresponding author. Supported by NKFIH grant K-131529 and ERC Advanced Grant “GeoScape”
No. 882971.
†Supported by NKFIH grant K-131529 and ERC Advanced Grant “GeoScape” No. 882971.
E-mail addresses: barat@mik.uni-pannon.hu (János Barát), toth.geza@renyi.mta.hu (Géza Tóth)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P1.05
There are several versions of these concepts, see e.g. [4]. The most studied one is when
we consider only simple drawings. A graph G is simple k-planar if it has a simple k-plane
drawing in the plane.
A simple k-plane drawing is saturated if no edge can be added so that the obtained
drawing is also simple k-plane. The 0-planar graphs are the well-known planar graphs. A
plane graph of n vertices has at most 3n − 6 edges. If it has exactly 3n − 6 edges, then it
is a triangulation of the plane. If it has fewer edges, then we can add some edges so that
it becomes a triangulation with 3n− 6 edges. That is, saturated plane graphs have 3n− 6
edges.
Pach and Tóth [6] proved the maximum number of edges of an n-vertex (simple)
1-planar graph is 4n − 8. Brandenburg et al. [3] noticed that saturated simple 1-plane
graphs can have much fewer edges, namely 4517n + O(1) ≈ 2.647n. Barát and Tóth [2]
proved that a saturated simple 1-plane graph has at least 20n9 −O(1) ≈ 2.22n edges.
For any k, n, let sk(n) be the minimum number of edges of a saturated n-vertex simple
k-plane drawing. With these notations, 45n17 + O(1) ≥ s1(n) ≥
20
9 n − O(1). For k > 1,
the best bounds known for sk(n) are shown by Auer et al [1] and by Klute and Parada [5].
Interestingly for k ≥ 5 the bounds are very close.
In this note, we concentrate on 2-planar graphs on n vertices. Pach and Tóth [6] showed
the maximum number of edges of a (simple) 2-planar graph is 5n− 10. Auer et al [1] and
Klute and Parada [5] proved that 4n3 +O(1) ≥ s2(n) ≥
n
2 −O(1). We improve the lower
bound.
Theorem 1.1. For any n > 0, s2(n) ≥ n− 1.
A drawing is l-simple if any two edges have at most l points in common. By definition
a simple drawing is the same as a 1-simple drawing. Let slk(n) be the minimum number of
edges of a saturated n-vertex l-simple k-plane drawing. In [5] it is shown that 4n5 +O(1) ≥
s22(n) ≥ n2 − O(1) and
2n
3 + O(1) ≥ s
3
2(n) ≥ n2 − O(1). We make the following
improvements:
Theorem 1.2. (i) s22(3) = 3, and ⌊3n/4⌋ ≥ s22(n) ≥ ⌊2n/3⌋ for n ̸= 3,
(ii) s32(3) = 3, and s
3
2(n) = ⌊2n/3⌋ for n ̸= 3.
The saturation problem for k-planar graphs has many different settings, we can allow
self-crossings, parallel edges, or we can consider non-extendable abstract graphs. See [4]
for many recent results and a survey.
2 Proofs
Definition 2.1. Let G be a topological graph and u a vertex of degree 1. For short, u is
called a leaf of G. Let v be the only neighbor of u. The pair (u, uv) is called a flag. If there
is no crossing on uv, then (u, uv) is an empty flag.
Definition 2.2. Let G be an l-simple 2-plane topological graph. If an edge contains two
crossings, then its piece between the two crossings is a middle segment. The edges of G
divide the plane into cells. A cell C is special if it is bounded only by middle segments
and isolated vertices. Equivalently, C is special, if there is no vertex on its boundary, apart
from isolated vertices. An edge that bounds a special cell is also special.
J. Barát and G. Tóth: Saturated 2-plane drawings with few edges 3
Let G be a saturated l-simple 2-plane topological graph, where 1 ≤ l ≤ 3. Suppose
a cell C contains an isolated vertex v. Since G is saturated, C must be a special cell and
there is no other isolated vertex in C. Now suppose C is an empty special cell. Each
boundary edge contains two crossings. Therefore, if we put an isolated vertex in C, then
the topological graph remains saturated. So if we want to prove a lower bound on the
number of edges, we can assume without loss of generality that each special cell contains
an isolated vertex.
Claim 2.3. A special edge can bound at most one special cell.
Proof. Suppose uv is a special edge and let pq be its middle segment. If uv bounds more
than one special cell, then there is a special cell on both sides of pq, C1 and C2 say. Let
p be a crossing of the edges uv and xy. There is no crossing on xy between p and one
of the endpoints, x say. Therefore, one of the cells C1 and C2 has x on its boundary, a
contradiction.
Proof of Theorem 1.1. Suppose G is a saturated simple 2-plane topological graph of n
vertices and e edges. We assume that each special cell contains an isolated vertex.
Claim 2.4. All flags are empty in G.
Proof. Let (u, uv) be a flag. Suppose to the contrary there is at least one crossing on uv.
Let p be the crossing on uv closest to u, with edge xy. Since it is a 2-plane drawing, there
is no crossing on xy between p and one of the endpoints, x say. In this case, we can connect
u to x along up and px. Since the drawing was saturated, u and x are adjacent in G, and
x ̸= v, that contradicts to d(u) = 1.
Remove all empty flags from G. Observe the resulting topological graph G′ is also
saturated. If we can add an edge to G′, then we could have added the same edge to G.
Suppose to the contrary that G′ contains a flag (v, vw). Since G′ is saturated, the flag
is empty by Claim 2.4. In G, vertex v had degree at least 2, so v had some other neighbors,
u1, . . . , um say, in clockwise order. The flags (ui, uiv) were all empty. However, u1 can
be connected to w, which is a contradiction. Therefore, there are no flags in G′. On the
other hand, the graph G′ may contain isolated vertices. Let n′ and e′ denote the number of
vertices and edges of G′. Since n − n′ = e − e′, it suffices to show that e′ ≥ n′ − 1. If
there are no isolated vertices in G′, then e′ ≥ n′ is immediate.
We assign weight 1 to each edge. If G′ has no edge, then it has one vertex and we are
done. We discharge the weights to the vertices so that each vertex gets weight at least 1. If
uv is not a special edge, then it gives weight 1/2 to both endpoints u and v. Suppose now
that uv is a special edge. It bounds the special cell C containing the isolated vertex x. If
d(u) = 2, then uv gives weight 1/2 to u, if d(u) ≥ 3, then it gives weight 1/3 to u. We
similarly distribute the weight to vertex v. We give the remaining weight of uv to x.
We show that each vertex gets weight at least 1. This holds immediately for all vertices
of positive degree. We have to show the statement only for isolated vertices. Let x be an
isolated vertex in a special cell C bounded by e1, e2, . . . , em in clockwise direction. Let
ei = uivi such that the oriented curve −−→uivi has C on its right. See Figure 1 for m = 5.
Let pi be the crossing of ei and ei+1. Indices are understood modulo m. In general, it may
happen that some of the points in { ui, vi | i = 1, . . . ,m } coincide. For each vertex ui
or vi of degree at least 3, the corresponding boundary edge of C has a remainder charge
4 Ars Math. Contemp. 24 (2024) #P1.05
v u
u
v
vu
2 4
2 4
1
3
v
1
=u
3
v
u
v u
u
v
vu
2 4
3
1
2 4
1
3
v u
u
1
2
1
=u
3
2
v
v
3
v
u4
u
4
v
5
5
Figure 1: Case 1, d(v1) ≥ 4, Case 2, d(v1) ≥ 3 and Case 2, u1 = u3.
at least 1/6. We have to prove that (with multiplicity) at least 6 of the vertices ui, vi have
degree at least 3. Consider vertex vi.
Case 1: vi = ui+2. The vertex vi = ui+2 can be connected to ui+1 along the segments
vipi and piui+1, that are crossing-free segments of the corresponding edges. Similarly,
vi = ui+2 can be connected to vi+1 along vipi+1 and pi+1vi+1. Since the drawing was
simple and saturated, ui, ui+1, vi+1, vi+2 are all different and they are already connected
to vi = ui+2, so it has degree at least 4.
Case 2: vi ̸= ui+2. The vertex vi can be connected to ui+1 as before, and to ui+2
along vipi, pipi+1 and pi+1ui+2. Since the drawing was saturated, vi is already adjacent
to ui, ui+1, ui+2. Unless ui = ui+2, vertex vi has degree at least 3. Note that ui+1 ̸= ui
and ui+1 ̸= ui+2, since the drawing was 1-simple.
We can argue analogously for ui. We conclude that vi has degree 2 only if ui = ui+2,
and ui has degree 2 only if vi = vi−2.
Recall that m is the number of bounding edges of the special cell C. For m = 3, it is
impossible that ui = ui+2 or vi = vi−2, therefore, for i = 1, 2, 3 all six vertices ui, vi have
degree at least 3.
Let m > 3, and suppose v1 has degree 2, consequently u1 = u3. In this case, we prove
that um, u1, u2, u3, vm, v2 all have degree at least 3.
We show it for u2, the argument is the same for the other vertices. Let γ be the closed
curve formed by the segments u1p1, p1p2 and p2u3. (We have u1 = u3.) Suppose
d(u2) = 2. By the previous observations, vm = v2. However, vm and v2 lie on dif-
ferent sides of γ, therefore they cannot coincide. Therefore, there are always at least six
vertices ui, vi, with multiplicity, which have degree at least 3, so the isolated vertex x gets
weight at least 1. This concludes the proof.
We recall that s32(n) denotes the minimum number of edges of a saturated n-vertex
3-simple 2-plane drawing.
Proof of Theorem 1.2. We start with the upper bounds. Let
f(n) =
{
3 if n = 3
⌊3n/4⌋ otherwise.
First we construct a saturated 2-plane, 2-simple topological graph with n vertices and
f(n) edges, for every n. Let k ≥ 3. A k-propeller is isomorphic to a star with k edges as an
J. Barát and G. Tóth: Saturated 2-plane drawings with few edges 5
Figure 2: A 3-propeller and a 2-propeller.
abstract graph, drawn as in Figure 2. Clearly it is a saturated 2-plane, 2-simple topological
graph with k + 1 vertices, k edges and the unbounded cell is special.
For n = 1, 2, 3, a complete graph of n vertices satisfies the statement. For n ≥ 4,
n ≡ 0 mod 4, consider n/4 disjoint 3-propellers such that each of them is in the unbounded
cell of the others. For n ≥ 4, n ≡ 1, 2, 3 mod 4, replace one of the propellers by an isolated
vertex, a K2, and a 4-propeller, respectively. This implies the upper bound in (i), that is,
s22(n) ≤ f(n).
Now we construct a saturated 2-plane, 3-simple topological graph with n vertices and
⌊2n/3⌋ edges, for every n. A 2-propeller is isomorphic to a path of 2 edges as an abstract
graph, drawn as in Figure 2. Clearly it is a saturated 2-plane, 3-simple topological graph
with 3 vertices, 2 edges and the unbounded cell is special.
For n ≡ 0 mod 3, take n/3 disjoint 2-propellers such that each of them is in the un-
bounded cell of the others. For n ≡ 1, 2 mod 3, add an isolated vertex or an independent
edge. This implies the upper bound in (ii), s32(n) ≤ ⌊2n/3⌋.
We prove by induction on n that s22(n) ≥ ⌊2n/3⌋ and s32(n) ≥ ⌊2n/3⌋. It is trivial for
n ≤ 4. Let n > 4 and assume that s22(m), s32(m) ≥ ⌊2m/3⌋ for every m < n. Let G
be a saturated 2-plane, 2-simple or 3-simple drawing with n vertices and e edges. We may
assume again that every special cell contains an isolated vertex.
Suppose that (u, uv) is an empty flag. We remove u from G. Analogous to the proof
of Theorem 1.1, the obtained topological graph is saturated, it has n− 1 vertices and e− 1
edges. By the induction hypothesis, e−1 ≥ ⌊2(n−1)/3⌋, which implies that e ≥ ⌊2n/3⌋.
Therefore, we assume for the rest of the proof that G does not contain empty flags.
Claim 2.5. If (u, uv) is a flag, then either d(v) ≥ 3 or u and v are included in a 2-propeller.
Proof. Since G does not contain empty flags, there is a crossing on uv. Let p be the
crossing on uv closest to u, with edge xy. There is no crossing on xy between p and one
of the endpoints, x say, and x ̸= u by the assumptions. We can connect u to x along the
segments up and px. Since the drawing was saturated, u and x are adjacent in G. Since u
has degree 1, x = v. This implies d(v) ≥ 2. We exclude parallel edges, so y ̸= u.
Suppose d(v) = 2. There is a crossing on the segment py of vy, otherwise we could
connect u to y along the segments up and py contradicting the degree assumption on u.
Let q be the crossing of vy and ab. There is no crossing on ab between q and one of the
endpoints, a say. If a and u are on the same side of edge vy (that is, the directed edges
−→
ab
6 Ars Math. Contemp. 24 (2024) #P1.05
and −→uv cross the directed edge −→vy from the same side), then we can connect u to a along
the segments up, pq, qa. Therefore a = v, so either d(v) ≥ 3, or b = u, and edges uv and
vy form a 2-propeller. Note that this case is possible only if G is 3-simple.
So we may assume that a is on the other side. If a = v, then d(v) ≥ 3, so we also
assume that a ̸= v. Consider now the edge uv. If there was no crossing on the segment pv
of uv, then we can connect u to a along up, the segment pv of yv, the segment vp of uv,
pq, and qa. Therefore, there is a crossing on the segment pv of uv. Let r be this crossing
of uv with edge cd, and we can assume there is no crossing on the segment cr. (Here, c or
d might coincide with a.) If c and y are on the same side of uv (that is, the directed edges
−→vy and
−→
dc cross the directed edge −→vu from the same side), then we can connect u to c along
up, px, xr, rc, which means that c = v, so d(v) ≥ 3. If c and y are on opposite sides of
uv, then we can connect c to v, so they are already connected. Therefore, c = y. However,
we assumed that −→vy and
−→
dc cross the directed edge −→vu from the opposite sides, so there is
another crossing of uv and vy. If G is 2-simple, this is impossible and we are done. If G is
3-simple, then this crossing can only be r, so c = y and d = x. Now the edges uv and vy
form a 2-propeller.
In a graph G, a connected component with at least two vertices is an essential compo-
nent. If G has only one essential component, then G is essentially connected.
Claim 2.6. We can assume without loss of generality that G is essentially connected.
Proof. Suppose to the contrary G has at least two essential components. We define a partial
order on the essential components of G: Gi ≺ Gj if and only if Gi lies in a bounded cell
of Gj . Let G1 be a minimal element with respect to ≺ and let G2 be the union of all
other essential components. There is a cell C of G, which is bounded by both G1 and
G2. Let C correspond to cell C1 of G1 and cell C2 of G2. By the definition of G1, C1 is
the unbounded cell of G1. Since G is saturated, at least one of C1 or C2 is a special cell,
otherwise G1 and G2 can be connected.
For i = 1, 2, let Hi be the topological graph Gi together with an isolated vertex in every
special cell. Let ni denote the number of vertices and ei the number of edges in Hi. We
notice e = e1 + e2 and n = n1 + n2 − 1 if exactly one of C1 and C2 is a special cell. Also
n = n1+n2−1 if both of them are special cells, since we can add 1 isolated vertex instead
of 2. By the induction hypothesis, we have ei ≥ ⌊2ni/3⌋, so e ≥ ⌊2n1/3⌋+ ⌊2n2/3⌋, and
it is easy to check, that for any n1, n2 ≥ 2, ⌊2n1/3⌋ + ⌊2n2/3⌋ ≥ ⌊2(n1 + n2 − 1)/3⌋.
Therefore, e ≥ ⌊2n1/3⌋ + ⌊2n2/3⌋ ≥ ⌊2(n1 + n2 − 1)/3⌋ = ⌊2n/3⌋. So, if G is not
essentially connected, then we reduce the problem and proceed by induction.
Assume the 3-simple 2-plane drawing G has a flag (u, uv). If d(v) = 1, then G is
isomorphic to K2 and the theorem holds. If d(v) = 2, then G contains a 2-propeller u, v, w
by Claim 2.5. Since G is essentially connected, but there is an isolated vertex in every
special cell, there is an isolated vertex x in the special cell of the 2-propeller. Therefore,
if d(v) = 2 and d(w) = 1, then G is isomorphic to a 2-propeller plus an isolated vertex
and we are done. If d(v) = 2 and d(w) > 1, then remove vertices u, v, x. We removed 3
vertices and 2 edges, so we can use induction.
In the rest of the proof, we assume that every leaf of G is adjacent to a vertex of degree
at least 3, and there is no 2-propeller subgraph in G. We give weight 3/2 to every edge. We
J. Barát and G. Tóth: Saturated 2-plane drawings with few edges 7
discharge the weights to the vertices and show that either every vertex gets weight at least
1, or we can prove the lower bound on the number of edges by induction.
Let uv be an edge. Vertex u gets 1/d(u) weight and v gets 1/d(v) weight from uv.
Every edge has a non-negative remaining charge.
If uv is a special edge, then it is easy to verify that uv bounds only one special cell,
and the special cell contains an isolated vertex by the assumption, just like in the proof of
Claim 2.3. In this case, edge uv gives the remaining charge to this isolated vertex. After
the discharging step, any vertex x with d(x) > 0 gets charge at least 1.
Now let x be an isolated vertex, its special cell being C. We distinguish several cases.
Case 1: The special cell C has two sides. Let u1v1 and u2v2 be the bounding edges.
They cross twice, in p and q say, so there are no further crossings on u1v1 and u2v2.
The four endpoints are either distinct, or two of them u1 and u2 might coincide, if G was
3-simple. Suppose the order of crossings on the edges is uipqvi, for i = 1, 2. If the vertices
u1 and u2 are distinct, then they can be connected along u1p and pu2. Therefore, u1 and
u2 are either adjacent or coincide in G. Similarly, v1 and v2 are also adjacent. Therefore,
all four endpoints have degree at least 2, and both u1v1 and u2v2 give at most charge 1/2
to its endpoints. Their remaining charges are at least 1/2, so x gets at least charge 1.
For the rest of the proof, suppose C is bounded by e1, e2, . . . , em in clockwise direction,
ei = uivi such that −−→uivi has C on its right.
Case 2: m = 3. If none of the bounding edges is a flag, then we are done since each
of those edges give weight at least 1/2 to x. Suppose that u1 is a leaf. We can connect u1
to v2 along segments of the edges u1v1 and u2v2. Since u1 is a leaf and the drawing was
saturated, u1 and v2 are adjacent, consequently v1 = v2. Similarly, we can connect u1 to
v3, so v1 = v2 = v3.
If u2 is not a leaf, then u1v1 and u3v3 both give at least 1/6 to x, and u2v2 gives at least
2/3, so we have charge at least 1 for x. The same applies if u3 is not a leaf. So assume u1,
u2 and u3 are all leaves. If there are no other edges in G, then we can see from the crossing
pattern that G is a 3-propeller and an isolated vertex. That is, n = 5 and e = 3 and the
required inequality holds.
Suppose there are further edges. By Claim 2.6, G is essentially connected. Since u1,
u2, u3 are leaves, v1 is a cut vertex. Let H1 = G \ {x, u1, u2, u3}. The induced subgraph
H1 has n − 4 vertices and e − 3 edges, and it is saturated. Therefore, by the induction
hypothesis, e− 3 ≥ f(n− 4). Notice that f(n) ≤ f(n− 4) + 3, consequently e ≥ f(n).
Case 3: m > 3. Each edge gives at least 1/6 charge to x by Claim 2.5. If an edge is not
a flag, then it gives at least 1/2 charge to x. If there is at least one non-flag bounding edge,
we are done. Suppose that each edge uivi is a flag (that is, d(ui) or d(vi) is 1). We may
also assume that u1 is a leaf. Now, as in the previous case, we can argue that v3 = v2 = v1.
It implies u2 and u3 are leaves, and by the same argument, v5 = v4 = v3 = v2 = v1.
We can continue and finally we obtain that all vi are identical and all ui are leaves. So
the vertices ui, vi 1 ≤ i ≤ m form a star, and they have the same crossing pattern as an
m-propeller. Therefore, ui, vi 1 ≤ i ≤ m span an m-propeller. We can finish this case
exactly as Case 2. If there are no further edges in G, then the graph is an m-propeller and
an isolated vertex. That is, n = m + 2 and e = m and the inequality holds. If there are
further edges, then v1 is a cut vertex, and we can apply induction. This concludes the proof
of Theorem 1.2.
8 Ars Math. Contemp. 24 (2024) #P1.05
Remarks
• We have established lower and upper bounds on the number of edges of a saturated,
k-simple, 2-plane drawing of a graph. As we mentioned in the introduction, this
problem has many modifications, generalizations. Probably the most natural modifi-
cation is that instead of graphs already drawn, we consider saturated abstract graphs.
A graph G is saturated l-simple k-planar, if it has an l-simple k-planar drawing but
adding any edge, the resulting graph does not have such a drawing. Let tlk(n) be
the minimum number of edges of a saturated l-simple k-planar graph of n vertices.
By definition, slk(n) ≤ tlk(n). We are not aware of any case when the best lower
bound on tlk(n) is better than for s
l
k(n). On the other hand, it seems to be much
harder to establish an upper bound construction for tlk(n) than for s
l
k(n). In fact,
we know nontrivial upper bounds only in two cases, t11(n) ≤ 2.64n + O(1) [3] and
t12(n) ≤ 2.63n+O(1) [1], the latter without a full proof.
It is known that a k-planar graph has at most c
√
kn edges [6], so tlk(n) ≤ c
√
kn, for
some c > 0.
Problem 1. Prove that for every c > 0, tlk(n) ≤ c
√
kn if k, l, n are large enough.
• For any n and k, the best known upper and lower bounds on slk decrease or stay the
same as we increase l. This would suggest that slk ≤ s
l−1
k for any n, k, l, or at least
if n is large enough, however, we cannot prove it.
Problem 2. Is it true, that for any k and l, and n large enough, slk ≤ s
l−1
k ?
ORCID iDs
János Barát https://orcid.org/0000-0002-8474-487X
Géza Tóth https://orcid.org/0000-0003-1751-6911
References
[1] C. Auer, F. J. Brandenburg, A. Gleißner and K. Hanauer, On sparse maximal 2-planar graphs,
in: W. Didimo and M. Patrignani (eds.), Graph Drawing, Springer Berlin Heidelberg, Berlin,
Heidelberg, 2013 pp. 555–556.
[2] J. Barát and G. Tóth, Improvements on the density of maximal 1-planar graphs, J. Graph Theory
88 (2018), 101–109, doi:10.1002/jgt.22187, https://doi.org/10.1002/jgt.22187.
[3] F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer and J. Reislhu-
ber, On the density of maximal 1-planar graphs, in: Graph drawing. 20th international sym-
posium, GD 2012, Redmond, WA, USA, Springer, Berlin, pp. 327–338, 2013, doi:10.1007/
978-3-642-36763-2 29, https://doi.org/10.1007/978-3-642-36763-2_29.
[4] S. Chaplick, F. Klute, I. Parada, J. Rollin and T. Ueckerdt, Edge-minimum saturated k-planar
drawings, 2021, arXiv:2012.08631 [math.CO].
[5] F. Klute and I. Parada, Saturated k-plane drawings with few edges, 2021,
arXiv:2012.02281 [math.CO].
[6] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997),
427–439, doi:10.1007/bf01215922, https://doi.org/10.1007/bf01215922.