ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 69–87
https://doi.org/10.26493/1855-3974.2226.e93
(Also available at http://amc-journal.eu)
On plane subgraphs of complete topological
drawings*
Alfredo Garcı́a Olaverri † , Javier Tejel Altarriba ‡
Departamento de Métodos Estadı́sticos and IUMA, University of Zaragoza, Spain
Alexander Pilz §
Institute of Software Technology, Graz University of Technology, Austria
Received 22 January 2020, accepted 15 October 2020, published online 17 August 2021
Abstract
Topological drawings are representations of graphs in the plane, where vertices are
represented by points, and edges by simple curves connecting the points. A drawing is
simple if two edges intersect at most in a single point, either at a common endpoint or at a
proper crossing. In this paper we study properties of maximal plane subgraphs of simple
drawings Dn of the complete graph Kn on n vertices. Our main structural result is that
maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected.
Besides, any maximal plane subgraph contains at least ⌈3n/2⌉ edges. We also address the
problem of obtaining a plane subgraph of Dn with the maximum number of edges, proving
that this problem is NP-complete. However, given a plane spanning connected subgraph of
Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a
side result, we also show that the problem of finding a largest compatible plane straight-line
graph of two labeled point sets is NP-complete.
Keywords: Graph, topological drawing, plane subgraph, NP-complete problem.
Math. Subj. Class. (2020): 05C10, 68R10
*This project has received funding from the European Union’s Horizon 2020 research and innovation pro-
gramme under the Marie Skłodowska-Curie grant agreement No. 734922.
†Supported by MINECO project MTM2015-63791-R and Gobierno de Aragón Grant E41-17 (FEDER).
‡Supported by MINECO project MTM2015-63791-R, Gobierno de Aragón Grant E41-17 and project
PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation.
§Supported by a Schrödinger fellowship of the Austrian Science Fund (FWF): J-3847-N35.
E-mail addresses: olaverri@unizar.es (Alfredo Garcı́a Olaverri), jtejel@unizar.es (Javier Tejel Altarriba),
apilz@ist.tugraz.at (Alexander Pilz)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
70 Ars Math. Contemp. 20 (2021) 69–87
1 Introduction
In a topological drawing (in the plane or on the sphere) of a graph, vertices are represented
by points and edges by simple curves connecting the corresponding pairs of points.Usually,
we only consider drawings satisfying some natural non-degeneracy conditions, in particular
a drawing is called simple (or a good drawing) if two edges intersect at most in a single
point, either at a common endpoint or at a crossing in their relative interior. When all
the edges of a topological drawing are straight-line segments, then the drawing is called a
rectilinear drawing or geometric graph.
In this paper we consider only simple topological drawings of the complete graph Kn
on n vertices. Simple topological drawings of complete graphs have been studied exten-
sively, mainly in the context of crossing number problems. It is well known that a drawing
minimizing the number of crossings has to be simple, and besides, if n ≥ 8, the drawings
of Kn minimizing that crossing number are not rectilinear. We refer the reader to [1, 3, 4]
for recent advances on the Harary-Hill conjecture on the minimum number of crossings of
drawings of Kn, and to the survey [22] for some variants on this crossing number problem.
The problem of enumerating all the non-isomorphic drawings of Kn has been studied
in [2, 12, 13, 18] (two drawings are isomorphic if there is a homeomorphism of the sphere
that transforms one drawing into the other).
Let Dn be a simple topological drawing of Kn. Herein, we consider graphs in con-
nection with their drawings, and in particular when addressing subgraphs of Kn we also
consider the associated sub-drawing of Dn. We are interested in crossing-free edge sets F
in Dn, and we will say that F is a plane subgraph of Dn. Crossing-free edge sets in Dn
have attracted considerable attention, in part because problems on embedding graphs on a
set of points usually generalize to finding plane subgraphs of Dn. For instance, the problem
of computing the maximum number of plane Hamiltonian cycles that a simple drawings Dn
can contain, is a generalization of the same problem considering only rectilinear drawings
of Kn. And this last is the (open) problem of computing the maximum number of simple
n-gons that can be formed on n points in the plane.
There are relatively few results on plane subgraphs of Dn. It is well known that in any
drawing Dn of Kn, there are plane subgraphs with 2n− 3 edges, and that there are at most
2n−2 edges uncrossed by any other edge [6, 8, 19]. Pach, Solymosi, and Tóth [14] showed
that any Dn has Ω
(
log1/6(n)
)
pairwise disjoint edges. This bound was subsequently
improved in [5, 16, 23]. The current best bound of Ω(n1/2−ϵ) is by Ruiz-Vargas [20].
However, the much stronger conjecture that any simple drawing Dn of Kn contains a plane
Hamiltonian cycle remains unproved, although it has been verified for n ≤ 9, see [2].
In the course of their work on disjoint edges and empty triangles in Dn, Fulek and
Ruiz-Vargas [6] showed the following lemma.1
Lemma 1.1 (Fulek and Ruiz-Vargas [6]). Between any plane connected subgraph F of Dn
and a vertex v not in F , there exist at least two edges from v to F that do not cross F .
This result can be used to build large plane subgraphs. For instance, we can begin with
F consisting of only one edge, then for each vertex v not in F , we add to F the edges
from v to F not crossing F . In this way, we will obtain a maximal plane subgraph: a plane
subgraph F such that any edge e /∈ F crosses some edge of F .
1Their lemma is actually more general. It does not require F and v to be elements of a drawing of Kn, but
rather of a drawing that contains all edges from v to vertices of F .
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 71
In Section 2 of this work, we extend that Lemma 1.1 to arbitrary (not necessarily con-
nected) plane subgraphs. Further, in Section 3, we prove that any plane subgraph of Dn
can be augmented to a 2-connected plane subgraph of Dn. A consequence of this result is
that maximal plane subgraphs contain at least min(⌈3n/2⌉, 2n− 3) edges, and this bound
is tight. Maximal plane subgraphs of Dn have other interesting properties. For example,
we show that, when removing two edges from a maximal plane subgraph, it either stays
connected or one of the two components is a single vertex. Another consequence of the
previous results is that for every vertex v of a drawing Dn, there is a plane subgraph of Dn
consisting of the n-vertex star of edges incident to v, plus the edges of a spanning tree on
the n− 1 vertices of V \ {v}.
The problem setting changes when we want our plane graphs not only to be maximal,
but also to contain the maximum number of edges. While for geometric graphs, every max-
imal plane subgraph is a triangulation and thus also has a maximum number of edges, the
situation is different for plane subgraphs of Dn. In Section 4, we will prove that comput-
ing a plane subgraph of Dn with maximum number of edges is an NP-complete problem.
However, if a connected plane spanning subgraph F is given, we can adapt a classic algo-
rithm from computational geometry to show that a maximum plane augmentation of F can
be found in O(n3) time.
As a side result, we also show that the problem of finding a largest compatible plane
graph on two labeled point sets is NP-complete.
Finally, going back to Lemma 1.1, we give an O(n) algorithm to compute all the edges
from a vertex v to a plane connected subgraph F that do not cross F .
2 Adding a single vertex
We now discuss a generalization of Lemma 1.1 to arbitrary plane subgraphs. This general-
ization will also follow independently from Theorem 3.1. Still, the following proposition
gives further insight on the position of the uncrossed edges around the vertex v, which
might help in the construction of algorithms.
We assume that a simple topological drawing Dn of Kn in the plane is given, with
vertex set V = {v1, . . . , vn}. If x1, x2 are two points on an edge e of Dn (not necessar-
ily the endpoints of e), by line x1x2 we mean the portion of the curve e of the drawing
placed between the points x1 and x2. For a vertex v, the star graph with center v is the
subgraph formed by the edges connecting v to all the other vertices. We denote this set of
edges by S(v), usually call rays to these edges emanating from v, and we suppose that the
rays of S(v) are (circularly) clockwise ordered. By the clockwise range [vp, vq] of S(v)
we mean the ordered set of rays placed clockwise between vp and vq, including rays vp
and vq. When vp or vq or both are not included in that ordered set of rays, we will use
(vp, vq], [vp, vq) or (vp, vq), respectively. In the same way, we can define counterclock-
wise ranges.
In the rest of this section, we suppose F is a given plane subgraph of Dn and v a vertex
not in F . In the figures, we use red color for the edges of F , so we usually call them red
edges. We say a ray vr of S(v) is uncrossed if it does not cross any edge of F .
Suppose that the ray vr crosses some edge of F , let e = pq be the first edge of F
crossed by vr, and let x be the first crossing point. Without loss of generality, we can
suppose that the rays vr, vp, and vq appear in this clockwise order in S(v). See Figure 1.
We define the clockwise range Rcw of rays centered at v corresponding to the crossing
72 Ars Math. Contemp. 20 (2021) 69–87
v
pq
r
qp
r
RcwRccw
x x
Rccw
Rcw
yy′
ll′
l′l
y′y
v
Tcw
Tcw
Figure 1: The clockwise and counterclockwise ranges of a first crossing.
x in the following way: if no ray in the clockwise range (vp, vq) crosses the edge pq
between x and p, then Rcw is the range (vr, vp]; otherwise, (some rays in the clockwise
range (vp, vq) cross the line xp), Rcw is the clockwise range (vr, vl], where vl is the last
ray in (vp, vq) crossing the line xp. That implies that if vl crosses xp at the point y, among
the intersection points of rays in (vp, vq) with the line xp, the closest to x is y. See Figure 1.
Analogously, the range Rccw is defined either as the counterclockwise range (vr, vq] if no
edge in the counterclockwise range (vq, vp) crosses the line xq, or as the counterclockwise
range (vr, vl′], where vl′ is the ray in the counterclockwise range (vq, vp) crossing the line
xq in a point y′ closest to x. By definition, the rays vr, vp, vl, vl′, vq appear clockwise in
that order around v. Observe that Rcw and Rccw are disjoint sets and they are also nonempty,
as vp is in Rcw and vq is in Rccw. The following result generalizes Lemma 1.1.2
Proposition 2.1. Suppose the ray vr first crosses the edge e of F at the point x. Let Rcw
and Rccw be the clockwise and counterclockwise ranges of rays of v corresponding to that
crossing. Then, each one of these two ranges contains an uncrossed ray. As a consequence,
S(v) contains at least two uncrossed rays.
Proof. We prove the statement for Rcw, the proof for Rccw is identical.
Observe that by definition, no red edge can cross the line vx, and a ray in the clockwise
range (vq, vr] cannot cross the line xp. Let y be the crossing point between the red edge
e = pq and the ray vl. When Rcw is (vr, vp] (i.e., no ray in the clockwise range (vp, vq)
crosses xp), then we identify the points p, l and y. The lines vx, xy and yv define a simple
closed curve, that divides the plane into two regions Tcw, Tcw, where Tcw is the region not
containing the point q.
From the definition of Tcw, it follows that a ray containing a point placed in the interior
of Tcw must be in the range Rcw. Besides, a red edge can cross the boundary of that region
only through the line yv, and hence, if a red edge e crosses yv, one endpoint of e must be
inside Tcw the other one in Tcw.
The proof is done by induction on |Rcw|, the number of rays in that range. So, first sup-
pose that the only ray in the range Rcw is the ray vp. In this case, Tcw is the region bounded
by the closed curve vx, xp, pv not containing the point q. This region cannot contain any
2Like Lemma 1.1, this result is more general. It does not require F and v to be elements of a drawing of Kn,
but rather of a drawing that contains all edges from v to vertices of F .
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 73
vertex r′ of F , because then vr′ would be in Rcw, therefore vp must be uncrossed. This
proves the base case of the induction.
Now suppose that the proposition has been proved for any clockwise range containing
less than |Rcw| rays. Let vr′ be the first ray of Rcw. Of course, if the ray vr′ is uncrossed,
the proof is done, so we can suppose that the ray vr′ is first crossed by a red edge e′ at a
point x′. We are going to prove that the clockwise range R′cw corresponding to the crossing
x′ is strictly contained in Rcw. Then, by induction, R′cw contains an uncrossed ray, and thus
also Rcw. To prove that R′cw ⊂ Rcw strictly, it is enough to prove that the clockwise last ray
of R′cw is contained in Rcw.
Let us first analyze Case A: when the edge e′ is precisely the edge e. See Figure 2.
In this case, if x′ is between x and y, then the clockwise range R′cw corresponding to the
v
pq
r
x
v
pq
r
x
r′
r′y
l
x′ y x′
Figure 2: Case A, the ray vr′ first crosses the edge e = pq.
new crossing point x′ is precisely Rcw minus its first ray vr′. And if x′ is between y and p,
then all the points of the line x′p (including point p) are in the interior of the region Tcw,
therefore the corresponding last ray of R′cw has to be in Rcw. Thus, in both subcases is
R′cw ⊂ Rcw strictly.
Suppose now Case B: when e′ ̸= e. See Figure 3. Clearly, at least one endpoint of e′ is
v
pq
r
x
Subcase B1
v
pq
r
x
Subcase B2
r′
x′
x′
p′
q′
Figure 3: Case B, the ray vr′ first crosses an edge e′ ̸= e.
in Tcw, as otherwise the ray vl would be crossed twice by e′. Hence, either both endpoints
are in Tcw, subcase B1, or one of them is in Tcw and the other one in Tcw, subcase B2. In
subcase B1, the entire edge e′ = p′q′ must be inside Tcw. Therefore, any ray containing a
74 Ars Math. Contemp. 20 (2021) 69–87
point of e′ must be in Rcw. In particular, the last ray of R′cw must be in Rcw, and hence,
R′cw is strictly contained in Rcw.
In subcase B2, an endpoint, p′, of e′ is inside Tcw and the other, q′, is in Tcw. Observe
that the ray vp′ must be in Rcw, however the ray vq′ cannot be in Rcw because the range
(vr, vr′) is empty, and a ray in [vr′, vl] finishing at q′ has to cross the edge e′. See Figure 3.
Therefore, the rays vr′, vp′, vq′ appear clockwise around v in this order. Hence, the last
ray of R′cw is either vp
′ or a ray crossing the line x′p′. In any case, as the line x′p′ is inside
Tcw, this last ray of R′cw has to be in Rcw. This completes the proof.
3 Structure of maximal plane subgraphs
Let Dn be an arbitrary simple drawing of Kn. In this section, we identify several structural
properties of maximal plane subgraphs of Dn, using Lemma 1.1 or Proposition 2.1 as
our main tool. Maximal plane subgraphs turn out to be 2-connected. While there are
examples of maximal plane subgraphs that are not 3-connected, we elaborate further on
the structure, showing that a maximal plane subgraph is either 3-edge-connected or has a
vertex of degree 2.
Theorem 3.1. A maximal plane subgraph of Dn is spanning and 2-connected.
Proof. The proof is by induction on n. The result is obviously true for n ≤ 3. For n > 3,
assume there exists a maximal plane subgraph F that is not 2-connected, and let us see that
a contradiction is reached.
We first claim that, under this assumption, F has no vertices of degree less than 3.
Suppose the contrary, that the vertex v has degree ≤ 2. Let F ′ be the subgraph of F
obtained after removing the vertex v, and let F ′ be a maximal plane subgraph (in the
drawing Dn−{v} of Kn−1) containing F ′. By the induction hypothesis, F ′ is 2-connected.
We observe that v cannot have (in F ) degree less than 2, since applying Lemma 1.1 to v
and F ′ would give two edges at v not crossing F , contradicting the maximality of F .
So suppose v has degree 2. As we assume that F is not 2-connected, F ′ cannot be 2-
connected. However, F ′ is 2-connected, and hence there exists an edge e′ in F ′ − F ′. By
the maximality of F , e′ must cross at least one edge vw of F incident to v. But applying
Lemma 1.1 to v and F ′ gives at least two edges incident to v not crossing F ′. These two
edges and also vw do not cross F , contradicting the maximality of F . Therefore, the claim
follows.
Assume now that F is not connected. Let C1, C2 be two connected components of F .
As all vertices have (in F ) degree at least 3, C1 cannot be an outerplanar graph, and it has
more than one face. Without loss of generality, we can suppose that C2 is in the unbounded
face of C1. Let v1 be an interior vertex of C1, F ′ the graph obtained from F by removing
v1, and f1 the face of F ′ containing v1. The face containing C2 remains unchanged by the
removal of v1. By induction, F ′ can be completed to a 2-connected plane graph F ′, and
due to the maximality of F , all the edges in F ′ − F ′ should be in the face f1. But then, as
C2 is outside f1, F ′ could not be connected, a contradiction. Thus, F has to be connected.
By a similar reasoning we arrive at our contradiction to F not being 2-connected. A
block is a 2-connected component of a graph, and a leaf block is a block with only one cut
vertex. Since F is not 2-connected, it has at least two leaf blocks B1 and B2. As all vertices
have degree at least 3, B1 cannot have all its vertices on the same face. Again, without loss
of generality, we can suppose B2 is in the outer face of B1, and there is an interior vertex
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 75
v1 of B1. Removing v1 from F , we obtain a plane graph F ′ that has a face f1 containing
v1, and F ′ is contained in a maximal plane graph F ′ that is 2-connected. Again, by the
maximality of F , all the edges in F ′ − F ′ must be in f1, implying that B2 is still a block
of F ′, contradicting the fact that F ′ is 2-connected. Hence, F must be 2-connected.
Theorem 3.1 can be used to obtain more properties of maximal plane subgraphs.
Lemma 3.2. If a maximal plane subgraph F of Dn contains a vertex v of degree 2, then
the subgraph of F obtained after removing v is also maximal in Dn − {v}.
Proof. Suppose the contrary. Remove v from F to obtain F ′ and let F ′ be a maximal plane
graph containing F ′. As F is maximal but F ′ is not, F ′ − F ′ must contain an edge e′ that
crosses some edge vw of F . But by Lemma 1.1 there are at least two edges from v to F ′.
These two edges and also vw do not cross F , contradicting the maximality of F .
Proposition 3.3. Any maximal plane subgraph F of Dn with n ≥ 3 must contain at least
min(⌈3n/2⌉, 2n− 3) edges. This bound is tight.
Proof. Suppose that n > 3 and F0 = F has a vertex v0 with degree 2. By removing this
vertex we obtain another maximal plane graph F1 (maximal on n−1 points), and if F1 is in
the same conditions (with at least three vertices and a vertex v1 of degree 2), by removing
v1 we obtain a new maximal plane graph F2, and so on. We finish this process in a step k
because either Fk only has three points, or all the points of Fk have degree at least 3. In the
first case, the original graph F contains n = k + 3 vertices and 2k + 3 edges, so 2n − 3
edges. In the second case, F must contain at least 2k + ⌈3(n − k)/2⌉ edges, this amount
reaching its minimum value when k = 0.
Finally, let us see that the bound is tight. If 2 ≤ n ≤ 6, then a straight-line drawing
on n points in convex position gives the bound 2n − 3 ≤ ⌈3n/2⌉. If n > 6 and n is an
even number, a drawing like the one shown in Figure 4 proves that the bound ⌈3n/2⌉ is
tight. The drawing is done on n = 2(k + 1) points in convex position, that clockwise are
u0
u1 uk
v1 vk
vk+1
Figure 4: A drawing of Kn. The missing edges should be drawn as straight-line segments
inside the convex hull of the set of points. The black edges form a maximal plane subgraph
with ⌈3n/2⌉ edges.
76 Ars Math. Contemp. 20 (2021) 69–87
denoted by u0, u1, u2, . . . , uk, vk+1, vk, . . . , v2, v1. Let C denote the convex hull of that
set of points. All the edges of Dn are drawn straight-line except for the 2(k − 1) edges
uivi+1, viui+1, i = 1, . . . , k − 1, and the edge u0vk+1, that are drawn outside C as shown
in Figure 4. Observe that the 2(k − 1) edges uivi+1, viui+1, i = 1, . . . , k − 1, are the
diagonals of the (k−1) quadrilaterals uiui+1vi+1vi, with uivi+1 only crossing viui+1 and
u0vk+1, for i = 1, . . . , k − 1. Clearly, straight-line edges can cross at most once, and the
edges placed outside C, by construction, cross at most once. The graph F formed by the
2(k + 1) edges on the boundary of C, the k edges uivi, i = 1, . . . , k, and the edge u0vk+1
is clearly plane and maximal, since the other straight-line edges cross at least one edge
uivi, and the non-straight-line edges cross the edge u0vk+1.
If n is odd, we can add to the previous set a point u′0 between u0 and u1, very close
to segment u0u1, but keeping all the 2k + 3 points in convex position. By connecting u′0
with straight lines to the rest of the points, we obtain a simple topological drawing of Kn
on this set of n = 2k+ 3 points, and a new maximal plane graph is obtained by adding the
edges u0u′0,u
′
0u1 to the above graph F . This new maximal plane subgraph also has ⌈3n/2⌉
edges.
We mention another interesting implication of Theorem 3.1. For a vertex v, we can
augment the star S(v) to a 2-connected plane graph F , and since F \ {v} is connected, it
contains a spanning tree. So we have
Corollary 3.4. For each vertex v there exists a spanning tree Tv of V \ {v}, such that the
edges of S(v) ∪ Tv form a plane subgraph of Dn.
Our next results are about diagonals on plane cycles. Let C = (v1, v2, . . . , vk) be a
plane cycle of Dn. A diagonal of C is an edge of Dn connecting two non-consecutive
vertices of C. It was previously known that, even for the case where there are diagonals
intersecting both faces of C, there are at least ⌈k/3⌉ of them not crossing C (cf. [17,
Corollary 6.6]). Proposition 3.3, applied to the subdrawing induced by the vertices of C,
directly implies the following result.
Corollary 3.5. Let C = (v1, v2, . . . , vk) be a plane cycle of Dn, with k ≥ 6. Then, there
exists a set D of diagonals, with |D| ≥ ⌈k/2⌉, such that the subgraph C ∪D is plane.
It turns out that the structure of the diagonals of a cycle, as shown in the next lemma, is
useful for our further results.
Lemma 3.6. Let C = (v1, v2, . . . , vk) be a plane cycle of Dn, k ≥ 3, dividing the plane
into two faces f1 and f2. If there is no diagonal of C entirely in f1, then all the diagonals
of C are entirely in f2.
Proof. The proof is by induction on k. For k < 5 the statement is obvious, so suppose
k ≥ 5 and consider only the subdrawing Dk induced by the vertices of C. Suppose C ∪D
is a maximal plane graph of Dk, so necessarily, D consists of diagonals placed on f2.
Let d be a diagonal of D connecting two vertices at minimum distance on the graph C.
Lemma 3.2 implies that in a maximal plane subgraph, vertices with degree 2 cannot be
adjacent. Therefore, diagonal d has to connect two vertices at distance 2 on C. Without
loss of generality, suppose d = vkv2 and let ∆ be the triangle vkv1v2. Then, the cycle
C1 = (v2, v3, . . . , vk) with k − 1 vertices has the faces f ′1 = f1 +∆ and f ′2 = f2 −∆.
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 77
We claim that there cannot be diagonals of C1 entirely in f ′1. Such a diagonal e en-
tirely in f ′1 would have to intersect ∆. Then, adding e to C ∪ {vkv2} and removing all
edges crossed by e, we would obtain a plane graph F in which v1 has degree 0 or 1. By
Lemma 1.1, there must be another edge between v1 and C1, and this edge would be a di-
agonal of C entirely in f1, a contradiction. Thus, by induction, any diagonal vivj of C1 is
entirely in f ′2 and hence also in f2.
It remains to see that the diagonals with endpoint v1 are also in f2. By our induction
hypothesis, the diagonal v2v4 is in f ′2 and thus also in f2. Hence, arguing as before on the
cycle C3 = (v1, v2, v4, . . . , vk), we deduce that all the diagonals of C3 incident to v1 must
be in f2. So it remains to see that the diagonal v1v3 is also in f2. But v3v5 is also in f ′2, so
it is in f2, and again applying the same reasoning on the cycle (v1, v2, v3, v5, . . . , vk), all
the diagonals of this cycle not incident to v4 have to be in f2.
To prove the next result, we recall some definitions and properties of any 2-connected
graph G = (V,E). Two vertices v1, v2 are called a separation pair of G if the induced
subgraph G \ {v1, v2} on the vertices V \ {v1, v2} is not connected. Let G1, . . . , Gl be the
connected components of G \ {v1, v2}, with l ≥ 2. For each i ∈ {1, . . . , l}, let G∗i be the
subgraph of G induced by V (Gi) ∪ {v1, v2}. Observe that G∗i contains at least one edge
incident to v1 and at least another edge incident to v2.
Theorem 3.7. Let F be a maximal plane subgraph of Dn, n ≥ 3. Then, for each separation
pair v1, v2 of F , at least one of the subgraphs F
∗
i must be 2-connected.
Proof. Suppose that v1, v2 is a separation pair of F , and let F 1, F 2, . . . , F l be the con-
nected components of F \ {v1, v2}, l ≥ 2. Since F is 2-connected, the graph F \ {v2} is
connected with v1 as a cut vertex. As F is plane, we can suppose that v1 is in the outer face
of F \ {v2} (v2 must be inside that face) and that clockwise around vertex v1 first there
appear the edges from v1 to some vertices of the component F 1, then edges connecting v1
to some vertices of F 2 and so on. See Figure 5.
v1
v2
F ∗3 F
∗
2 F ∗1 u1u2
u3
R1R2R3
Figure 5: A plane graph with separating pair v1, v2 and three subgraphs F ∗i , none of them
2-connected. This plane graph cannot be maximal.
Now suppose that none of the subgraphs F
∗
i is 2-connected. Then each subgraph F
∗
i
contains at least one cut vertex ui. Since F i is connected and there exist edges in F
∗
i
incident to v1 and v2, vertex ui is different from v1 and v2. On the other hand, a connected
component C of F
∗
i \{ui} must contain at least one of v1 or v2 because otherwise, C would
be a connected component of F \ {ui}, contradicting that F is 2-connected. Therefore,
F
∗
i \ {ui} has exactly two components, one containing v1, the other one containing v2.
78 Ars Math. Contemp. 20 (2021) 69–87
This also implies that the edge v1v2 of Dn cannot belong to F , and that the cut-vertex ui
is in the outer face of F
∗
i (and hence in the outer face of F \ {v2}) since v1 and v2 are in
the outer face of F \ {v2}. See Figure 5.
In the graph F \ {v2}, around the vertex v1, the edges to vertices of F1 first appear,
then the edges to vertices of F2 and so on. Therefore, when we add to that graph the vertex
v2 and all the edges connecting v2 to each component Fi to obtain F , v1 and v2 must be
in the faces Ri of F defined as the regions placed between the last edge from v1 to F i and
the first edge from v1 to F i+1, for i = 1, . . . , l, and the vertex ui must be in the faces Ri
and Ri−1. However, by the maximality of F , no edge of Dn is entirely in any of those
faces Ri. Then, Lemma 3.6 implies that no point of the edge v1v2 of Dn can be inside any
face Ri. See Figure 5. Thus, v1v2 must begin between two edges v1v, v1v′ with both v
and v′ belonging to a common connected component F i. However, since ui belongs to the
faces Ri−1 and Ri, any curve from v1 to v2 passes either through the point ui or through
the interior of Ri−1 or Ri, which contradicts either the simplicity of Dn or Lemma 3.6.
Therefore, if none of the subgraphs F
∗
i is 2-connected, F cannot be maximal.
We call a graph essentially 3-edge-connected if it stays connected after removing any
two edges not sharing a vertex of degree 2 (i.e., the graph either stays connected or one
component is a single vertex). Theorem 3.7 implies that a maximal plane subgraph is
essentially 3-edge-connected:
Theorem 3.8. Any maximal plane subgraph, F , of a simple topological drawing of Kn is
essentially 3-edge-connected.
Proof. If the removal of two edges v1v2 and v′1v
′
2 from the plane subgraph F results in two
non-trivial components C1, C2 (see Figure 6), then v1, v′2 is a separation pair of F , that has
as induced subgraphs C1∪{v′1v′2} and C2∪{v1v2}, neither of which is 2-connected. Then,
by Theorem 3.7, F cannot be maximal.
v1
R1
R2
C1
C2
v2
v′1 v′2
Figure 6: A graph that is not essentially 3-edge-connected. The induced subgraphs of the
separation pair v1, v′2 are subgraph C1 plus edge v
′
1v
′
2 and subgraph C2 plus edge v1v2. By
Lemma 3.6, the edge v1v′2 of Dn cannot enter either the R1 face or the R2 face, which is
impossible in any good drawing.
4 Adding the maximum number of edges
Now, assume that a plane subgraph of Dn is given, and we want to add the maximum
number of edges keeping plane the augmented graph. Clearly, the decision of adding one
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 79
edge will in general block other edges from being added. We will see that the complexity
of an algorithm solving this problem highly depends on whether the given subgraph is
connected or not.
Before talking about algorithms and their complexity we have to talk about what infor-
mation of the drawing Dn we will need to compute plane subgraphs. For each vertex v, the
clockwise cyclic order of edges of S(v) is usually given as a permutation of V \ {v} (that
is to be interpreted circularly) of the second vertices of all edges of S(v). That permutation
of V \ {v} is called the rotation of v, and the rotation system of a drawing Dn consists of
the collection of the rotations of each vertex v of Dn. It is well-known that from the in-
formation provided by the rotation system, one can determine whether two edges cross or
not, and therefore, that information is enough to compute plane subgraphs. See [7, 11, 15].
From the rotation system, we can also compute (in O(n2) time) the inverse rotation system
that, for each vertex vi and index j, j ̸= i, gives the position of vj in the rotation of vi.
When we say that a drawing Dn is given, we mean that we know the rotation system
and the inverse rotation system of Dn. Using these two structures, one can determine
whether two edges cross, in which direction an edge is crossed, and in which order two
non-crossing edges cross a third one in constant time [11].
Theorem 4.1. Let F be a connected spanning plane subgraph of Dn. Then there is an
O(n3) time algorithm to augment F to a plane subgraph F ′ of Dn with the maximum
number of edges.
Proof. As F is plane and thus contains a linear number of edges, we can identify all the
edges of Dn not crossed by F in O(n3) time. This also gives us, for each such edge, the
face of F in which it is contained, and we can also compute for each face f of F the set ∆f
of edges of Dn entirely inside f . Clearly, each face of F can be considered independently,
adding the maximum number of edges in it.
Let f be a face of F . For simplicity, we assume f to be bounded by a simple cycle
(v1, . . . , vk). Other cases can be solved similarly by an appropriate “splitting” of edges
having f on both sides. Disregarding Dn, consider the rectilinear drawing Dk obtained
from k points p1, . . . , pk placed on a circle C, and assign to each edge pipj of Dk weight
0 if vivj is in ∆f , weight 1 otherwise. Observe that two edges of ∆f cross properly, if and
only if, the corresponding 0-weight edges in circle C cross properly. It is well-known that
a minimum-weight triangulation in Dk can be obtained in O(k3) time [9] by a dynamic
programming algorithm, and this triangulation gives a plane set of 0-weight edges with
maximum cardinality. Hence, the corresponding edges of ∆f form a plane set of edges
entirely inside face f with maximum cardinality.
In contrast to this result, the problem becomes NP-complete when the subgraph F is
not connected.
Theorem 4.2. Given a simple topological drawing Dn of Kn and a cardinality k′, it is
NP-complete to decide whether there is a plane subgraph that has at least k′ edges.
Proof. We give a reduction from the independent set problem on segment intersection
graphs (SEG problem), which is known to be NP-complete [10]: Given a set S of s seg-
ments in the plane that pairwise either are disjoint or intersect in a proper crossing, and an
integer k > 0, is there a subset of k disjoint segments?
80 Ars Math. Contemp. 20 (2021) 69–87
For each instance of a SEG problem, we are going to build, in polynomial time, a
drawing Dn of Kn and an integer k′ such that the instance of the SEG problem has a Yes
answer, if and only if, the drawing Dn contains a plane subgraph with k′ edges.
Let vi, ti be the endpoints of each segment si, i = 1, . . . , s, of S. We can suppose that
these endpoints are in general position and that their convex hull is a triangle. Thus, for
each endpoint vi, we can find a disc Bi centered at vi, such that any straight line connecting
two endpoints of S different from vi does not cross Bi.
In each disc Bi, we place two points ui, wi very close to the segment viti, in such a
way that when connecting the point vi with straight-line segments to all the other points, the
segments viui, viti, viwi are clockwise consecutive. In other words, the clockwise wedge
defined by the half-lines viui, viwi only contains the endpoint ti. See Figure 7.
ui
vi wi
ti
ui
vi wi
ti
Figure 7: Drawings Dn (left) and Dn (right). The gray wedge only contains the endpoint
ti. In Dn, the dashed edges need to take a detour to avoid intersecting the edge uiwi twice.
Consider the rectilinear drawing Dn obtained by connecting the n = 4s points vi, ui,
wi, ti. In Dn, maximal plane graphs are triangulations, but we are going to consider only
the family Γ of plane triangulations of Dn containing the 2s edges uivi, wivi. The weight
of a triangulation of Γ is the number of edges viti that it contains. Clearly, in the set S
there are k disjoint segments, if and only if, there is a triangulation in Γ with weight k.
Now, consider the drawing Dn obtained from Dn doing the following changes:
For i = 1, . . . , s, only the edges of the star S(ui) crossing viwi, the edges of the star
S(wi) crossing uivi, and the edge uiwi are modified.
Suppose that in S(ui) after uivi are clockwise the edges uip1, . . . , uipk, uiwi, where
each uipj has to cross viwi. Let vipi1 , vipi2 . . . , vipik be the clockwise ordered edges
of S(vi) with endpoint one of the vertices pi. Then, we modify Dn by redrawing uipi1
following first the line uivi until point vi, then turning around vi and following the line
vipi1 , in such a way that in the rotation of ui the new edge uipi1 is placed just before uivi.
See Figure 7, right. The new drawing obtained is simple, because no edge crosses both uivi
and vipi1 , edges uipj cannot cross vipi1 and none edge of S(pi1) can cross uivi. Moreover,
the number of crossings in the edge viwi has decreased by one. We repeat the same process
for the edge uipi2 (the new edge uipi2 is placed just before uivi in the rotation of ui ), then
uipi3 , and so on. The same process can be done with the edges wiqj crossing uivi. See
Figure 7, right. Finally, we can redraw uiwi in the same way, following the edge uivi then
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 81
turning around vi following edge viwi. If we do this process for all the edges crossing viui
or uiwi, i = 1, . . . , s, at the end we obtain the simple drawing Dn. By construction, in
Dn, neither the edges viui nor the edges viwi are crossed by any other edge.
Now, let us see that Dn has a triangulation of the family Γ of weight k, if and only if,
Dn has a plane subgraph of size k′, with k′ = 3n− 6− (s− k) = 11s− 6 + k. Suppose
Dn has a triangulation F with weight k. This means that F contains (s − k) edges uiwi.
By removing from F these uiwi edges, we obtain a plane set F ′ of edges, where no edge
of F ′ has been modified to obtain the drawing Dn. Therefore, the edges of F ′ also form a
plane subgraph in Dn of size 3n− 6− (s− k) = 11s− 6 + k.
Conversely, suppose Dn contains a plane subgraph with 3n−6−(s−k) edges. Since the
edges uivi, wivi are not crossed by any edge of Dn, they must belong to any maximal plane
graph of Dn. Therefore, Dn has a plane subgraph F containing all the edges uivi, viwi
and of size k′ ≥ 3n − 6 − (s − k). As the wedge viwi, viui only contains point ti, if the
edge viti is not in F , then, the face of F containing the edges viui and viwi cannot be
a triangle. But, if a plane graph on n vertices contains more than (s − k) non-triangular
faces, its maximum number of edges is < 3n− 6− (s− k). As a consequence, viti is not
in F for at most (s − k) indices i, or equivalently, the plane subgraph F contains at least
k edges viti. This means that we can obtain a triangulation of the family Γ of weight k by
including k of these non-crossing edges.
Note that in the straight-line setting, we can always draw a triangulation of the underly-
ing point set, which contains the maximum number of edges. However, this is not the case
for simple topological drawings. We were not able to come up with a reduction solving the
following problem.
Problem 4.3. What is the complexity of deciding whether a given Dn contains a triangu-
lation, i.e., a plane subgraph whose faces are all 3-cycles?
Our reduction can also be adapted for a related problem on compatible graphs. We leave
the realm of general simple topological drawings and consider the following problem in the
more specialized setting of geometric graphs (rectilinear drawings). Let P = {p1, . . . , pn}
and P ′ = {p′1, . . . , p′n} be two sets of points in the plane. A planar graph is compatible
if it can be embedded on both P and P ′ in a way that there is an edge pipj if and only if
there is an edge p′ip
′
j . Saalfeld [21] asked for the complexity of deciding whether two such
point sets (with a given bijection between them) have a compatible triangulation. We will
say that triangulations F of P and F ′ of P ′ have k′ compatible edges when there exists a
subset of k′ edges pipj of F , such that their images, edges p′ip
′
j , are edges of F ′.
We can show the NP-completeness of the following optimization variant of the prob-
lem. (However, as the similar Open Problem 4.3, Saalfeld’s problem remains unsolved.)
Theorem 4.4. Given two point sets P = {p1, . . . , pn} and P ′ = {p′1, . . . , p′n} and the in-
dicated bijection between them, as well as a cardinality k′, the problem of deciding whether
P and P ′ admit two triangulations with k′ compatible edges is NP-complete.
Proof. We follow the idea of the proof of Theorem 4.2, and use a reduction from the SEG
problem. Suppose that an instance of the SEG problem is given: a set S of s segments in
the plane that pairwise either are disjoint or intersect in a proper crossing, and an integer
k > 0. We will build two sets of points P = {p1, . . . , pn} and P ′ = {p′1, . . . , p′n} and
obtain an integer k′ such that the SEG problem has answer Yes if and only if, P and P ′
admit two triangulations with k′ compatible edges.
82 Ars Math. Contemp. 20 (2021) 69–87
Let P be the set of n = 5s points formed by the vi, ti, ui, wi (i = 1, . . . , s) points
obtained from S as in the above Theorem 4.2, plus s points ṽi, where each point ṽi is
placed inside the triangle viuiwi very close to the point vi, to the right of the oriented line
viti, in such a way that in the wedge defined by the half-lines ṽiui, ṽiwi the only point of
P is ti, and the wedges uivi, uiṽi and wiṽi, wivi do not contain points of P . See Figure 8,
left. By construction, any triangulation F of the set of points P must contain the edge viṽi.
Observe that if the edge tivi is in F , then the edge tiṽi has to be also in F . Also note that
uiwi is only crossed by the edges tivi and tiṽi.
ui
vi wi
ti
ṽi
p
ui
vi wi
ti
ṽ′i
p
Bi Bi
Figure 8: The point sets P (left) and P ′ (right).
In the same way, let P ′ be the set of n = 5s points vi, ti, ui, wi, ṽ′i (i = 1, . . . , s), where
now each point ṽ′i is placed outside the triangle viuiwi, very close to the intersection point
of uiwi with viti, to the right of the line viti, and satisfying that any clockwise triangle
uiwip contains inside the point ṽ′i. See Figure 8, right. The bijection between the points
of P and P ′ is the obvious one, to each point ṽi of P corresponds point ṽ′i of P
′, for any
other point its image is itself.
To prove the statement of the theorem, it is enough to prove the following:
If in the set S there are k disjoint segments, then there are triangulations F and F ′
of the sets P and P ′, respectively, with k′ = 3n − 6 − (s − k) compatible edges. And
reciprocally, if F and F ′ contain k′ = 3n− 6− (s− k) compatible edges, then S contains
k disjoint segments.
Suppose first that S contains a set D of k disjoint segments viti. Let P0 be the set of 4s
common points of P and P ′ (all the points vi, ui, wi, ti). We build a triangulation F0 of P0
in the following way. If viti is in D, then we include the edges viti, viui, viwi, tiui, tiwi
in F0. If viti is not in D, then we include the edges uivi, viwi, wiui in F0. After that, we
add edges in an arbitrary way until obtaining a triangulation F0 of P0. Now, to obtain F
and F ′, we add the points ṽi and ṽ′i to F0 and retriangulate the triangular faces where they
are. If the edge viti is in D, then the points ṽi, ṽ′i are both in the triangle uiviti. So, by
adding the point ṽi and the three edges ṽiui, ṽivi, ṽiti to F0, or the point ṽ′i and the three
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 83
edges ṽ′iui, ṽ
′
ivi, ṽ
′
iti we continue with all the edges being compatible. However, if the edge
viti is not in D, then the point ṽi is in the triangle uiviwi, but the point ṽ′i is in a triangle
uiwipi. Then, we obtain a triangulation F of P by adding the edges ṽiui, ṽivi, ṽiwi, and
a triangulation F ′ of P ′ by adding the edges ṽ′iui, ṽ
′
ipi, ṽiwi. Now, the images of the
edges ṽivi of F , edges ṽ′ivi, are not in F ′ (there the edges ṽ
′
ipi appear instead). This
situation occurs (s − k) times, so the number of compatible edges between F and F ′ is
3n− 6− (s− k).
Conversely, suppose P and P ′ contain triangulations F and F ′ with k′ = 3n − 6 −
(s − k) compatible edges. If ṽiti is not in F , then the edges ṽivi and uiwi must be both
in F , because the edge uiwi can be crossed only by the edges tivi and tiṽi. However, in
set P ′, always the edge ṽ′ivi is crossed by the edge uiwi. Then, for each index i such that
ṽiti is not in F , one of the edges ṽivi or uiwi of F is not in F ′. Therefore, this situation
can happen at most (s− k) times, that is, the triangulation F must contain at least k edges
ṽiti. But if k segments ṽiti are disjoint, also their corresponding viti edges are disjoint.
Therefore, S has to contain at least k disjoint segments.
Finally, let us analyze the complexity of augmenting a plane subgraph F of Dn until
obtaining a maximal plane subgraph. Since F has O(n) edges, the set of edges of S(v) not
crossing F can be trivially found in O(n2) time. This directly implies an O(n3) algorithm
to obtain a maximal plane graph containing F : For i = 1, . . . , n, update F by adding
the edges of S(vi) non-crossing F , not in F . The following result implies that, if F is
connected, finding a maximal plane subgraph containing F can be done in O(n2) time.
Theorem 4.5. Given a simple topological drawing of Kn, a connected plane subgraph F ,
and a vertex v, we can find the edges from v to F not crossing F in O(n) time.
Proof. Notice that as F is a plane graph, we can compute in linear time, for each vertex w
the clockwise order of the edges of F incident to w, the faces of F , and for each face f ,
the clockwise cyclic list of edges and vertices found along its boundary.
Suppose first that the vertex v is not in F , and let vw1 be the first edge in the rotation of
v with one endpoint in F . The algorithm runs in three stages. In the first stage, it starts by
finding the edge of F , edge e1 = u0u1, that intersects vw1 closest to v along vw1. When
the first intersection point occurs precisely at the vertex w1, we take e1 as the first edge
of F that follows, counterclockwise, to w1v in S(w1). Using the rotation system and its
inverse, this edge e1 of F can be found in linear time, since |F | ∈ O(n). It also gives us
the face f of F containing the vertex v inside.
For simplicity, let us suppose that f is a bounded face and that the boundary of f is a
simple cycle, formed by the edges e1 = u0u1, e2 = u1u2, em = um−1u0. We will later
discuss the general case. Notice that if the edges vwi, vwj , vwk are in this clockwise order
in S(v), their corresponding first crossing points xi, xj , xk with F are found in a clockwise
walk of the boundary of f in that same clockwise order. See the right bottom drawing of
Figure 9.
In the second stage, the algorithm simulates a clockwise walk x1u1, u1u2, . . . ,uk−1uk ,
. . . of the boundary of f starting at point x1, the first crossing point of vw1 with e1 = u0u1,
and simultaneously a clockwise walk vw1, vw2, . . . , vwi, . . . on the edges of the star S(v),
beginning with the edge vw1. In each step, the algorithm makes progress in at least one
of the two walks, by adding the following edge on the boundary to the boundary walk or
passing to explore the following edge of S(v). In this process the algorithm will keep a list
σ with some of the explored edges of S(v).
84 Ars Math. Contemp. 20 (2021) 69–87
In a generic step, the edges Si = (vw1, vw2, . . . , vwi) of S(v), and the portion of the
boundary of f , Wk = (x1u1, u1u2, . . . , uk−1uk), have been visited, and the two following
invariants hold:
(A) The first crossing of the edge vwi is not on Wk−1 = (x1u1, u1u2, . . . , uk−2uk−1)
(the walk Wk minus its last edge).
(B) The list σ contains an ordered list (vui1 , vui2 , . . . , vuis) of the explored edges of
S(v) finishing at some of the vertices uj , 1 ≤ j < k, satisfying:
(B1) All the explored edges of S(v) not placed in σ cross the boundary of f .
(B2) The first crossing point of each edge vuj of σ with the boundary of f is either
uj or is placed clockwise after uj .
Initially, if x1 is an interior point of the edge e1 = u0u1, then Wk = (x1u1), Si =
(vw1, vw2) and the list σ is empty. If x1 coincides with the vertex u0, then Wk = (u0u1),
Si = (vw1, vw2) and the list contains the edge vu0. In both cases invariants (A) and (B)
are satisfied (the walk Wk−1 is empty or consists of only one vertex).
f
v
f
v1
2
3
4
5
6 7
8
9
10
f
v
1
2
3
4
5
6
7
8
9
10
v
f
Figure 9: Top left: A vertex v inside the face f . Only the edges vui, with ui incident to the
face f , can be uncrossed by F . Top right: A clockwise walk along the boundary of the face
f . Bottom left: In a walk along the boundary of f , the first crossing points of the edges
of S(v) are found in the same order as the edges of S(v). Bottom right: An equivalent
drawing to the top left figure with the boundary of f being a simple cycle. Some vertices,
like (2, 4, 9), can correspond to the same vertex of the first drawing.
In this second stage the algorithm proceeds as follows:
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 85
• If vwi crosses the last edge of Wk, edge ek, or if wi is not a vertex of f , iterate
considering the clockwise successor vwi+1 of vwi in the rotation of v.
As the first crossing of vwi must be on the edge ek or a posterior edge et, t > k, also
the first crossing of vwi+1 must be on ek or a posterior edge. Thus invariant (A) is
kept. On the other hand, observe that σ does not change, vwi must not be included
in σ (it crosses f ), and Wk is not modified. Therefore invariant (B) is also kept.
• If vwi does not cross ek and wi is a vertex of f , wi ̸= uk, then, add the following
edge ek+1 on f to Wk, keeping the same edge vwi of S(v).
Invariant (A) is kept, because the first crossing point of vwi cannot be on Wk. In-
variant (B) is also kept, because σ is not modified.
• If vwi does not cross ek and wi = uk, then, add vwi to the list σ, pass to explore the
following edge vwi+1 of S(v) and add the following edge ek+1 on f to Wk.
Again, invariant (A) is kept, because the first crossing of vwi+1 must be after uk.
On the other hand, the first crossing point of vwi is either uk or it is placed after uk,
hence property (B) is kept.
This second stage of the algorithm ends when all the edges of S(v) and f have been
explored. The last edge of the boundary of f being either u0x1 or um−1u0. Therefore, at
the end, invariant (B) implies that σ will contain the uncrossed edges of S(v) plus some
crossed edges vui of S(v) satisfying that the first crossing (on the boundary of f ) is placed
after the endpoint ui of that edge.
In each step of this stage, a new edge in the boundary of f , a new edge of S(v), or both
edges become explored. As the number of edges in f and in S(v) is linear, this second
stage of the algorithm runs in O(n) time.
In the third stage, the algorithm repeats counterclockwise the above stage considering
only the edges in σ. That means, it explores counterclockwise the boundary of f (in the
order x1u0, u0um−1, . . . , and counterclockwise the edges of S(v) placed in σ (so, in the
order vuis , vuis−1 , . . . ). In this third stage, in linear time, a new list σ is obtained. By
invariant (B1), all the uncrossed edges of S(v) have to be in σ. And by invariant (B2), if
vui is in σ, its first crossing point cannot be clockwise nor counterclockwise before ui, so
it has to be ui. Therefore, σ will contain the uncrossed edges of S(v).
In general, the boundary of face f is not a simple cycle, some edges of f can be incident
to f for both sides, so they appear twice in a walk along the boundary of f . However, this
general case can be transformed to the previous case by standard techniques, as done in [6]
in their proof of the general case of Lemma 1.1. In Figure 9, the bottom right figure shows
how to transform the drawing of the top left figure, to obtain an equivalent drawing where
the boundary of f is a simple cycle. When the face f is the unbounded face the algorithm
is totally analogous.
Finally, let us consider the case when the vertex v is in F . Then, vertex v can be
incident to several faces f1, . . . , fl, l ≥ 1. Again, for simplicity, suppose that the boundary
of each one of these faces is a simple cycle. For each face fi, if vwi1 , vwi2 are the two
edges incident to vertex v in fi, we can compute by the above method the uncrossed edges
of S(v) placed inside fi, using only the edges of S(v) placed clockwise between vwi1
and vwi2 .
86 Ars Math. Contemp. 20 (2021) 69–87
5 Conclusion
In this paper, we considered maximal and maximum plane subgraphs of simple topological
drawings of Kn. It turns out that maximal plane subgraphs have interesting structural prop-
erties. These insights could be useful in improving the bounds on the number of disjoint
edges in any such drawing, continuing this long line of research.
Also, algorithmic questions arise. For example, Proposition 2.1 ensures that there are
always two edges connecting a vertex v to a not necessarily connected plane graph F in Dn
without crossings. Moreover, the set of edges of S(v) not crossing F can be trivially found
in O(n2) time. This leads to the following question.
Problem 5.1. Given a not necessarily connected plane graph F in Dn, plus a vertex v not
in F , can the edges of S(v) incident to but not crossing F be found in o(n2) time?
ORCID iDs
Alfredo Garcı́a Olaverri https://orcid.org/0000-0002-6519-1472
Alexander Pilz https://orcid.org/0000-0002-6059-1821
Javier Tejel Altarriba https://orcid.org/0000-0002-9543-7170
References
[1] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, D. McQuillan, B. Mohar, P. Mutzel,
P. Ramos, R. B. Richter and B. Vogtenhuber, Bishellable drawings of Kn, SIAM J. Discrete
Math. 32 (2015), 2482–2492, doi:10.1137/17m1147974.
[2] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, J. Pammer, A. Pilz, P. Ramos, G. Salazar
and B. Vogtenhuber, All good drawings of small complete graphs, in: Proceedings of the 31st
European Workshop on Computational Geometry (EuroCG 2015), 2015 pp. 57–60.
[3] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos and G. Salazar, Shellable
drawings and the cylindrical crossing number of Kn, Discrete Comput. Geom. 52 (2015), 743–
753, doi:10.1007/s00454-014-9635-0.
[4] M. Balko, R. Fulek and J. Kynčl, Crossing numbers and combinatorial characterization
of monotone drawings of Kn, Discrete Comput. Geom. 53 (2015), 107–143, doi:10.1007/
s00454-014-9644-z.
[5] J. Fox and B. Sudakov, Density theorems for bipartite graphs and related Ramsey-type results,
Combinatorica 29 (2009), 153–196, doi:10.1007/s00493-009-2475-5.
[6] R. Fulek and A. J. Ruiz-Vargas, Topological graphs: empty triangles and disjoint matchings,
in: Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry (SoCG
’13), Association for Computing Machinery, New York, NY, USA, 2013 pp. 259–266, doi:
10.1145/2462356.2462394.
[7] E. Gioan, Complete graph drawings up to triangle mutations, in: D. Kratsch (ed.), Graph-
Theoretic Concepts in Computer Science, Springer, Berlin, volume 3787 of Lecture Notes in
Computer Science, pp. 139–150, 2005, doi:10.1007/11604686 13.
[8] H. Harborth and I. Mengersen, Edges without crossings in drawings of complete graphs, J.
Comb. Theory Ser. B 17 (1974), 299–311, doi:10.1016/0095-8956(74)90035-5.
[9] G. T. Klincsek, Minimal triangulations of polygonal domains, Ann. Discrete Math. 9 (1980),
121–123, doi:10.1016/s0167-5060(08)70044-x.
A. Garcı́a Olaverri et al.: On plane subgraphs of complete topological drawings 87
[10] J. Kratochvı́l and J. Nešetřil, INDEPENDENT SET and CLIQUE problems in intersection-
defined classes of graphs, Comment. Math. Univ. Carolinae 31 (1990), 85–93, http://dml.
cz/dmlcz/106821.
[11] J. Kynčl, Simple realizability of complete abstract topological graphs in P, Discrete Comput.
Geom. 45 (2011), 383–399, doi:10.1007/s00454-010-9320-x.
[12] J. Kynčl, Enumeration of simple complete topological graphs, Euopean. J. Comb. 30 (2009),
1676–1685, doi:10.1016/j.ejc.2009.03.005.
[13] J. Kynčl, Improved enumeration of simple topological graphs, Discrete Comput. Geom. 50
(2013), 727–770, doi:10.1007/s00454-013-9535-8.
[14] J. Pach, J. Solymosi and G. Tóth, Unavoidable configurations in complete topological graphs,
Discrete Comput. Geom. 30 (2003), 311–320, doi:10.1007/s00454-003-0012-9.
[15] J. Pach and G. Tóth, Which crossing number is it anyway?, J. Comb. Theory Ser. B 80 (2000),
225–246, doi:10.1006/jctb.2000.1978.
[16] J. Pach and G. Tóth, Disjoint edges in topological graphs, in: J. Akiyama, E. T. Baskoro and
M. Kano (eds.), Combinatorial Geometry and Graph Theory, Springer, Berlin, volume 3330 of
Lecture Notes in Computer Science, pp. 133–140, 2005, doi:10.1007/978-3-540-30540-8 15.
[17] J. Pammer, Rotation Systems and Good Drawings, Master’s thesis, Graz University of Tech-
nology, 2014.
[18] N. H. Rafla, The Good Drawings Dn of the Complete Graph Kn, Ph.D. thesis, McGill Univer-
sity, Montreal, 1988.
[19] G. Ringel, Extremal problems in the theory of graphs, in: M. Fiedler (ed.), Theory of Graphs
and Its Applications, Publishing House of the Czechoslovak Academy of Sciences, Prague,
1964 pp. 85–90, proceedings of the Symposium held in Smolenice in June 1963.
[20] A. J. Ruiz-Vargas, Many disjoint edges in topological graphs, Comput. Geom. 62 (2017), 1–13,
doi:10.1016/j.comgeo.2016.11.003.
[21] A. Saalfeld, Joint triangulations and triangulation maps, in: Proceedings of the Third Annual
Symposium on Computational Geometry (SCG ’87), Association for Computing Machinery,
New York, NY, USA, 1987 pp. 195–204, doi:10.1145/41958.41979.
[22] M. Schaefer, The graph crossing number and its variants: A survey, Electron. J. Comb. (2021),
#DS21, doi:10.37236/2713.
[23] A. Suk, Disjoint edges in complete topological graphs, Discrete Comput. Geom. 49 (2013),
280–286, doi:10.1007/s00454-012-9481-x.