is not a sphere. Our aim is to show that the first homology group of $C$
cannot be trivial.

We will rely on the fact that the first homology group of
$X=\operatorname{\mathbb{S}}^{3}\setminus\operatorname{\mathbb{S}}^{1}$ is not
trivial. It suffices to show that the homology group of $X$ is a quotient of
the homology group of $C$. Since here by Hurewicz’s theorem, the homology
group is the abelisation of the fundamental group, it suffices to show that
the fundamental group $\pi_{1}(X)$ of $X$ is a quotient of the fundamental
group $\pi_{1}(C)$.

We let $C_{1}$ be a small open neighbourhood of $C$ in the embedding of $C$ in
$\operatorname{\mathbb{S}}^{3}$. Since $C_{1}$ has a deformation retract onto
$C$, it has the same fundamental group. We obtain $C_{2}$ from $C_{1}$ by
attaching the interiors of all local surfaces of the embedding except for one
– which is not a sphere. This can be done by attaching finitely many 3-balls.
Similar as in the proof of Section 2.5, one can use Van Kampen’s theorem to
show that the fundamental group of $C_{2}$ is a quotient of the fundamental
group of $C_{1}$. By adding finitely many spheres if necessary and arguing as
above one may assume that remaining local surface is a torus. Hence $C_{2}$
has the same fundamental group as $X$. This completes the sketch.

###  2.8 Embedding general simplicial complexes

There are three classes of simplicial complexes that naturally include the
simply connected simplicial complexes: the $p$-nullhomologous ones that are
included in those with abelian fundamental group that in turn are included in
general simplicial complexes. Theorem 2.2.2 characterises embeddability of
$p$-nullhomologous complexes. In this section we prove embedding results for
the later two classes. The bigger the class gets, the stronger assumptions we
will require in order to guarantee topological embeddings into
$\operatorname{\mathbb{S}}^{3}$.

A _curve system_ of a surface $S$ of genus $g$ is a choice of at most $g$
genus reducing curves in $S$ that are disjoint. An _extension_ of a rotation
system $\Sigma$ is a choice of curve system at every local surface of
$\Sigma$. An extension of a rotation system of a complex $C$ is _simply
connected_ if the topological space obtained from $C$ by gluing131313We stress
that the curves need not go through edges of $C$. ‘Gluing’ here is on the
level of topological spaces not of complexes. a disc at each curve of the
extension is simply connected. The definition of a _$p$ -nullhomologous
extension_ is the same with ‘$p$-nullhomologous’ in place of ‘simply
connected’.

######  Theorem 2.8.1.

Let $C$ be a connected and locally connected simplicial complex with a
rotation system $\Sigma$. The following are equivalent.

  1. 1.

$\Sigma$ is induced by a topological embedding of $C$ into
$\operatorname{\mathbb{S}}^{3}$.

  2. 2.

$\Sigma$ is a planar rotation system that has a simply connected extension.

  3. 3.

We can subdivide edges of $C$, do baricentric subdivision of faces and add new
faces such that the resulting simplicial complex is simply connected and has a
topological embedding into $\operatorname{\mathbb{S}}^{3}$ whose induced
planar rotation system $\Sigma^{\prime}$ ‘induces’ $\Sigma$.

Here we define that ‘$\Sigma^{\prime}$ induces $\Sigma$’ in the obvious way as
follows. Let $C$ be a simplicial complex obtained from a simplicial complex
$C^{\prime}$ by deleting faces. A rotation system $\Sigma=(\sigma(e)|e\in
E(C))$ of $C$ is _induced_ by a rotation system
$\Sigma^{\prime}=(\sigma^{\prime}(e)|e\in E(C))$ of $C^{\prime}$ if
$\sigma(e)$ is the restriction of $\sigma^{\prime}(e)$ to the faces incident
with $e$. If $C$ is obtained from contracting edges of $C^{\prime}$ instead, a
rotation system $\Sigma$ of $C$ is _induced_ by a rotation system
$\Sigma^{\prime}$ of $C^{\prime}$ if $\Sigma$ is the restriction of
$\Sigma^{\prime}$ to those edges that are in $C$. If $C^{\prime}$ is obtained
from $C$ by a baricentric subdivision of a face $f$ we take the same
definition of ‘induced’, where we make the identification between the face $f$
of $C$ and all faces of $C^{\prime}$ obtained by subdividing $f$. Now in the
situation of Theorem 2.8.1, we say that $\Sigma^{\prime}$ _induces_ $\Sigma$
if there is a chain of planar rotation systems each inducing the next one
starting with $\Sigma^{\prime}$ and ending with $\Sigma$.

Before we can prove Theorem 2.8.1, we need some preparation. The following is
a consequence of the Loop Theorem [29, 17].

######  Lemma .

Let $X$ be an orientable surface of genus $g\geq 1$ embedded topologically
into ${\mathbb{R}}^{3}$, then there is a genus reducing circle141414A _circle_
is a topological space homeomorphic to $\mathbb{S}^{1}$.  $\gamma$ of $X$ and
a disc $D$ with boundary $\gamma$ and all interior points of $D$ are contained
in the interior of $X$.

######  Corollary .

Let $X$ be an orientable surface of genus $g\geq 1$ embedded topologically
into ${\mathbb{R}}^{3}$, then there are genus reducing circles $\gamma_{1}$,…,
$\gamma_{g}$ of $X$ and closed discs $D_{i}$ with boundary $\gamma_{i}$ such
that the $D_{i}$ are disjoint and the interior points of the discs $D_{i}$ are
contained in the interior of $X$.

###### Proof.

We prove this by induction on $g$. In the induction step we cut of the current
surface along $D$. Then we the apply Section 2.8 to that new surface. ∎

###### Proof of Theorem 2.8.1..

1 is immediately implied by 3.

Next assume that $\Sigma$ is induced by a topological embedding of $C$ into
$\operatorname{\mathbb{S}}^{3}$. Then $\Sigma$ is clearly a planar rotation
system. It has a simply connected extension by Section 2.8. Hence 1 implies 2.

Next assume that $\Sigma$ is a planar rotation system that has a simply
connected extension. We can clearly subdivide edges and do baricentric
subdivision and change the curves of the curve system of the simply connected
extension such that in the resulting simplicial complex $C^{\prime}$ all the
curves of the simply connected extension closed are walks in the 1-skeleton of
$C^{\prime}$. We define a planar rotation system $\Sigma^{\prime}$ of
$C^{\prime}$ that induces $\Sigma$ as follows. If we subdivide an edge, we
assign to both copies the cyclic orientation of the original edge. If we do a
baricentric subdivision, we assign to all new edges the unique cyclic
orientation of size two. Iterating this during the construction of
$C^{\prime}$ defines $\Sigma^{\prime}=(\sigma^{\prime}(e)|e\in E(C))$, which
clearly is a planar rotation system that induces $\Sigma$. By construction
$\Sigma^{\prime}$ has a simply connected extension such that all its curves
are walks in the 1-skeleton of $C^{\prime}$ .

Informally, we obtain $C^{\prime\prime}$ from $C^{\prime}$ by attaching a disc
at the boundary of each curve of the simply connected extension. Formally, we
obtain $C^{\prime\prime}$ from $C^{\prime}$ by first adding a face for each
curve $\gamma$ in the simply connected extension whose boundary is the closed
walk $\gamma$. Then we do a baricentric subdivision to all these newly added
faces. This ensures that $C^{\prime\prime}$ is a simplicial complex. Since $C$
is locally connected, also $C^{\prime\prime}$ is locally connected. Since the
geometric realisation of $C^{\prime\prime}$ is equal to the geometric
realisation of $C$, which is simply connected, the simplicial complex
$C^{\prime\prime}$ is simply connected.

Each newly added face $f$ corresponds to a traversal of a curve $\gamma$ of
some edge $e$ of $C^{\prime}$. This traversal is a unique edge of the local
surface $S$ to whose curve system $\gamma$ belongs. For later reference we
denote that copy of $e$ in $S$ by $e_{f}$.

We define a rotation system
$\Sigma^{\prime\prime}=(\sigma^{\prime\prime}(e)|e\in E(C))$ of
$C^{\prime\prime}$ as follows. All edges of $C^{\prime\prime}$ that are not
edges of $C^{\prime}$ are incident with precisely two faces. We take the
unique cyclic ordering of size two there.

Next we define $\sigma^{\prime\prime}(e)$ at edges $e$ of $C^{\prime}$ that
are incident with newly added faces. If $e$ is only incident with a single
face of $C^{\prime}$, then $e$ is only in a single local surface and it only
has one copy in that local surface. Since the curves at that local surface are
disjoint. We could have only added a single face incident with $e$. We take
for $\sigma^{\prime\prime}(e)$ the unique cyclic orientation of size two at
$e$.

So from now assume that $e$ is incident with at least two faces of
$C^{\prime}$. In order to define $\sigma^{\prime\prime}(e)$, we start with
$\sigma^{\prime}(e)$ and define in the following for each newly added face in
between which two cyclic orientations of faces adjacent in
$\sigma^{\prime}(e)$ we put it. We shall ensure that between any two
orientations we put at most one new face. Recall that two cyclic orientations
$\vec{f_{1}}$ and $\vec{f_{2}}$ of faces $f_{1}$ and $f_{2}$, respectively,
are adjacent in $\sigma^{\prime}(e)$ if and only if there is a clone
$e^{\prime}$ of $e$ in a local surface $S$ for $(C^{\prime},\Sigma^{\prime})$
containing $\vec{f_{1}}$ and $\vec{f_{2}}$ such that $e^{\prime}$ is incident
with $\vec{f_{1}}$ and $\vec{f_{2}}$ in $S$. Let $f$ be a face newly added to
$C^{\prime\prime}$ at $e$. Let $\gamma_{f}$ be the curve from which $f$ is
build and let $S_{f}$ be the local surface that has $\gamma_{f}$ in its curve
system. Let $e_{f}$ be the copy of $e$ in $S_{f}$ that corresponds to $f$ as
defined above. when we consider $f$ has a face obtained from the disc glued at
$\gamma_{f}$. We add $f$ to $\sigma^{\prime}(e)$ in between the two cyclic
orientations that are incident with $e_{f}$ in $S_{f}$. This completes the
definition of $\Sigma^{\prime\prime}$. Since the copies $e_{f}$ are distinct
for different faces $f$, the rotation system $\Sigma^{\prime\prime}$ is well-
defined. By construction $\Sigma^{\prime\prime}$ induces $\Sigma$. We prove
the following.

######  Claim .

$\Sigma^{\prime\prime}$ is a planar rotation system of $C^{\prime\prime}$.

Proof of Claim. Let $v$ be a vertex of $C^{\prime\prime}$. If $v$ is not a
vertex of $C^{\prime}$, then the link graph at $v$ is a cycle. Hence the link
complex at $v$ is clearly a sphere. Hence we may assume that $v$ is a vertex
of $C^{\prime}$.

Our strategy to show that the link complex $S^{\prime\prime}$ at $v$ for
$(C^{\prime\prime},\Sigma^{\prime\prime})$ is a sphere will be to show that it
is obtained from the link complex $S^{\prime}$ for
$(C^{\prime},\Sigma^{\prime})$ by adding edges in such a way that each newly
added edge traverses a face of $S^{\prime}$ and two newly added edges traverse
different face of $S^{\prime}$.

So let $f$ be a newly added face incident with $v$ of $C^{\prime}$. Let $x$
and $y$ be the two edges of $f$ incident with $v$. We make use of the
notations $\gamma_{f}$, $S_{f}$, $x_{f}$ and $y_{f}$ defined above. Let
$v_{f}$ be the unique vertex of $S_{f}$ traversed by $\gamma_{f}$ in between
$x_{f}$ and $y_{f}$. By Section 2.4 there is a unique face $z_{f}$ of
$S^{\prime}$ mapped by the map $\iota$ of that lemma to $v_{f}$. And $x$ and
$y$ are vertices in the boundary of $z_{f}$. The edges on the boundary of
$z_{f}$ incident with $x$ and $y$ are the cyclic orientations of the faces
that are incident with $x_{f}$ and $y_{f}$ in $S_{f}$. Hence in
$S^{\prime\prime}$ the edge $f$ traverses the face $z_{f}$.

It remains to show that the faces $z_{f}$ of $S^{\prime}$ are distinct for
different newly added faces $f$ of $C^{\prime\prime}$. For that it suffices by
Section 2.4 to show that the vertices $v_{f}$ are distinct. This is true as
curves for $S_{f}$ traverse a vertex of $S_{f}$ at most once and different
curves for $S_{f}$ are disjoint. ! $\diamondsuit$

Since $\Sigma^{\prime\prime}$ is a planar rotation system of the locally
connected simplicial complex $C^{\prime\prime}$ and $C^{\prime\prime}$ is
simply connected, $\Sigma^{\prime\prime}$ is induced by a topological
embedding of $C^{\prime\prime}$ into $\operatorname{\mathbb{S}}^{3}$ by
Theorem 2.5.1. Hence 2 implies 3. ∎

A natural weakening of the property that $C$ is simply connected is that the
fundamental group of $C$ is abelian. Note that this is equivalent to the
condition that every chain that is $p$-nullhomologous is simply connected.

######  Theorem 2.8.2.

Let $C$ be a connected and locally connected simplicial complex with abelian
fundamental group. Then $C$ has a topological embedding into
$\operatorname{\mathbb{S}}^{3}$ if and only if it has a planar rotation system
$\Sigma$ that has a $p$-nullhomologous extension.

In order to prove Theorem 2.8.2, we prove the following.

######  Lemma .

A $p$-nullhomologous extension of a planar rotation system of a simplicial
complex $C$ with abelian fundamental group is a simply connected extension.

###### Proof.

Let $C^{\prime}$ be the topological space obtained from $C$ by gluing discs
along the curves of the $p$-nullhomologous extension. The fundamental group
$\pi^{\prime}$ of $C^{\prime}$ is a quotient of the fundamental group $\pi$ of
$C$, see for example [18, Proposition 1.26]. Since $\pi$ is abelian by
assumption, also $\pi^{\prime}$ is abelian. That is, it is equal to its
abelisation, which is trivial by assumption. Hence $C^{\prime}$ is simply
connected. ∎

###### Proof of Theorem 2.8.2..

If $C$ has a topological embedding into $\operatorname{\mathbb{S}}^{3}$, then
by Theorem 2.8.1 it has a planar rotation system that has a $p$-nullhomologous
extension. If $C$ has a planar rotation system that has a $p$-nullhomologous
extension, then that extension is simply connected by Section 2.8. Hence $C$
has a topological embedding into $\operatorname{\mathbb{S}}^{3}$ by the other
implication of Theorem 2.8.1. ∎

###  2.9 Non-orientable 3-manifolds

By Section 2.5 and Section 2.5 a 2-complex $C$ is embeddable in an orientable
3-manifold if and only if it has a planar rotation system. Here we discuss a
notion similar to planar rotation systems that can be used to characterise
embeddability in 3-manifolds combinatorially.

Recall that a rotation framework of a 2-complex $C$ is a choice of embedding
of all its link graphs in the plane so that for each edge $e$ of $C$ in the
two link graphs at the endvertices of the edge $e$, the rotators at the vertex
$e$ are reverse or agree. We colour an edge _red_ if they agree. A
_generalised planar rotation system_ is a rotation framework with the further
condition that for every face $f$ of $C$ its number of red incident edges is
even.

######  Remark .

Any planar rotation system defines a generalised planar rotation system. In
this induced generalised planar rotation system no edge is red.

######  Remark .

Let $C$ be simplicial complex whose first homology group over the binary field
${\mathbb{F}}_{2}$ is trivial, for example this includes the case where $C$ is
simply connected. Then $C$ has a planar rotation system if and only if it has
a generalised planar rotation system by Section 1.2.

######  Remark .

A locally 3-connected 2-complex has a generalised planar rotation system if
and only if every choice of embeddings of its link graphs in the plane is a
generalised planar rotation system. Indeed, any face shares an even number of
edges with every vertex. By local 3-connectedness, the embeddings of a link
graph at some vertex $v$ is unique up to orientation, which reverses all
rotators at edges incident with $v$. So it flips red edges to non-red ones and
vice versa. Hence the number of red edges modulo two does not change.

Thus there is a trivial algorithm that verifies whether a locally 3-connected
2-complex has a generalised planar rotation system: embed the link graphs in
the plane arbitrarily (if possible) and then check the condition at every edge
and face.

The following was proved by Skopenkov.

######  Theorem 2.9.1 ([36]).

The following are equivalent for a 2-complex $C$.

  * •

$C$ has a generalised planar rotation system;

  * •

$C$ has a thickening that is a 3-manifold;

  * •

$C$ has a piece-wise linear embedding in some (not necessarily compact)
3-manifold.

######  Remark .

For 2-dimensional manifolds there are two types of rotation systems: one for
the orientable case and one for the general case. In dimension three the
situation is analoguous. For orientable 3-manifolds we have ‘planar rotation
systems’ and ‘generalised planar rotation systems’ for general 3-manifolds.

######  Remark .

Similarly as for planar rotation systems, the methods of this series of papers
can also be used to also give a polynomial time algorithm that verifies the
existence of generalised planar rotation systems. As mentioned in Section 2.9
the locally 3-connected case has a polynomial algorithm and the reduction to
the locally 3-connected case works the same as for planar rotation systems.

######  Remark .

In Section 1.5 we explain how in an earlier version of this paper we
characterise the existence of a planar rotation system, and thus embeddability
in an orientable 3-manifold, in terms of excluded minors. Similarly, one can
characterise the existence of a generalised planar rotation system (and thus
embeddability in a 3-manifold) in terms of excluded minors, see [7] for
details.

##  Chapter 3 A refined Kuratowski-type characterisation

###  3.1 Abstract

Building on earlier chapters, we prove an analogue of Kuratowski’s
characterisation of graph planarity for three dimensions.

More precisely, a simply connected 2-dimensional simplicial complex embeds in
3-space if and only if it has no obstruction from an explicit list. This list
of obstructions is finite except for one infinite family.

###  3.2 Introduction

We assume that the reader is familiar with chapter 1. In that chapter we prove
that a locally 3-connected simply connected 2-dimensional simplicial complex
has a topological embedding into 3-space if and only if it has no space minor
from a finite explicit list ${{\cal Z}}$ of obstructions (based on a
topological theorem proved in chapter 2). The purpose of this chapter is to
extend that theorem beyond locally 3-connected (2-dimensional) simplicial
complexes to simply connected simplicial complexes in general.

The first question one might ask in this direction is whether the assumption
of local 3-connectedness could simply be dropped from the result of chapter 1.
Unfortunately this is not true. One new obstruction can be constructed from
the Möbius-strip as follows.

######  Example .

One can obtain the Möbius-strip from an untwisted strip as follows. Take one
of the boundary components. This is homeomorphic to
$\operatorname{\mathbb{S}}^{1}$ and now identify antipodal points. Similarly,
one can start with an untwisted strip and now on one boundary component
identify every point with its rotation by $120$ degrees. Now identify these
two spaces at their central cycles; that is the images of the boundary
component where the gluing took place (via some homeomorphism of
$\operatorname{\mathbb{S}}^{1}$).

In a few lines we explain why this topological space $X$ cannot be embedded in
3-space. Any triangulation of $X$ gives an obstruction to embeddability. It
can be shown that such triangulations have no space minor in the finite list
${{\cal Z}}$.

Why can $X$ not be embedded in 3-space? To answer this, consider a small torus
around the central cycle. The two glued spaces each intersect that torus in a
circle. These circles however have a different homotopy class in the torus.
Since any two circles in the torus of a different homotopy class intersect111A
simple way to see this is to note that the torus with a circle removed is an
annulus. , the space $X$ cannot be embedded in 3-space without intersections
of the two glued spaces. Obstructions of this type we call _torus crossing
obstructions_. A precise definition is given in Section 3.3.

A refined question might now be whether the result of chapter 1 extends to
simply connected simplicial complex if we add the list ${{\cal T}}$ of torus
crossing obstructions to the list ${{\cal Z}}$ of obstructions. The answer to
this question is ‘almost yes’. Indeed, we just need to add to the space minor
operation the operations of stretching defined in Section 3.6 and add a finite
set to ${{\cal Z}}$; we refer to this larger finite set as ${{\cal Y}}$.

The stretching operations are illustrated in Figure 3.3, Figure 3.7 and Figure
3.9. It is not hard to show that stretching preserves embeddability. The main
result of this chapter is the following.

######  Theorem 3.2.1.

Let $C$ be a 2-dimensional simplicial complex such that the first homology
group $H_{1}(C,{\mathbb{F}}_{p})$ is trivial for some prime $p$. The following
are equivalent.

  * •

$C$ has a topological embedding in 3-space;

  * •

$C$ is simply connected and has no stretching that has a space minor in
${{\cal Y}}\cup{{\cal T}}$.

We deduce Theorem 3.2.1 from the results of chapter 1 in two steps as follows.
The notion of ‘local almost 3-connectedness and stretched out’ is slightly
more general and more technical than ‘local 3-connectedness’, see Section 3.3
for a definition. First we extend the results of chapter 1 to locally almost
3-connected and stretched out simply connected simplicial complexes, see
Theorem 3.3.1 below. We conclude the proof by showing that any simplicial
complex can be stretched to a locally almost 3-connected and stretched out
one. More precisely:

######  Theorem 3.2.2.

For any simplicial complex $C$, there is a simplicial complex $C^{\prime}$
obtained from $C$ by stretching so that $C^{\prime}$ is locally almost
3-connected and stretched out or $C^{\prime}$ has a non-planar link.

Moreover $C$ has a planar rotation system if and only if $C^{\prime}$ has a
planar rotation system.

The overall structure of the argument is similar to that for problems in
structural graph theory with ‘3-connected kernel’ (in such arguments one first
proves the 3-connected case, then in a second step deduces the 2-connected
case and then finally deduces the general case). In Section 3.3 we prove the
extension of the results of chapter 1 to locally almost 3-connected and
stretched out simplicial complexes, Theorem 3.3.1. In Section 3.4 we develop
the tools to extend this to the locally almost 2-connected case. In Section
3.5 and Section 3.6 we extend Theorem 3.3.1 to general simplicial complexes,
which proves Theorem 3.2.2. Then we prove Theorem 3.2.1. Finally in Section
3.7 we describe algorithmic consequences.

For graph theoretic definitions we refer the reader to [11].

###  3.3 A Kuratowski theorem for locally almost 3-connected simply connected
simplicial complexes

This section is subdivided into five subsections. In the first two we
introduce the context for Theorem 3.3.1, and in the next three subsections we
prove it.

####  3.3.1 Torus crossing obstructions

In this section we prove Theorem 3.3.1, which is used in the proof of the main
theorem. First we define the list ${{\cal T}}$ of torus crossing obstructions.

Given a simplicial complex $C$, a _mega face_ $F=(f_{i}|i\in{\mathbb{Z}}_{n})$
is a cyclic orientation of faces $f_{i}$ of $C$ together with for every
$i\in{\mathbb{Z}}_{n}$ an edge $e_{i}$ of $C$ that is only incident with
$f_{i}$ and $f_{i+1}$ such that the $e_{i}$ and $f_{i}$ are locally distinct,
that is, $e_{i}\neq e_{i+1}$ and $f_{i}\neq f_{i+1}$ for all
$i\in{\mathbb{Z}}_{n}$. We remark that since in a simplicial complex any two
faces can share at most one edge, the edges $e_{i}$ are implicitly given by
the faces $f_{i}$. A _boundary component_ of a mega face $F$ is a connected
component of the 1-skeleton of $C$ restricted to the faces $f_{i}$ after we
topologically delete the edges $e_{i}$. Given a cycle $o$ that is a boundary
component of a mega face $F$, we say that $F$ is _locally monotone_ at $o$ if
for every edge $e$ of $o$ and each face $f_{i}$ containing $e$, the next face
of $F$ after $f_{i}$ that contains an edge of $o$ contains the unique edge of
$o$ that has an endvertex in common with $e$ and $e_{i+1}$. Under these
assumptions for each edge $e$ of $o$ the number of indices $i$ such that $e$
is incident with $f_{i}$ is the same. This number is called the _winding
number_ of $F$ at $o$.

A _torus crossing obstruction_ is a simplicial complex $C$ with a cycle $o$
(called the _base cycle_) whose faces can be partitioned into two mega faces
that both have $o$ has a boundary component and are locally monotone at $o$
but with different winding numbers. We denote the set of torus crossing
obstructions by ${{\cal T}}$.

######  Remark .

The set of torus crossing obstructions is infinite. Indeed, it contains at
least one member for every pair of distinct winding numbers. So it is not
possible to reduce it to a finite set. However one can further reduce torus
crossing obstruction as follows. First, by working with the class of 3-bounded
2-complexes as defined in chapter 1 instead of simplicial complexes, one may
assume that the cycle $o$ is a loop. Secondly, one may introduce the further
operation of gluing two faces along an edge if that edge is only incident with
these two faces. This way one can glue the two mega faces into single faces.
Thirdly, one can enlarge the holes of the mega faces to make them into one big
hole (after contracting edges one may assume that this single hole is bounded
by a loop). After all these steps we only have one torus crossing obstruction
left for any pair of distinct winding numbers. This obstruction consists of
three vertex-disjoint loops and two faces, each incident with two loops. The
loop contained by both faces is the base cycle $o$. Here the faces may have
winding number greater than one. The faces have winding number precisely one
at the other loops.

A _parallel graph_ consists of two vertices, called the _branch vertices_ ,
and a set of disjoint paths between them. Put another way, start with a graph
with only two vertices and all edges going between these two vertices, now
subdivide these edges arbitrarily, see Figure 3.1. For example, parallel
graphs where the branch vertices have degree two are cycles.

Figure 3.1: A parallel graph with five paths.

A _para-cycle_ in a simplicial complex $C$ is a cycle $o$ such that all its
edges have face-degree at least three and all link graphs at vertices of $o$
are parallel graphs. A para-cycle $o$ is _planar_ if there is a choice of
embedding of the link graph at each vertex of $o$ so that for each edge $e$ of
$o$ the two rotators at $e$ in the link graphs at its endvertices are reverse
of one another.

######  Lemma .

Let $C$ be a simplicial complex with a non-planar para-cycle $o$. Then a torus
crossing obstruction can be obtained from $C$ by deleting faces.

###### Proof.

First we prove the lemma under the additional assumption that $o$ has length
at least four and is chordless. Our aim is to define a torus crossing
obstruction with base cycle $o$. For that we define a set of possible mega
faces as follows. By deleting faces of $C$ that do not have a vertex in the
cycle $o$ if necessary, assume that all faces of $C$ have an endvertex on $o$.

Let $X$ be the set of edges of $C$ that are not on $o$ but have an endvertex
on $o$. Every edge in $X$ is incident with exactly two faces. And every face
of $C$ is incident with exactly two edges of $X$ since $o$ has length at least
four and no chords. This defines a partition of the set of faces of $C$ into
mega-faces, where the two edges adjacent with a face are its two unique edges
in $X$.

Since $o$ is a para-cycle, the cycle $o$ is a boundary component of each of
these mega-faces. It is straightforward to check that these mega-faces are
locally monotone at $o$.

It suffices to show that two of these mega faces have distinct winding number
at $o$. Suppose not for a contradiction. Then all mega faces have the same
winding number (this includes the case that there is only one mega face).

We enumerate the above mega faces and let $K$ be their total number. We denote
by $W$ the common winding number; that is, for all of the $K$ mega faces each
edge of $o$ is in exactly $W$ faces of each mega face. By $f[k,w,e]$ (or
$f[k,w]$ if $e$ is implicitly given) we denote the $w$-th face incident with
$e\in o$ on the $k$-th mega face, where $k$ and $w$ are in the cyclic groups
${\mathbb{Z}}_{K}$ and ${\mathbb{Z}}_{W}$, respectively (with respect to a
fixed linear order of the faces of a mega face that is induced by its unique
cyclic ordering of its faces). We define the rotator at the edge $e$ to be
$f[1,1]$, $f[2,1]$, …, $f[K,1]$, $f[1,2]$, $f[2,2]$, …, $f[K,2]$, $f[1,3]$,
…,…, $f[K,W]$, $f[1,1]$. All other edges of $C$ have face degree at most two
and thus a unique rotator. So these choices define a rotation system of $C$.
Since all the link graphs at vertices of $o$ are parallel graphs, this defines
a plane embedding of them. So this rotation system is planar, and witnesses
that the para-cycle $o$ is planar. This is the desired contradiction to our
assumption. Hence two mega faces must have a different winding number. So $C$
contains a torus crossing obstruction. This is the desired contradiction to
our assumption. Hence two mega faces must have a different winding number. So
$C$ contains a torus crossing obstruction.

Having completed the proof under the additional assumption that $o$ has length
at least four and no chords, we now deduce the general case from that special
case. We consider the operation of subdividing an edge, which subdivides an
edge and all the resulting faces of size four into two triangular faces such
that the newly introduced vertex is incident with all newly introduced edges.
If such a subdivision has a torus crossing obstruction, then also $C$ has a
torus crossing obstruction (simply replace subdivision-faces by the primal
faces containing them). Via subdivisions we first ensure that $o$ has length
at least four and then we subdivide every chord, to obtain a chordless cycle.
Since subdivisions of parallel graphs are parallel graphs, we can apply the
special case now and deduce the general case. ∎

####  3.3.2 Statement of Theorem 3.3.1

Let $G$ be a link graph of a vertex of a 2-complex $C$ incident with a single
loop $\ell$. We say that $G$ is _helicopter planar_ if $G$ has a plane
embedding so that the rotators at the two vertices of $G$ corresponding to
$\ell$ are reverse of one another – where two edges incident with these
vertices are in bijection if they come from the same face of $C$ (this is
unambigious as $C$ has exactly one loop). A _helicopter complex_ is a
2-complex with a single loop $\ell$ such that the link graph at the unique
vertex incident with $\ell$ is not helicopter planar.

######  Observation .

A helicopter complex does not admit a planar rotation system. ∎

A helicopter complex is _nice_ if its link graph at the unique vertex incident
with its loop is a subdivision of a 3-connected graph.

######  Lemma .

There is a finite set ${{\cal X}}$ of helicopter complexes so that every nice
helicopter complex has a space minor in ${{\cal X}}$.

######  Remark .

Subsection 3.3.2 will be proved in Subsection 3.3.4 below. The finite list
${{\cal X}}$ of Subsection 3.3.2 is computed explicitly in [6, Section: Marked
graphs]; however, here we only prove existence of a finite set as this is much
shorter and contains the central ideas.

Denote by ${{\cal Y}}$ the list of the nine 2-complexes of Section 1.4
together with the finite list ${{\cal X}}$ from Subsection 3.3.2.

Figure 3.2: A 3-star, an edge and a 2-cycle with an attached leaf. Free-graphs
are subdivisions of these graphs.

A _free-graph_ is a subdivision of a 3-star, a path or a cycle with an
attached path, see Figure 3.2. These graphs are ‘free’ in the sense that any
rotation system on them defines an embedding in the plane. A graph is _almost
3-connected_ if it is a subdivision of a 3-connected graph, a parallel graph
or a free-graph. A simplicial complex is _locally almost 3-connected_ if all
its link graphs are almost 3-connected.

######  Remark .

(Motivation) Next we define ‘stretched out’. This is a technical condition,
which is used only three times in the argument, namely in the proofs of
Subsection 3.3.5, Subsection 3.3.5 and Subsection 3.3.2 below. We remark that
the notion of stretched out as defined here is only intended to be useful for
locally 3-connected 2-complexes. In this context, it very roughly says that
every edge of degree two has an endvertex whose link graph is ‘very simple’.

A simplicial complex is _stretched out_ if every edge incident with only two
faces has an endvertex $x$ such that the link graph at $x$ is not a
subdivision of a 3-connected graph and not a parallel graph whose branching
vertices have degree at least three.

######  Theorem 3.3.1.

Let $C$ be a nullhomologous simplicial complex that is locally almost
3-connected and stretched out. The following are equivalent.

  * •

$C$ has a planar rotation system;

  * •

$C$ has no space minor in ${{\cal Y}}\cup{{\cal T}}$.

Next we define ‘para-paths’ (which are similar to para-cycles) and analyse
them. A path in a simplicial complex $C$ is a _para-path_ if

  1. 1.

the link graphs at all interior vertices of $P$ are parallel graphs, where the
branching vertices have degree at least three;

  2. 2.

the link graphs at the two endvertices of $P$ are subdivisions of 3-connected
graphs.

Similar to planarity of para-cycles, we define: a para-path $P$ in a 2-complex
$C$ is _planar_ if there is a choice of embedding at each vertex of $P$ so
that for each edge $e$ of $P$the two rotators at $e$ in the link graphs at its
endvertices are reverse of one another; we additionally require that if the
endvertices of $P$ are joined by an edge $e^{\prime}$, then the chosen
embeddings at the endvertices of $P$ evaluated at the rotators of $e^{\prime}$
are reverse of one another.

As a preparation for the proof of Theorem 3.3.1, we prove the following
analogue of Section 1.2.

######  Lemma .

A null-homological locally almost 3-connected simplicial complex $C$ has one
of the following:

  1. 1.

a planar rotation system;

  2. 2.

a non-planar link graph;

  3. 3.

a non-planar para-path;

  4. 4.

a non-planar para-cycle;

  5. 5.

a space minor that is a nice helicopter complex.

####  3.3.3 Proof of Subsection 3.3.2

A vertex of a 2-complex is _relevant_ if its link graph is a parallel graph
where the two branching vertices have degree at least three or if its link
graph is a subdivision of a 3-connected graph. An edge is _relevant_ if both
its endvertices are relevant and it is incident with at least three faces. A
_pre-rotation framework_ of a 2-complex $C$ is a choice of a embedding at each
link graph at a relevant vertex of $C$ so that at each relevant edge $e$ the
two rotators at $e$ in the chosen embeddings of the link graphs at its
endvertices are reverse of one another or agree. We colour a relevant edge
_green_ if the two rotators are reverse, and we colour if _red_ otherwise, in
which case they agree. A pre-rotation framework is _even_ if every cycle
consisting only of relevant edges contains an even number of red edges;
otherwise it is _odd_. A cycle is _red_ if it contains an odd number of red
edges, and all its edges are incident with at least three faces and it is not
a para-cycle.

######  Lemma .

If an almost locally 3-connected 2-complex $C$ admits an even pre-rotation
framework, then it admits a planar rotation system.

###### Proof.

First imitate the proof of Section 1.2 to modify the pre-rotation system so
that all relevant edges are coloured green. Now pick plane embeddings at link
graphs of remaining vertices, in three steps as follows. Let $X$ be the set of
those non-relevant vertices that are incident with an edge of face-degree
three to a relevant vertex. Since vertices of $X$ have free link graphs, they
are incident with a unique edge of face-degree three and pick an embedding of
their link graph so that the rotator at its unique-degree three vertex is the
reverse of the rotator picked at the link graph at the relevant endvertex of
that edge. An edge of face degree three is _very irrelevant_ if both
endvertices have link graphs that are free. Let $Y$ be the set of endvertices
of very irrelevant edges. Note that $Y$ is disjoint from $X$. Vertices in $Y$
are incident with a unique edge of face-degree three and it is very
irrelevant. Pick an embedding of the two endvertices of that edge so that the
rotator at that edge are reverse. Now we have defined embeddings at all link
graphs of minimum degree at least three. All other link graphs have unique
rotation systems and we pick them. This defines a rotation framework. Since
edges of degree at most two are always green, all edges are green and so this
rotation framework gives rise to a planar rotation system as in the proof of
Section 1.2. ∎

######  Lemma .

If an almost locally 3-connected 2-complex does not admit a pre-rotation
framework, then it has a non-planar link graph, a non-planar para-path or a
non-planar para-cycle.

###### Proof.

We prove the contra-positive: assume that all link graphs at vertices of $C$
are planar, all para-paths are planar and all para-cycles are planar. Our aim
is to construct a pre-rotation framework. At link graphs that are subdivisions
of 3-connected graphs, pick an arbitrary embedding. Since single edges are
examples of para-paths, their planarity ensures compatibility along edges both
whose endvertices have link graphs that are subdivisions of 3-connected
graphs. Now let $X$ be the set of those relevant edges that have an endvertex
whose link graph is a parallel graph. The edge set $X$ – considered as a
subset of the 1-skeleton of $C$ – spans a graph of maximum degree two. So each
connected component of $X$ is a path or a cycle. If it is a cycle, this cycle
is a para-cycle, and by assumption it is planar, so pick embeddings at link
graphs of its vertices accordingly. If this component is a path, this path is
a para-path; call it $P$. The embeddings at the link graphs of the endvertices
of $P$ are unique up to reversing, and since the para-path $P$ is planar, we
can pick embeddings at link graphs of interior vertices of $P$ so that along
each edge of $P$ they are reverse or agree. This defines a pre-rotation
frameworks. ∎

######  Lemma .

If a simplicial complex $C$ has a pre-rotation framework but no planar
rotation system, then it has a red chordless cycle.

###### Proof.

We obtain $G$ from the 1-skeleton of $C$ by deleting all edges that are not
relevant; note that all remaining edges have degree at least three in $C$. By
assumption, $G$ contains a cycle $o$ with an odd number of red edges. The
chordless cycles of $G$ generate all cycles of $G$ over the field
${\mathbb{F}}_{2}$, so in particular the cycle $o$. The parity of the number
of red edges of the sum of two cycles is the sum of their parities. So the
family of chordless cycles generating $o$ cannot all contain an even number of
red edges. Thus in this generating family we find a red chordless cycle. ∎

######  Lemma .

If a simplicial complex $C$ has a pre-rotation framework $\Sigma$ with a red
chordless cycle $o$, then $C$ has a space minor that is a nice helicopter
complex.

###### Proof.

Let $e$ be an arbitrary edge of $o$. We obtain $D$ from $C$ by contracting
$o-e$. Since $o$ is chordless, $e$ is the only loop of $D$. Let $v$ be the
unique vertex of $D$ that is incident with the loop $e$. Suppose for a
contradiction that the link graph at $v$ in $D$ is helicopter planar. The link
graph $L(v)$ at $v$ is the vertex sum over all link graphs of $C$ at the
vertices of the path $o-e$ via the edges of that path. Then by Section 1.1
applied successively along the edges of $o-e$, the embedding of $L(v)$ induces
embeddings at all link graphs at vertices of $o$ in $C$ that are compatible
along the edges. We denote these embeddings of the link graphs at vertices of
$o$ by $(\tau(x)|x\in V(o))$.

We obtain $\Sigma^{\prime}$ from the pre-rotation framework $\Sigma$ by
changing the embeddings at the vertices $x$ of $o$ to $\tau(x)$. Since $o$ is
red, by definition it is not a para-cycle and thus contains a vertex whose
link graph is a subdivision of a 3-connected graph. Its embedding $\tau(x)$ is
the same or the flip of the corresponding embedding for $\Sigma$. Using this
we prove inductively along the edges of $o$ that each embedding $\tau(x)$ is
the same or the flip of the corresponding embedding for $\Sigma$. So
$\Sigma^{\prime}$ is a pre-rotation framework. The cycle $o$ has only green
edges in the pre-rotation framework $\Sigma^{\prime}$. Modifying the pre-
rotation framework $\Sigma$ by flipping embeddings at link graphs of $C$ does
not change the parity of the red edges of $o$. So the cycle $o$ contains an
even number of red edges with respect to $\Sigma$, a contradiction to the
assumption that $o$ is red. So the link graph at $v$ is not helicopter planar.
The link graph at $v$ is a subdivision of a 3-connected graph, and thus the
space minor $D$ is nice. ∎

We summarise this subsection with the following.

###### Proof of Subsection 3.3.2.

By Subsection 3.3.3 assume that $C$ admits a pre-rotation framework. If it is
even, by Subsection 3.3.3, $C$ admits a planar rotation system and we find one
of the outcomes. So assume that it is odd. By Subsection 3.3.3 $C$ has a red
chordless cycle. Then by Subsection 3.3.3 $C$ has a helicopter complex as a
space minor; this is outcome 5. ∎

####  3.3.4 Helicopter minors

The aim of this section is to prove Subsection 3.3.2; we begin by introducing
our tools. A _helicopter graph_ is a graph $G$ together with two of its
vertices $v$ and $w$ and three pairs $((a_{i},b_{i})|i=1,2,3)$ of its edges,
where the edges $a_{i}$ are incident with $v$ and the edges $b_{i}$ are
incident with $w$. We stress that we allow $a_{i}=b_{j}$ for some $i,j\in[3]$
and $v=w$.

A helicopter graph $(G,v,w,((a_{i},b_{i})|i=1,2,3))$ is _helicopter planar_ if
there is a planar rotation system $(\sigma_{x}|x\in V(G))$ of $G$ such that
the rotator $\sigma_{v}$ at $v$ restricted to $(a_{1},a_{2},a_{3})$ is the
reverse permutation of the rotator $\sigma_{w}$ at $w$ restricted to
$(b_{1},b_{2},b_{3})$ – when concatenated with the bijective map $b_{i}\mapsto
a_{i}$.

######  Example .

Let $C$ be a 2-complex with a single loop $\ell$ and $x$ be the unique vertex
of $C$ incident with $\ell$. Let $(f_{1},f_{2},f_{3})$ be a choice of three
faces incident with $\ell$. Denote the vertices corresponding to $\ell$ in the
link graph $L(x)$ by $v$ and $w$, and let $a_{i}$ be the edge of $L(x)$
incident with $v$ corresponding to $f_{i}$. Similarly, let $b_{i}$ be the edge
of $L(x)$ incident with $w$ corresponding to $f_{i}$. Then
$(L(x),v,w,((a_{i},b_{i})|i=1,2,3))$ is a helicopter graph.

We refer to the helicopter graph constructed in Subsection 3.3.4 as the
helicopter graph _associated_ to $C$ at $x$ given the choices
$(f_{1},f_{2},f_{3})$. The connection with helicopter complexes is as follows.

######  Lemma .

Let $C$ be a 2-complex with a single loop $\ell$ and $x$ be the unique vertex
of $C$ incident with $\ell$. Then $C$ is a helicopter complex if one of the
helicopter graphs associated to $C$ at $x$ is not helicopter planar.

###### Proof.

If an associated helicopter graph is not helicopter-planar, then the link
graph cannot be helicopter planar; and thus $C$ is a helicopter complex. ∎

A helicopter graph $(G,v,w,((a_{i},b_{i})|i=1,2,3))$ is _3-connected_ if $G$
is 3-connected. We abbreviate $A=\\{a_{1},a_{2},a_{3}\\}$ and
$B=\\{b_{1},b_{2},b_{3}\\}$.

A _helicopter minor_ of a helicopter graph $(G,v,w,((a_{i},b_{i})|i=1,2,3))$
is obtained by doing a series of the following operations:

  * •

contracting or deleting an edge not in $A\cup B$;

  * •

replacing an edge $a_{i}\in A\setminus B$ and an edge $b_{j}\in B\setminus A$
that are in parallel by a single new edge which is in that parallel class. In
the reduced graph, this new edge is $a_{i}$ and $b_{j}$.

  * •

the above with ‘series’ in place of ‘parallel’.

  * •

apply the bijective map222That is, we exchange the roles of the vertices ‘$v$’
and ‘$w$’ and the roles of ‘$a_{i}$’ and ‘$b_{i}$’ are interchanged for
$i\in[3]$. $(v,A)\mapsto(w,B)$.

######  Lemma .

Let $\hat{G}=(G,v,w,((a_{i},b_{i})|i=1,2,3))$ be a helicopter graph such that
G is planar. Let $\hat{H}$ be a 3-connected helicopter minor of $\hat{G}$.
Then $\hat{G}$ is helicopter planar if and only if $\hat{H}$ is helicopter
planar.

Before we can prove this, we need to recall some facts about rotation systems
of graphs. Given a graph $G$ with a rotation system $\Sigma=(\sigma_{v}|v\in
V(G))$ and an edge $e$. The rotation system _induced_ by $\Sigma$ on $G-e$ is
$(\sigma_{v}-e|v\in V(G))$. Here $\sigma_{v}-e$ is obtained from the cyclic
ordering $\sigma_{v}$ by deleting the edge $e$. The rotation system _induced_
by $\Sigma$ on $G/e$ is $(\sigma_{v}|v\in V(G/e)-e)$ together with
$\sigma_{e}$ defined as follows. Let $v$ and $w$ be the two endvertices of
$e$. Then $\sigma_{e}$ is obtained from the cyclic ordering $\sigma_{v}$ by
replacing the interval $e$ by the interval $\sigma_{w}-e$ (in such a way that
the predecessor of $e$ in $\sigma_{v}$ is followed by the successor of $e$ in
$\sigma_{w}$). Summing up, $\Sigma$ induces a rotation system at every minor
of $G$. Since the class of plane graphs333A _plane graph_ is a graph together
with an embedding in the plane.  is closed under taking minors, rotation
systems induced by planar rotation systems are planar.

###### Proof of Subsection 3.3.4.

Let $\Sigma$ be a planar rotation system of $G$. Let $\Sigma^{\prime}$ be the
rotation system of the graph $H$ of $\hat{H}$ induced by $\Sigma$. As
mentioned above, $\Sigma^{\prime}$ is planar.

Moreover, $\Sigma$ witnesses that $\hat{G}$ is helicopter planar if and only
if $\Sigma^{\prime}$ witnesses that $\hat{H}$ is helicopter planar. Hence if
$\hat{G}$ is helicopter planar, so is $\hat{H}$. Now assume that $\hat{H}$ is
helicopter planar. Since $H$ is 3-connected, it must be that $\Sigma^{\prime}$
witnesses that the helicopter graph $\hat{H}$ is helicopter planar. Hence the
helicopter graph $\hat{G}$ is helicopter planar. ∎

Our aim is to characterise when 3-connected helicopter graphs are helicopter
planar. By Subsection 3.3.4 it suffices to study that question for helicopter-
minor minimal 3-connected helicopter graphs; we call such helicopter graphs
_3-minimal_.

It is reasonable to expect – and indeed true, see below – that there are only
finitely many 3-minimal helicopter graphs, as follows.

Let $\hat{G}=(G,v,w,((a_{i},b_{i})|i=1,2,3))$ be a helicopter graph. We denote
by $V_{A}$ the set of endvertices of edges in $A$ different from $v$. We
denote by $V_{B}$ the set of endvertices of edges in $B$ different from $w$.

######  Lemma .

Let $\hat{G}=(G,v,w,((a_{i},b_{i})|i=1,2,3))$ be 3-minimal. Unless $G$ is
$K_{4}$, every edge in $E(G)\setminus(A\cup B)$ has its endvertices either
both in $V_{A}$ or both in $V_{B}$.

In the proof of Subsection 3.3.4 we shall use the following lemma of Bixby.

######  Lemma  (Bixby’s lemma [3] or [27, Lemma 8.7.3]).

Let $G$ be a 3-connected graph different444In the original paper, Bixby proves
this lemma in the more general context of matroids and the definitions are set
up so that the matroids $U_{1,3}$ and $U_{2,3}$ are 3-connected and thus the
assumption $G\neq K_{4}$ is not necessary. from $K_{4}$. For every edge $e$ of
$G$ the simplification of $G/e$ or the co-simplification of $G-e$ is
3-connected.

###### Proof of Subsection 3.3.4..

By assumption $G$ is a 3-connected graph with at least five vertices such that
any proper helicopter minor of $\hat{G}$ is not 3-connected. Let $e$ be an
edge of $G$ that is not in $A\cup B$. By Bixby’s Lemma (Subsection 3.3.4)
either $G-e$ is 3-connected after suppressing series edges or $G/e$ is
3-connected after suppressing parallel edges.

######  Claim .

There is no 3-connected graph $H$ obtained from $G-e$ by suppressing series
edges.

Proof of Claim. Suppose for a contradiction that there is such a graph $H$. As
$G$ is 3-connected, every class of series edges of $G-e$ has size at most two.
By minimality of $G$, there is no helicopter minor of $\hat{G}$ with graph
$H$. Hence one of these series classes has to contain two edges in $A$ or two
edges in $B$. By symmetry, we may assume that $e$ has an endvertex $x$ that is
incident with two edges $e_{1}$ and $e_{2}$ in $A$. As $G$ is 3-connected
these two adjacent edges of $A$ can only share the vertex $v$. Thus $x=v$.
This is a contradiction to the assumption that $e_{1}$ and $e_{2}$ are in
series as $v$ is incident with the three edges of $A$. ! $\diamondsuit$

By Subsection 3.3.4 and Bixby’s Lemma (Subsection 3.3.4), we may assume that
the graph $H$ obtained from $G/e$ by suppressing parallel edges is
3-connected. By minimality of $G$, there is no helicopter minor of $\hat{G}$
with graph $H$. Hence $G/e$ has a nontrivial parallel class; and it must
contain two edges $e_{1}$ and $e_{2}$ that are both in $A$ or both in $B$. By
symmetry we may assume that $e_{1}$ and $e_{2}$ are in $A$. Since $G$ is
3-connected, the edges $e$, $e_{1}$ and $e_{2}$ form a triangle in $G$. The
common vertex of $e_{1}$ and $e_{2}$ is $v$. Thus both endvertices of $e$ are
in $V_{A}$. ∎

A consequence of Subsection 3.3.4 is that every 3-minimal helicopter graph has
at most most 12 edges. However, we can say more:

######  Corollary .

Let $\hat{G}=(G,v,w,((a_{i},b_{i})|i=1,2,3))$ be 3-minimal. Then $G$ has at
most five vertices.

###### Proof.

Let $G_{A}$ be the induced subgraph with vertex set $V_{A}+v$. Let $G_{B}$ be
the induced subgraph with vertex set $V_{B}+w$. Note that $G=G_{A}\cup G_{B}$.
If $G_{A}$ and $G_{B}$ have at least three vertices in common, then $G$ has at
most five vertices as $G_{A}$ and $G_{B}$ both have at most four vertices.
Hence we may assume that $G_{A}$ and $G_{B}$ have at most two vertices in
common. As $G$ is 3-connected, the set of common vertices cannot be a
separator of $G$. Hence $G_{A}\subseteq G_{B}$ or $G_{B}\subseteq G_{A}$.
Hence $G$ has at most four vertices in this case. ∎

###### Proof of Subsection 3.3.2..

Let $C$ be a 2-complex with a single loop $\ell$ be given. Let $x$ be its
unique vertices incident with the loop $\ell$. Assume that the link graph at
$x$ is a subdivision of a 3-connected graph. Assume that the link graph at $x$
is not helicopter planar. Our aim is to construct a helicopter complex of
bounded size that has $C$ as a space minor.

We denote the link graph at $x$ by $G$. If $G$ is non-planar, we are done by
Subsection 1.3.1 and Section 1.4, so assume it is planar. Since $G$ is not
helicopter planar but planar, the loop must be incident with at least three
faces. Since $G$ is a subdivision of a 3-connected graph, it has a unique
embedding in the plane (up to reversing). Since $G$ is not helicopter planar,
no associated helicopter graph can be helicopter planar. Let
$\hat{G}=(G,v,w,((a_{i},b_{i})|i=1,2,3))$ be some associated helicopter graph.
$\hat{G}$ has a 3-connected helicopter graph as a helicopter minor. So by
definition of 3-minimality, $\hat{G}$ has a 3-minimal minor
$\hat{H}=(H,v,w,((a_{i},b_{i})|i=1,2,3))$; say, $H$ is obtained from $G$ by
contracting the edge set $Z$ and deleting the edge set $D$, in formulas:
$H=G/Z\setminus D$.

Amongst all choices for sets $Z$ and $D$ we pick one so that $D$ is inclusion-
wise maximal. Let $D^{\prime}$ consist of those edges of $D$ that do not carry
any label. We obtain $\hat{I}=(I,v,w,((a_{i},b_{i})|i=1,2,3))$ from $\hat{G}$
by deleting those edges of $D^{\prime}$. By the choice of $D$ and since $H$
has bounded size by Subsection 3.3.4, all but boundedly many edges of $Z$ are
subdividing edges in $I$. We obtain $Z^{\prime}$ from $Z$ by removing all
edges that carry labels and removing all edges that are not subdivision edges
in $I$ and removing two subdivision edges of each edge of $I$, and if there
are less than two subdivision edges for some edge of $I$ we remove all of
them; note that $Z\setminus Z^{\prime}$ has bounded size. We obtain
$\hat{J}=(J,v,w,((a_{i},b_{i})|i=1,2,3))$ from $\hat{I}$ by contracting
$Z^{\prime}$. This construction ensures that $J=G/Z^{\prime}\setminus
D^{\prime}$. By Subsection 3.3.4 $\hat{H}$ has bounded size and since only a
bounded number of edges carry labels and $Z\setminus Z^{\prime}$ is bounded,
also $\hat{J}$ has bounded size.

######  Example .

This construction ensures that in the graph $\hat{J}$ the vertices $v$ and $w$
are distinct as they are distinct in $\hat{G}$.

Since $\hat{G}$ is not helicopter planar, by Subsection 3.3.4 $\hat{H}$ is not
helicopter planar. Applying the other implication of Subsection 3.3.4 to
$\hat{J}$ and $\hat{H}$ we deduce that $\hat{J}$ is not helicopter planar.

It remains to show that $C$ has a space minor $\hat{C}$ that is a helicopter
2-complex so that its unique vertex $y$ incident with the loop has the
property that $\hat{J}$ is an associated helicopter link graph of $\hat{C}$ at
$y$, and so that $\hat{C}$ has bounded size. We obtain $C_{1}$ from $C$ by
deleting all faces and edges that are not incident with the vertex $x$ and
then splitting all vertices except for $x$. The link graph of $C_{1}$ at $x$
is $G$, and all edges not incident with $x$ are in a single face, and are
nonloops. Moreover, all its vertices are equal to $x$ or adjacent to it and
all its edges or faces correspond to vertices or edges of $G$.

We obtain $C_{2}$ from $C_{1}$ by deleting all faces corresponding to edges in
$D^{\prime}$, and then split at all vertices aside from $x$, and delete
isolated edges of $C$. The link graph of $C_{2}$ at $x$ is $G\setminus
D^{\prime}$. If a non-loop edge incident with $x$ is incident with exactly two
faces, then the link graph at its endvertex other than $x$ is a path
consisting of two edges. Let $Z^{\prime\prime}$ be the set of edges of $C_{2}$
not incident with $x$ that are in faces corresponding to an edge of $L(x)$ in
$Z^{\prime}$. We obtain $C_{3}$ from $C_{2}$ by contracting
$Z^{\prime\prime}$. The link graph of $C_{3}$ at $x$ is $G\setminus
D^{\prime}$.

######  Claim .

$C_{3}$ has only the loop $\ell$, and $C_{3}$ is a space minor of $C_{2}$.

Proof of Claim. Recall that $C_{2}$ has only the loop $\ell$, so we need to
investigate whether a new loop can arise from the contraction of
$Z^{\prime\prime}$. Let $P$ be a path of $I$ all of whose internal vertices
have degree two in $I$. Let $F_{P}$ be the set of faces whose corresponding
edges in the link graph $L(x)$ are edges in $P$. Let $C_{2}^{\prime}$ be the
2-complex obtained from $C_{2}$ by deleting the faces of $F_{P}$ and after
that deleting edges not in a face, and split isolated vertices. Now $C_{2}$
can be obtained from $C_{2}^{\prime}$ by adding the cone over $P$ at the path
of length two corresponding to the first and last vertex of $P$. The set
$Z^{\prime}$ avoids all edges of $P$ or at least two of them. Since
contracting these edges commutes with the gluing of the cone over $P$ onto
$C_{2}^{\prime}$, it does not create any loop. This is true for every choice
of $P$ and contracting edges on different paths does not affect the other
paths. In particular, we can contract the edges of $Z^{\prime\prime}$ in
$C_{2}$ successively so that none of them creates a loop contracted, so
$C_{3}$ is a space minor of $C_{2}$. ! $\diamondsuit$

For every edge in $Z^{\prime}$ its corresponding face of $C_{3}$ contains two
edges since $C_{3}=C_{2}/Z^{\prime\prime}$. Since $\ell$ is the only loop of
$C_{3}$ by Subsection 3.3.4, it cannot be in any of these faces of size two.
We obtain $\hat{C}$ from $C_{3}$ by contracting each face corresponding to an
edge of $Z^{\prime}$ onto a single edge. The link graph at $x$ is
$J=G/Z^{\prime}\setminus D^{\prime}$. By Subsection 3.3.4 $\hat{C}$ has only
the loop $\ell$ and is a space minor of $C$. Since $\hat{J}$ is not helicopter
planar, by Subsection 3.3.4 $\hat{C}$ is a helicopter complex. Moreover,
$\hat{C}$ has bounded size as all its vertices are equal to $x$ or adjacent to
it and all its edges or faces correspond to one of the boundedly many vertices
or edges of $J$.

∎

####  3.3.5 Proof of Theorem 3.3.1

######  Lemma .

Let $C$ be a stretched-out simplicial complex with a non-planar para-path $P$.
Assume that the endvertices of $P$ are joined by an edge $e$ in $C$.

Then $e$ is a non-planar para-path or $C$ has a space minor that is a
helicopter complex.

###### Proof.

Since we are done otherwise, assume that $e$ is not a para-path; that is, in
$C/e$ the link graph at $e$ is planar. Let $x$ be an arbitrary edge of $P$.
The 2-complex $D$ is obtained from $C$ by contracting $P+e-x$. Since $C$ is
stretched out, the edge $x$ is the only loop of $D$. Let $v$ be the vertex of
$D$ incident with $x$. If the link graph at $v$ in $D$ is helicopter planar,
by Section 1.1 applied successively along the edges $P$, the para-path $P$ is
planar. Since this is not possible by assumption, the link graph at $v$ is not
helicopter planar. So $D$ is a helicopter complex. ∎

######  Lemma .

Let $C$ be a stretched-out simplicial complex with a non-planar para-path $P$
so that the two endvertices of $P$ are not adjacent in $C$.

Then $C$ has a space minor $D$ that is a simplicial complex and has an edge
$e$ so that the link graph of $D/e$ at the vertex $e$ is not planar.

###### Proof.

We obtain $C_{1}$ from $C$ by topologically deleting all edges of $C$ that do
not have an endvertex on $P$ and then we split all vertices outside $P$. Note
that $C_{1}$ is a simplicial complex and it is stretched out. Let $e$ be an
arbitrary edge on $P$. We obtain $C_{2}$ from $C_{1}$ by contracting the edges
of $P-e$. By construction of $C_{1}$, the 2-complex $C_{2}$ has no loops and
if edges are in parallel, then they form a face of size two. We obtain $D$
from $C_{2}$ by contracting all faces of size 2. By construction of $C_{2}$,
the 2-complex $D$ is a simplicial complex. The link graphs at the two
endvertices of $e$ in $D$ are isomorphic to the link graphs at the endvertices
of $P$ in $C$. So the edge $e$ is a non-planar para-path in $D$; that is, the
link graph of $D/e$ at the vertex $e$ is not planar. ∎

We summarise this section in the following.

###### Proof of Theorem 3.3.1..

Let $C$ be a nullhomologous simplicial complex that is locally almost
3-connected and stretched out. First note that by Subsection 3.3.2 no
2-complex in ${{\cal X}}$ admits a planar rotation system, and so by Theorem 1
and Section 1.4 no 2-complex in ${{\cal Y}}$ admits a planar rotation system.
2-complexes in ${{\cal T}}$ do not admit planar rotation system, as explained
in the Introduction to this chapter.

Conversely, assume that $C$ has no planar rotation system. Then by Subsection
3.3.2 we get outcome 2, 3, 4 or 5 from that lemma. Outcome 2 gives a cone over
$K_{5}$ or $K_{3,3}$ as a space minor by Subsection 1.3.1 and Section 1.4;
such cones as in ${{\cal Y}}$.

Outcome 3 gives a non-planar para-path $P$. If $P$ consists of a single edge,
we can directly infer Subsection 1.3.2 and Section 1.4 to find a combined cone
from ${{\cal Y}}$ as a space minor of $C$. If otherwise the two endvertices of
$P$ are not adjacent, we use Subsection 3.3.5 to reduce to the case that $P$
has a single edge, and so are done here as well. In the remaining cases, we
rely on Subsection 3.3.5 to find outcome 5, which is discussed below.

Outcome 4 is a non-planar para-cycle. By Subsection 3.3.1 it gives rise to a
torus crossing obstruction, and thus an element of ${{\cal T}}$. Outcome 5 is
a helicopter complex, which contains an element of ${{\cal X}}$ by Subsection
3.3.2; and ${{\cal X}}\subseteq{{\cal Y}}$ by definition. ∎

###  3.4 Stretching local 2-separators

In this section we define stretching at local 2-separators and prove basic
properties of this operation. This operation is necessary for Theorem 3.2.2.

A _2-separator_ in a 2-connected graph555In this paper we will only consider
2-separators of link graphs of simplicial complexes; such link graphs do not
have parallel edges or loops. For multigraphs, it seems suitable to also
consider $(a,b)$ a 2-separator if there are two parallel edges between them
and $L-a-b$ is not empty or $a$ and $b$ have three parallel edges in between.
$L$ is a pair of vertices $(a,b)$ such that $L-a-b$ has at least two connected
components.

Given a simplicial complex $C$ with a vertex $v$ such that its link graph
$L(v)$ is 2-connected and has a 2-separator $(a,b)$, the simplicial complex
$C_{2}$ obtained from $C$ by _stretching $\\{a,b\\}$ at $v$_ is defined as
follows, see Figure 3.3.

Figure 3.3: If we stretch the highlighted pair of edges in the simplicial
complex on the left, we obtain the one on the right. The newly added faces are
depicted in grey. Figure 3.4: The simplicial complex $\Delta_{2}$.

We denote by $\Delta_{2}$ the simplicial complex obtained from two disjoint
faces of size three by gluing them together at an edge, see Figure 3.4. Let
$\Delta^{+}_{n}$ be the simplicial complex obtained by gluing $n$ copies of
$\Delta_{2}$ together at a path of length two whose endvertices have degree
two in $\Delta_{2}$ (this is uniquely defined up to isomorphism), see Figure
3.5.

Figure 3.5: The simplicial complex $\Delta^{+}_{3}$ with the gluing edges
labelled $\bar{a}$ and $\bar{b}$.

Informally, we obtain $C_{2}$ from $C$ by replacing the edges $a$ and $b$ by
$\Delta^{+}_{n}$, where $n$ is the number of components of $L(v)-a-b$. More
precisely, the simplicial complex $C_{2}$ is defined as follows. Let $n$ be
the number of components of $L(v)-a-b$. We denote the gluing edges of
$\Delta^{+}_{n}$ by $\bar{a}$ and $\bar{b}$. We label the vertices of
$\Delta^{+}_{n}$ incident with neither $\bar{a}$ nor $\bar{b}$ by the
components of $L(v)-a-b$.

In our notation we suppress a bijection between vertices of $C$ and
$\Delta^{+}_{n}$ as follows. We label the common vertex of the edges of
$\bar{a}$ and $\bar{b}$ by $v$. We denote the endvertex of the edge $a$ in $C$
different from $v$ by $w_{a}$; and we label the endvertex of the edge
$\bar{a}$ different from $v$ by $w_{a}$. Similarly, we denote the endvertex of
the edge $b$ in $C$ different from $v$ by $w_{b}$; and we label the endvertex
of the edge $\bar{b}$ different from $v$ by $w_{b}$.

  * •

The vertex set of $C_{2}$ is union of the vertex set of $C$ together with the
vertex set of $\Delta^{+}_{n}$, in formulas: $V(C_{2})=V(C)\cup
V(\Delta^{+}_{n})$. We stress that the sets $V(C)$ and $V(\Delta^{+}_{n})$
share the vertices $v$, $w_{a}$ and $w_{b}$ and hence these vertices appear in
$V(C_{2})$ only once as $V(C_{2})$ is just a set and not a multiset;

  * •

the edge set of $C_{2}$ is (in bijection with) the edge set of $C$ with the
edges $a$ and $b$ replaced by the set of edges of $\Delta^{+}_{n}$, in
formulas: $E(C_{2})=\left(E(C)-a-b\right)\cup E(\Delta^{+}_{n})$. The
incidences between vertices and edges are as in $C$ or $\Delta^{+}_{n}$,
except for those edges of $C$ that have the vertex $v$ as an endvertex. This
defines all incidences of edges except those of $C$ that have the endvertex
$v$. Given an edge $x$ of $C$ incident with $v$, and denote its other
endvertex by $x^{\prime}$. Then its corresponding edge of $C_{2}$ has the
endvertices $x^{\prime}$ and the vertex of $\Delta^{+}_{n}$ that is the
component of $L(v)-a-b$ containing $x$. This completes the definition of the
edges of $C_{2}$. We stress that the vertex $w_{a}$ of $C_{2}$ is incident
with those edges of $C-a-b$ with endvertex $w_{a}$ and those edges of
$\Delta^{+}_{n}$ with endvertex $w_{a}$;

  * •

the faces of $C_{2}$ are the faces of $C$ together with the faces of
$\Delta^{+}_{n}$; in formulas: $F(C_{2})=F(C)\cup F(\Delta^{+}_{n})$. We
stress that the sets $F(C)$ and $F(\Delta^{+}_{n})$ are disjoint. The
incidences between edges and faces are as in $C$ or $\Delta^{+}_{n}$, where
defined. This defines all incidences of faces except for those faces $f$ of
$C$ incident with the edges $a$ or $b$, which are defined as follows. There
are three cases:

– if $f$ is a face of $C$ incident with both the edges $a$ and $b$, then in
$C_{2}$ these incidences are replaced by incidences with the edges $\bar{a}$
and $\bar{b}$;

– if $f$ is a face of $C$ incident with the edge $a$ but not $b$, then in
$C_{2}$ the incidence of $f$ with $a$ is replaced with an incidence with the
edge $w_{a}x$ of $\Delta^{+}_{n}$; where $x$ is the component of $L(v)-a-b$
such that in $L(v)$ the edge $f$ joins $a$ with a vertex of $x$;

– similarly, if $f$ is a face of $C$ incident with the edge $b$ but not $a$,
then in $C_{2}$ the incidence of $f$ with $b$ is replaced with an incidence
with the edge $w_{b}x$ of $\Delta^{+}_{n}$; where $x$ is the component of
$L(v)-a-b$ such that in $L(v)$ the edge $f$ joins $b$ with a vertex of $x$.

This completes the definition of stretching a 2-separator at a vertex.

We refer to the vertices of $C_{2}$ that are not in $V(C)-v$ as the _new
vertices_ , other vertices of $C_{2}$ are called _old_.

The link graph at $w_{a}$ of $C$ is obtained from the link graph at $w_{a}$ in
$C_{2}$ by contracting all edges incident with the vertex $\bar{a}$. Note that
$w_{a}$ cannot be incident with $b$ as $C$ is a simplicial complex.

######  Example .

In Figure 3.6 we explain how the link graphs of Figure 3.3 change.

Figure 3.6: On the left we see the link graphs at the vertices $w_{a}$,
$w_{b}$ and $v$ of the simplicial complex in Figure 3.3. On the right we see
the link graphs after the stretching at $(a,b)$. The vertices $a$ and $b$ and
the new vertices and edges in the link graphs are depicted in grey.

The _(abbreviated) degree-sequence_ of a graph is the sequences of degrees of
its vertices, ordered by size, where we leave out the degrees which are at
most two. We compare degree-sequences in the lexicographical order.

######  Lemma .

Let $C_{2}$ be a simplicial complex obtained from $C$ by stretching the
2-separator $(a,b)$ at $v$. Then at each vertex of $C$ aside from $v$, the
degree-sequence at its link in $C_{2}$ is at most the degree-sequence at its
link in $C$. At all new vertices of $C_{2}$ the degree-sequence at the link is
strictly smaller than the degree-sequence of the link graph at $v$ in $C$ –
unless the link graph at $v$ in $C$ is a parallel graph or $L(v)-a-b$ has two
components and one is a path.

###### Proof.

Coadding a star at a vertex cannot increase the abbreviated degree-sequence,
hence the lemma is true at old vertices of $C_{2}$. So it remains to prove the
lemma for the new vertices of $C_{2}$ as it is obvious at the others. As the
link graph $L(v)$ at $v$ in $C$ is not a parallel graph, the degree-sequence
at the link at $v$ in $C_{2}$ is strictly smaller than that in $C$. Now let
$X$ be a component of $L(v)-a-b$. If $L(v)-a-b$ has at least three components,
then the degree-sequence at the link at $X$ in $C_{2}$ is strictly smaller the
degree-sequence of the link graph at $v$ in $C$. This is also true if
$L(v)-a-b$ has only two components and the other component has a vertex of
degree greater than two; that is, is not a path. This completes the proof of
the lemma. ∎

The _degree-parameter_ of a 2-complex is the sequence of degree-sequences of
all its link graphs, ordered by size. We compare degree-parameters in the
lexicographical order.

######  Lemma .

Let $C$ be a simplicial complex such that all link graphs are 2-connected or
free-graphs. Then we can apply stretchings at local 2-separators of
2-connected link graphs such that the resulting simplicial complex is locally
almost 3-connected.

Before we prove this, we need a definition. A 2-separator $(x,y)$ in a graph
$G$ is _proper_ unless $G-x-y$ has precisely two components and one of them is
a path and $xy$ is not an edge.

###### Proof.

If $C$ has a 2-connected link graph that is not a parallel graph or a
subdivision of a 3-connected graph, it contains a proper 2-separator and we
stretch at that 2-separator. Link graphs at other vertices remain 2-connected
or free graphs, respectively. By Section 3.4 the degree-parameter goes down
and hence this process has to stop after finitely many steps – with the
desired simplicial complex. ∎

Until the rest of this section we fix a simplicial complex $C$ with a vertex
$v$ such that the link $L(v)$ is 2-connected and let $(a,b)$ be a 2-separator
of $L(v)$. We denote the simplicial complex obtained from $C$ by stretching
$(a,b)$ at $v$ by $C_{2}$.

######  Remark .

$C$ can be obtained from $C_{2}$ as follows. First we contract the edges
incident with the vertex $v$ except for $\bar{a}$ and $\bar{b}$. We relabel
$\bar{a}$ by $a$ and $\bar{b}$ by $b$. We obtain some faces of size two, we
refer to these faces as _tiny_ faces. Then we contract all these tiny faces.
This gives $C$.

We say that an operation, such as contracting an edge, is an _equivalence_ for
a property, such as the existence of a planar rotation systems, if a
simplicial complex has that property if and only if the simplicial complex
after applying this operation has this property.

In Section 1.1 it is shown that contracting a non-loop edge where the link
graph at both endvertices are 2-connected is an equivalence for the existence
of planar rotation systems. Contracting a face of size two is not always an
equivalence for the existence of planar rotation systems but here the
contracted faces have the following additional property.

A face $f$ incident with only two edges $e_{1}$ and $e_{2}$ is _redundant_ if
there is a vertex $v$ incident with $f$ such that in $C/f$ in any planar
rotation system of the link graph $L(v)$ at the rotator at $f$, the edges
incident with $e_{1}$ in the link at $v$ for $C$ form an interval. (This
implies that also the edges incident with $e_{2}$ in the link at $v$ for $C$
form an interval.)

The following is obvious.

######  Observation .

Let $C^{\prime}$ be obtained from $C$ by contracting a redundant face. If
$C^{\prime}$ has a planar rotation system, then $C$ has a planar rotation
system. ∎

######  Observation .

Tiny faces (as defined in Section 3.4) are redundant.

###### Proof.

Let $X$ be a component of $L(v)-a-b$. Since $L(v)$ is 2-connected, the edges
between $a$ and $X$ form an interval in any rotator at $a$ for any embedding
of $L(v)$ in the plane. The same is true for ‘$b$’ in place of ‘$a$’. ∎

######  Lemma .

The simplicial complex $C$ has a planar rotation system if and only if the
simplicial complex $C_{2}$ has a planar rotation system.

###### Proof.

It is shown in Section 1.1 that contracting a non-loop edge where the link
graph at both endvertices are 2-connected is an equivalence for the existence
of planar rotation systems.

By Section 1.4 contracting a face of size two preserves the existence of
planar rotation systems. So contracting tiny faces is an equivalence for the
existence of planar rotation systems by Section 3.4 and Section 3.4.

Hence all the operation that transform the simplicial complex $C_{2}$ to $C$
as described in Section 3.4 are equivalences. Thus stretching at local
2-separators is an equivalence for planar rotation systems. ∎

The following is geometrically clear, see Figure 3.3, and we will not use it
in our proofs.

######  Lemma .

If $C$ embeds in 3-space, then also $C_{2}$ embeds in 3-space. ∎

######  Remark .

Also the converse of Section 3.4 is true.

###  3.5 Stretching a local branch

In this section we define stretching local branches and prove basic properties
of this operation. This operation is necessary for Theorem 3.2.2.

Given a connected graph $G$ with a cut-vertex $v$, a _branch_ at $v$ is a
connected component $X$ of $G-v$ together with the vertex $v$ (and all edges
between $X$ and $v$). A _branch of $G$_ is a branch at some cut-vertex of $G$.
For any branch $B$, there is a unique vertex $v$ such that $B$ is a branch at
$v$; we refer to that vertex $v$ as _the cut-vertex_ of the branch $B$.

Given a 2-complex $C$ with a vertex $v$ such that the link graph $L(v)$ at $v$
is connected and a branch $B$ of $L(v)$, the complex $C[B]$ obtained from $C$
by _pre-stretching_ $B$ is defined as follows, see Figure 3.7. We denote the
cut-vertex of the branch $B$ by $e$; and remark that $e$ is an edge of the
simplicial complex $C$.

Figure 3.7: The 2-complex on the right is obtained from the 2-complex on the
left by stretching the branch $B$, which consists of the grey box together
with the three faces attaching at the grey box. Stretching is defined like
pre-stretching but there we additionally subdivide faces to make them all have
size three.

  * •

The vertex set of $C[B]$ is that of $C$ together with one new vertex, which we
denote by $v[B]$, in formulas: $V(C_{1})=V(C)\cup\\{v[B]\\}$;

  * •

the edge set of $C[B]$ is (in bijection with) the edge set of $C$ together
with one additional edge, which we denote by $e[B]$, in formulas:
$E(C[B])=E(C)\cup\\{e[B]\\}$; The incidences between edges and vertices are as
in $C$ except for those edges $z\neq e$ of $C$ that are vertices of the branch
$B$. Such edges are incident with the new vertex $v[B]$ in place of $v$, the
other endvertex is not changed. The edge $e[B]$ has the endvertices $v$ and
$v[B]$;

  * •

the faces of $C[B]$ are (in bijection with) the faces of $C$; in formulas:
$F(C[B])=F(C)$. The incidences between faces and edges are as in $C$ except
for those faces of $C$ that are incident with the edge $e$ and are in the link
graph $L(v)$ edges of the branch $B$. These faces now have size four. They are
now additionally incident with the edge $e[B]$.

This completes the definition of pre-stretching the branch $B$ at $v$.
_Stretching_ the branch $B$ is defined the same way except that we
additionally subdivide each face $f$ of size four once. Namely we add a
subdivision-edge between the vertex $v$ and the unique vertex of the face that
is not in the edge $e$ and different from $v[B]$. Hence for any simplicial
complex $C$ any stretching at a branch is again a simplicial complex.

See Figure 3.8 for an example illustrating how the link changes at the vertex
$v$ and how the link looks like at the vertex $v[B]$.

Figure 3.8: On the left we see the link graph of a vertex $v$ with a cut-
vertex $e$ and a branch $B$. On the right we see the link graphs of the two
vertices obtained from the link graph of $v$ by stretching $B$.

Until the rest of this section we fix a simplicial complex $C$ with a vertex
$v$ such that the link graph $L(v)$ is connected and let $B$ be a branch of
that link. We denote the simplicial complex obtained from $C$ by stretching
$B$ by $C[B]$.

######  Remark .

The simplicial complex $C$ can be obtained from $C[B]$ as follows. First we
contract the edge $e[B]$. This makes the faces incident with $e[B]$ in $C[B]$
have size two. Then we contract these faces. This gives $C$. The contracted
faces are incident with an edge that is incident with only one other face.

######  Lemma .

The simplicial complex $C[B]$ has a planar rotation system if and only if $C$
has a planar rotation system.

###### Proof.

Let $\Sigma$ be a planar rotation system of the simplicial complex $C$. We
define666Faces incident with the edge $e$ in $C$ correspond in $C[B]$ either
to a single face of size three or two faces of size three obtained from a face
of size four by subdivision. This induces a bijective map from the faces
incident $e$ in $C$ to the faces incident with $e$ in $C[B]$, and an injective
partial map from the faces incident $e$ in $C$ to the faces incident with
$e[B]$ in $C[B]$. In order to simplify the presentation of the definition we
suppress these two maps. a rotation system $\Sigma^{\prime}$ of the simplicial
complex $C[B]$ by taking the same rotator as $\Sigma$ at every edge except for
$e[B]$ and other new edges, which are incident with two faces. At the edges
incident with two faces we take the unique cyclic ordering of size two. The
rotator at the edge $e[B]$ is constructed from the rotator at the edge $e$ for
$\Sigma$ by restricting it to the faces incident with the edge $e[B]$.

This rotation system is obviously planar at all vertices of $C[B]$ except for
the vertex $v$ and $v[B]$. We denote by $\Pi$ the rotation system induced by
$\Sigma$ of the link graph of $C$ at the vertex $v$. By the construction given
directly after Subsection 3.3.4, $\Pi$ induces a planar rotation system
$\Pi_{1}$ at the branch $B$, and $\Pi$ induces a planar rotation system
$\Pi_{2}$ at the minor of the link graph at $v$ in $C$ obtained by contracting
$B-e$ to a single vertex. It is immediate that the rotation system induced by
$\Sigma^{\prime}$ at $v[B]$ is $\Pi_{1}$, and the rotation system induced by
$\Sigma^{\prime}$ at $v$ is $\Pi_{2}$. Hence the rotation system
$\Sigma^{\prime}$ is planar for the simplicial complex $C[B]$.

By Section 1.1 contracting an edge preserves the existence of planar rotation
systems, and by Section 1.4 contracting a face of size two preserves the
existence of planar rotation systems. Hence by Section 3.5 if $C[B]$ has a
planar rotation system, then $C$ has a planar rotation system. ∎

The following is geometrically clear, see Figure 3.7, and we will not use it
in our proofs.

######  Lemma .

If $C$ embeds in 3-space, then also $C[B]$ embeds in 3-space. ∎

######  Remark .

Also the converse of Section 3.5 is true.

###  3.6 Increasing local connectivity

In the first three subsections of this section we define stretchings and prove
basic properties; these are necessary for Theorem 3.2.2. The forth subsection
is a preparation for the last subsection, in which we prove Theorem 3.2.2, and
Theorem 3.2.1.

####  3.6.1 The operation of stretching edges

Let $C$ be a 2-complex and let $e$ be an edge of $C$ incident with two faces
$f_{1}$ and $f_{2}$. Assume that there is an endvertex $v$ of the edge $e$
such that in any planar rotation system of the link graph $L(v)$ at $v$ the
edges $f_{1}$ and $f_{2}$ are adjacent in the rotator at $e$. The complex
$C^{\prime}$ obtained from $C$ by _pre-stretching the edge $e$ in the
direction of $f_{1}$ and $f_{2}$_ is obtained from $C$ as follows, see Figure
3.9. We replace the edge $e$ by two edges new edges $e_{1}$ and $e_{2}$, both
with the same endvertices as $e$. We add a face of size two only incident with
$e_{1}$ and $e_{2}$. The faces $f_{1}$ and $f_{2}$ are incident with $e_{1}$
instead of $e$, all other faces incident with $e$ in $C$ are incident with
$e_{2}$ instead. This completes the definition of pre-stretching an edge.
_Stretching_ an edge is defined the same way except that additionally we
subdivide the new face of size two to obtain a simplicial complex, see Figure
3.10.

Figure 3.9: The graph on the left defines a simplicial complex by adding faces
on all cycles of size three. We obtain the 2-complex on the right by pre-
stretching the edge $e$ in the direction of the faces $f_{1}$ and $f_{2}$. Its
faces are all triangles of the graph on the left except that the edge $e_{1}$
is only incident with the two faces $f_{1}$ and $f_{2}$ and the new face
$\\{e_{1},e_{2}\\}$ and the edge $e_{2}$ is only incident with the face
$f_{3}$ and the new face $\\{e_{1},e_{2}\\}$. Figure 3.10: Subdivision of a
face of size two to a simplicial complex.

######  Example .

The assumption for stretching an edge $e$ is particularly easy to verify if
the link graph $L(v)$ is 3-connected. Indeed, then by a theorem of Whitney, we
just need to check whether for a particular embedding of the link graph $L(v)$
the edges $f_{1}$ and $f_{2}$ are adjacent.

######  Remark .

The inverse operation of pre-stretching an edge $e$ to a face
$\\{e_{1},e_{2}\\}$ is contracting the face $\\{e_{1},e_{2}\\}$ to the edge
$e$ as defined in chapter 1.

######  Lemma .

Let $C^{\prime}$ be obtained from $C$ by pre-stretching an edge $e$. Then
$C^{\prime}$ has a planar rotation system if and only if $C$ has a planar
rotation system.

###### Proof.

Let $\Sigma$ be a planar rotation system of the 2-complex $C$. We denote the
two new edges of the 2-complex $C^{\prime}$ by $e_{1}$ and $e_{2}$. We obtain
a rotation system $\Sigma^{\prime}$ of the 2-complex $C^{\prime}$ from
$\Sigma$ by taking the same rotators at all edges of the 2-complex
$C^{\prime}$ except for $e_{1}$ and $e_{2}$. By assumption, the faces $f_{1}$
and $f_{2}$ along which we pre-stretch the edge $e$ are adjacent in the
rotator at the edge $e$. We define the new rotator at the edge $e_{1}$ to be
the rotator of the edge $e$ restricted to the adjacent faces $f_{1}$ and
$f_{2}$ and we add the new face $\\{e_{1},e_{2}\\}$ in place of the interval
formed by the deleted faces. Similarly, we define a rotator at the edge
$e_{2}$: we delete from the rotator at $e$ the faces $f_{1}$ and $f_{2}$ and
add the face $\\{e_{1},e_{2}\\}$ in the interval formed by the two deleted
faces. It remains to check that the rotation system $\Sigma^{\prime}$ is
planar. This is immediate at all vertices except for the two endvertices of
the edge $e$. For the two endvertices, note that pre-stretching the edge $e$
has the effect on the link graph as coadding777Recall that _addition_ is the
reverse operation of deletion of an edge, and _coaddition_ is the reverse
operation of contraction of an edge. an edge at the vertex $e$. As the edges
$f_{1}$ and $f_{2}$ of the link graphs are adjacent, the coaddition can be
done within the embeddings of the link graphs given by $\Sigma$.

By Section 1.4, contracting a face of size two preserves the existence of
planar rotation systems. Hence by Subsection 3.6.1 if $C^{\prime}$ has a
planar rotation system, then $C$ has a planar rotation system. ∎

The following is geometrically clear, see Figure 3.9, and we will not use it
in our proofs.

######  Lemma .

Let $C^{\prime}$ be obtained from $C$ by stretching an edge $e$. If $C$ embeds
in 3-space, then also $C^{\prime}$ embeds in 3-space. ∎

######  Remark .

Also the converse of Subsection 3.6.1 is true.

####  3.6.2 The operation of contracting edges

An edge $e$ in a 2-complex $C$ is _reversible_ if the 2-complex $C$ has a
planar rotation system if and only if the 2-complex $C/e$ has a planar
rotation system.

A _para-star_ is a graph obtained from a family of disjoint parallel graphs by
gluing them together at a single vertex.

######  Lemma .

Let $e$ be a non-loop edge with endvertices $v$ and $w$ of a 2-complex $C$
such that the link graphs $L(v)$ and $L(w)$ are para-stars and the vertex $e$
is a maximum degree vertex in both of them. Then the edge $e$ is reversible.

###### Proof.

By Section 1.1, it suffices to show how any planar rotation system $\Sigma$ on
the 2-complex $C/e$ induces a planar rotation system $\Sigma^{\prime}$ on the
2-complex $C$. Letting $\Sigma^{\prime}$ to be equal to $\Sigma$ at all edges
of $C$ not incident with $v$ or $w$, it suffices to show the following.

######  Claim .

Let $L(v)$ and $L(w)$ be para-stars and let the vertex $e$ have maximal degree
in both of them. Let $L(e)$ be the vertex sum of $L(v)$ and $L(w)$ along $e$.
For any planar rotation system $\Pi$ of the graph $L(e)$, there are planar
rotation systems of the graphs $L(v)$ and $L(w)$ that are reverse of one
another at the vertex $e$, and otherwise agree with the rotation system $\Pi$.

Proof of Claim. Throughout we assume in the graphs $L(v)$ and $L(w)$, the
vertex $e$ is adjacent to any other vertex. This easily implies the general
case by suppressing suitable degree two vertices as rotators at such vertices
are unique.

We prove this by induction on the number of branches of the graph $L(v)$. The
base case is that the graph $L(v)$ is a parallel graph. Then the graph $L(e)$
is isomorphic to the graph $L(w)$. So a planar rotation system on the graph
$L(e)$ induces a planar rotation system on the graph $L(w)$. There is a unique
planar rotation system on the graph $L(v)$ whose rotator at $e$ is reverse to
the rotator at $e$ in that planar rotation system of $L(w)$.

So we may assume that the graph $L(v)$ has at least two branches. We split
into two cases.

Case 1: the graph $L(e)$ is disconnected. We consider $L(e)$ as a bipartite
graph with the vertex set of $L(v)-e$ on the left and the vertex set of
$L(w)-e$ on the right. As every vertex of $L(e)$ is incident with an edge,
there are two vertices of $L(v)-e$ in different connected components of the
bipartite graph $L(e)$. Denote these two vertices by $y$ and $z$. We obtain
$L(v)^{\prime}$ from $L(v)$ by identifying the vertices $y$ and $z$ into a
single vertex. Denote that new vertex by $u$. We denote the vertex sum of
$L(v)^{\prime}$ and $L(w)$ along $e$ by $L(e)^{\prime}$. The graph
$L(e)^{\prime}$ is equal to the graph obtained from $L(e)$ by identifying the
vertices $y$ and $z$. Thus any planar rotation system of the graph $L(e)$
induces a planar rotation system of the graph $L(e)^{\prime}$ by sticking the
rotation systems at the vertices $y$ and $z$ together so that the rotator at
the new vertex $u$ contains the edges incident with the vertex $y$ or $z$,
respectively, as a subinterval. By induction such a rotation system induces
planar rotation systems at the graphs $L(v)^{\prime}$ and $L(w)$. This planar
rotation system at the graph $L(v)^{\prime}$ induces a rotation system on the
graph $L(v)$ by splitting the rotator at $u$ into the two subintervals for the
vertices $y$ and $z$. This induced rotation system is planar for $L(v)$ as the
rotators for $y$ and $z$ are subintervals of the rotator for $u$.

Case 2: not Case 1, so the graph $L(e)$ is connected. As above, we consider
$L(e)$ as a bipartite graph, and let a planar rotation system of the graph
$L(e)$ be given. Since the left side has at least two vertices, there is a
vertex on the right of the connected bipartite graph $L(e)$ that has two
neighbours on the left. Pick such a vertex $x$. We pick neighbours $y$ and $z$
of $x$ in $L(v)-e$ such that there are edges $e_{y}$ between $y$ and $x$ and
$e_{z}$ between $z$ and $x$ such that these two edges are incident in the
rotator at the vertex $x$. Let $L(v)^{\prime}$ be the graph obtained from
$L(v)$ by identifying the vertices $y$ and $z$ to a single vertex. Call that
new vertex $u$. We denote the vertex sum of $L(v)^{\prime}$ and $L(w)$ along
$e$ by $L(e)^{\prime}$. The graph $L(e)^{\prime}$ is equal to the graph
obtained from $L(e)$ by identifying the vertices $y$ and $z$. The chosen
planar rotation system of the graph $L(e)$ induces a rotation system for the
graph $L(e)^{\prime}$ by sticking the rotation systems at the vertices $y$ and
$z$ together so that the rotator at the new vertex $u$ contains the edges
incident with the vertex $y$ or $z$, respectively, as a subinterval. By the
choice of $y$ and $z$ this rotation system is planar. By induction this planar
rotation system on $L(e)^{\prime}$ induces planar rotation systems on the
graphs $L(v)^{\prime}$ and $L(w)$. This planar rotation system at the graph
$L(v)^{\prime}$ induces a rotation system on the graph $L(v)$ by splitting the
rotator at $u$ into the two subintervals for the vertices $y$ and $z$. This
induced rotation system is planar for $L(v)$ as the rotators for $y$ and $z$
are subintervals of the rotator for $u$. ! $\diamondsuit$ To summarise the
proof of Subsection 3.6.2, we define the planar rotation system
$\Sigma^{\prime}$ for the 2-complex $C$ as indicated above, and we choose the
rotators at the edges incident with the vertices $v$ or $w$ as induced in the
sense of Subsection 3.6.2 by the rotation system of the link graph $L(e)$ at
the vertex $e$ of the 2-complex $C/e$. ∎

####  3.6.3 The definition of stretching

We say that a simplicial complex $\tilde{C}$ is obtained from a simplicial
complex $C$ by _stretching_ , if it is obtained from $C$ by applying
successively operations of the following types:

  1. 1.

stretching local branches at connected link graphs;

  2. 2.

2-stretching at local 2-separators of 2-connected link graphs;

  3. 3.

stretching edges;

  4. 4.

contracting reversible edges that are not loops;

  5. 5.

splitting vertices.

We also call $\tilde{C}$ a _stretching_ of $C$.

######  Lemma .

Assume $C^{\prime}$ is a stretching of $C$. Then $C$ has a planar rotation
system if and only if $C^{\prime}$ has a planar rotation system.

###### Proof.

In the language introduced above we are to show that all five stretching
operations are equivalences for the property ‘existence of planar rotation
systems’. For the first operation it is proved in Section 3.5, for the second
it is proved in Section 3.4, and for the third it is proved in Subsection
3.6.1 for pre-stretchings of edges, and so the result for stretchings follows.
For the forth operation it is true by the definition of reversible. Splitting
vertices is clearly an equivalence for the existence of planar rotation
systems. ∎

####  3.6.4 Increasing the local connectivity a bit

A 2-complex is _locally almost 2-connected_ if all its link graphs are
2-connected or free graphs. The following is a key step towards Theorem 3.2.2.

######  Theorem 3.6.1.

Any simplicial complex $C$ has a stretching $C^{\prime}$ that is a simplicial
complex so that $C^{\prime}$ is locally almost 2-connected or $C^{\prime}$ has
a non-planar link graph.

Before we prove Theorem 3.6.1, we need some preparation. A _star of parallel
graphs_ is a graph that is not 2-connected and is obtained from a set of
disjoint parallel graphs by gluing them together at a single vertex.

######  Example .

The only parallel graphs that are stars of parallel graphs are paths. Stars of
parallel graphs are 2-connected para-stars.

######  Lemma .

Let $C$ be a simplicial complex that is locally connected. Then there is a
simplicial complex $\tilde{C}$ that is obtained from $C$ by stretching local
branches such that every link graph of $\tilde{C}$ is 2-connected or a star of
parallel graphs.

###### Proof.

We will prove this by induction. The base case is that every link graph is
2-connected or a star of parallel graphs. Next we consider the case that each
link graph has at most one cut-vertex. Let $v$ be a vertex of the simplicial
complex $C$ such that its link graph has a cut-vertex $e$. Then all branches
of $e$ are 2-connected graphs. We stretch all branches of $e$ that are not
parallel graphs, one after the other. Then the link at $v$ becomes a star of
parallel graphs and all other new link graphs are 2-connected. The old link
graphs, those at vertices of $C$ aside from $v$, do not change except possibly
for subdividing edges888The vertices $v^{\prime}$ of $C$ where those
subdivisions occur are those such that there is an edge $e^{\prime}$ between
$v$ and $v^{\prime}$ such that $e^{\prime}$ is a vertex of one of the branches
we stretch.. We apply this recursively to all link graphs with cut-vertices,
and so reduce this case to the base case.

Next suppose that there is a vertex $v$ such that its link graph has at least
two cut-vertices. Let $e_{1}$ be an arbitrary cut-vertex of that link graph.
Let $B$ be a branch of $e_{1}$ containing another cut-vertex $e_{2}$. Then we
stretch $B$. All link graphs at vertices of $C$ aside from $v$ are not changed
(except for possibly subdividing edges). The vertex $v$ is replaced by two new
vertices. Each cut-vertex of the link graph of $v$ is in precisely one of the
two new link graphs, and $e_{1}$ and $e_{2}$ are in different link graphs.
Hence both new link graphs have strictly less cut-vertices than the link graph
of $v$. Hence we can apply induction (on the sequence of numbers of cut-
vertices of link graphs, ordered by size and compared in lexicographical
order).

∎

###### Proof of Theorem 3.6.1..

The _cutvertex-degree_ of a simplicial complex $C$ is the maximal degree of a
cutvertex of a link graph of the simplicial complex $C$. We prove Theorem
3.6.1 by induction on the cutvertex-degree. So let $C$ be a simplicial complex
with cutvertex-degree $a$.

We obtain $C_{1}$ from $C$ by splitting all vertices whose link graphs are
disconnected. The simplicial complex $C_{1}$ is locally connected. By
Subsection 3.6.4 there is a stretching $C_{2}$ of the simplicial complex
$C_{1}$ such that all its link graphs are 2-connected or stars of parallel
graphs.

If the cutvertex-degree $a$ is at most three, then all link graphs of $C_{2}$
are 2-connected or stars of parallel graphs where the unique cut-vertex has
degree at most three. Graphs of the second type are always free, see Figure
3.2. This completes the proof if the cutvertex-degree is at most three, so
from now on let the cutvertex-degree $a$ be at least four.

We say that a simplicial complex $C$ is _$a$ -nice_ if all its link graphs are
2-connected, or stars of parallel graphs whose cutvertex has degree precisely
$a$ or else have maximum degree strictly less than $a$. For example the
simplicial complex $C_{2}$ is $a$-nice. We say that a simplicial complex $C$
is _$a$ -structured_ if all its link graphs are parallel graphs, or stars of
parallel graphs whose cutvertex has degree precisely $a$ or else have maximum
degree strictly less than $a$. For example, every $a$-structured simplicial
complex is $a$-nice.

######  Claim .

Assume $C_{2}$ is $a$-nice. There is a stretching $C_{3}$ of $C_{2}$ that is
$a$-structured or else has a non-planar link.

Proof of Claim. We prove this claim by induction on the degree-parameter as
defined in Section 3.4. So let $C_{2}$ be an $a$-nice simplicial complex such
that all $a$-nice simplicial complexes with strictly smaller degree-parameter
have a stretching that is $a$-structured or has a non-planar link.

We may assume that the simplicial complex $C_{2}$ is not $a$-structured; that
is, it has a vertex $v$ such that the link graph $L(v)$ is 2-connected but no
parallel graph and $L(v)$ has vertex $e$ of degree at least $a$. Also we may
assume that $L(v)$ is planar.

Case 1: the vertex $e$ is not contained in a proper 2-separator of $L(v)$.
Since embeddings of 2-connected graphs in the plane are unique up to flipping
at 2-separators by a theorem of Whitney, any embedding of the graph $L(v)$ in
the plane has the same rotator at the vertex $e$ (up to reversing). Take two
edges $f_{1}$ and $f_{2}$ incident with the vertex $e$ that are adjacent in
the rotator. Now we stretch the edge $e$ of $C_{2}$ in the direction of the
faces corresponding to $f_{1}$ and $f_{2}$. The link graphs at all vertices of
$C_{2}$ except for $v$ and the other endvertex $w$ of the edge $e$ of $C_{2}$
do not change. In the link graphs for $v$ and $w$ the vertex $e$ is replaced
by two new vertices (and a path of length two joining them), each of strictly
smaller degree than $e$, as its degree $a$ is at least four. This new
simplicial complex $C_{3}$ has strictly smaller degree-parameter than $C_{2}$.

In order to be able to apply induction, we need to show that $C_{3}$ is
$a$-nice. The link graph at $v$ is still 2-connected in $C_{3}$. If the link
graph at $w$ in $C_{2}$ is 2-connected, this is still true in $C_{3}$. Hence
it remains to consider the case that it is a star of parallel graphs. In this
case the vertex $e$ must be the cutvertex of $L(w)$ by the choice of $a$. Then
in the simplicial complex $C_{3}$, the link graph at $w$ has maximum degree
less than $a$. Thus $C_{3}$ is $a$-nice and we can apply the induction
hypothesis. So $C_{3}$ has a stretching of the desired type, and $C_{3}$ is a
stretching of $C_{2}$. This completes the induction step in this case.

Case 2: not Case 1. Then the vertex $e$ is contained in a proper 2-separator
of $L(v)$. Let $x$ be the other vertex in that 2-separator. We obtain $C_{3}$
from $C_{2}$ by stretching at the 2-separator $\\{e,x\\}$. The simplicial
complex $C_{3}$ has strictly smaller degree-sequence than $C_{2}$ by Section
3.4. We verify that $C_{3}$ is $a$-nice. All link graphs at new vertices are
still 2-connected in $C_{3}$. Let $w$ and $w^{\prime}$ be the endvertices of
the edges $e$ and $x$ aside from $v$, respectively. Hence it remains so show
that the link graphs at $w$ and $w^{\prime}$ in $C_{3}$ are 2-connected, stars
of parallel graphs whose cutvertex has degree $a$ or have maximal degree less
than $a$. If the link graph at $w$ in $C_{2}$ is 2-connected, it is also
2-connected in $C_{3}$ (as coadding a star preserves 2-connectedness). Hence
we may assume that the link graph at $w$ in $C_{2}$ is a star of parallel
graphs. and $e$ is its cutvertex by the choice of $a$. Then either $L(w)$ is
still a star of parallel graphs in $C_{3}$ or else it has maximum degree less
than $a$. The same analysis applies to the vertex ‘$w^{\prime}$’ in place of
‘$w$’. Thus $C_{3}$ is $a$-nice. So by induction there is a stretching of
$C_{3}$ of the desired type, and $C_{3}$ is a stretching of $C_{2}$. This
completes the induction step, and hence the proof of this claim. !
$\diamondsuit$

Let $C_{3}$ be stretching of the simplicial complex $C_{2}$ as in Subsection
3.6.4. If $C_{3}$ has a non-planar link, we are done. Hence we may assume that
the simplicial complex $C_{3}$ is $a$-structured. If $C_{3}$ has cutvertex-
degree less than $a$, we can apply the induction hypothesis. Hence we may
assume that $C_{3}$ has a vertex $v$ such that the link graph at $v$ is a star
of parallel graphs whose cutvertex $e$ has degree precisely $a$. Now we show
how the property ‘$a$-structured’ implies the existence of certain paths,
which can then be contracted to reduce the cutvertex-degree.

######  Claim .

There is a path $P_{n}$ from the vertex $v$ starting with $e$ to another
vertex $w_{n}$ whose link graph is a star of parallel graphs. All link graphs
at internal vertices of the path are parallel graphs and all edges of the path
have the same face-degree.

Proof of Claim. We build the path $P_{n}=w_{0}e_{1}w_{1}...e_{n}w_{n}$
recursively as follows. We start with $e_{1}=e$ and $w_{0}=v$ and let $w_{1}$
be the endvertex of the edge $e$ aside from $v$. Assume we already constructed
$w_{0}e_{1}w_{1}...e_{i}w_{i}$. If the link graph $L(w_{i})$ is a star of
parallel graphs we stop and let $i=n$ and $w_{i}=w_{n}$. Otherwise by
assumption, the link graph $L(w_{i})$ must be 2-connected. As the edge $e_{i}$
has degree precisely $a$ the link graph $L(w_{i})$ of the $a$-structured
simplicial complex $C_{3}$ is a parallel graph. So the link graph $L(w_{i})$
contains a unique vertex except from $e_{i}$ that has degree larger than two,
and this vertex has the same degree as the vertex $e_{i}$. We pick this vertex
for $e_{i+1}$. Note that $e_{i+1}$ is an edge of the simplicial complex $C$.
We let $w_{i+1}$ be the endvertex of $e_{i+1}$ different from $w_{i}$. Note
that all edges $e_{i}$ have the same face-degree by construction. Since any
path999A _path_ in a graph is a sequence alternating between vertices and
edges such that adjacent members are incident, and all vertices (and edges)
are distinct. in $C$ must be finite, it suffices to prove the following:

######  Fact .

For all $i$ the walk $P_{i}$ is a path.

###### Proof.

We prove this by induction on $i$. The base case is that $i=1$. Suppose for a
contradiction there is some $j<i$ such that $w_{i}=w_{j}$.

Case 1: $j=0$: then $e_{i}$ must be equal to the only vertex of $L(v)$ of the
same degree; that is, $e_{i}$ is equal to the edge $e_{1}$. But then the
endvertex $w_{i-1}$ of the edge $e_{i}$ is equal to the vertex $w_{1}$. This
is a contradiction to the induction hypothesis. Hence $w_{i}$ cannot be equal
to $w_{0}$.

Case 2: $j\geq 1$: as in the link graph $L(w_{j})$ the only two vertices with
the same degree as the vertex $e_{i}$ are $e_{j}$ and $e_{j+1}$, it must be
that the edge $e_{i}$ is equal to one of these two edges; that is, the
endvertex $w_{i-1}$ of $e_{i}$ must be equal to $w_{j-1}$ or $w_{j+1}$. The
vertex $w_{j-1}$ cannot be an option by the induction hypothesis. Similarly,
the vertex $w_{j+1}$ cannot be an option by the induction hypothesis if
$j+1<i-1$. So $j+2\geq i$, so $j=i-2$ or $j=i-1$. Since the simplicial complex
$C$ has no loops or parallel edges any three consecutive vertices on $P_{i}$,
such as $w_{i-2}$, $w_{i-1}$ and $w_{i}$, are distinct. Hence neither $j=i-2$
nor $j=i-1$ are possible. Thus we have also reached a contradiction in this
case. Hence the vertex $w_{i}$ is distinct from all previous vertices on the
walk $P_{i}$. ∎

! $\diamondsuit$

Given a path $P_{n}$ with endvertex $w_{n}$ as in Subsection 3.6.4, whose link
graph $L(w_{n})$ at $w_{n}$ is a star of parallel graphs, denote the (unique)
cut-vertex of the link graph $L(w_{n})$ by $x$.

######  Claim .

The cut-vertex $x$ is equal to the last edge $e_{n}$ on the path $P_{n}$.

Proof of Claim. We denote the degree of the cut-vertex $x$ by $a^{\prime}$. By
the definition of $a$, we have, $a^{\prime}\leq a$.

On the other hand by Subsection 3.6.4 the vertices $e$ and $e_{n}$ have the
same degree in the graphs $L(v)$ and $L(w_{n})$, and this degree is equal to
$a$ by the choice of the vertex $v$. As $L(w_{n})$ is a star of parallel
graphs with a cut-vertex, the degree of the cut-vertex $x$ is strictly larger
than the degree of any other vertex of $L(w_{n})$. Hence it must be that
$a=a^{\prime}$ and $x=e_{n}$. ! $\diamondsuit$

By Subsection 3.6.4 and Subsection 3.6.4, there is a set of vertex-disjoint
paths in $C_{3}$ such that any of their endvertices has a link graph that is a
star of parallel graphs whose cutvertex has degree $a$. All internal vertices
of these paths are parallel graphs. By taking this collection maximal, we
ensure that any vertex whose link graph is a star of parallel graphs whose
cutvertex has degree $a$ is an endvertex of one of these paths. We denote the
set of these paths by ${{\cal P}}$. We obtain the 2-complex $C_{4}$ from
$C_{3}$ by contracting all edges on these paths of ${{\cal P}}$. Contracting
the edges on the paths recursively, we note at each step that these edges are
reversible by Subsection 3.6.2. At all vertices of $C$ except for those
vertices on the paths, the two $2$-complexes $C_{3}$ and $C_{4}$ have the same
link graphs. In addition, $C_{4}$ has the contraction vertices, one for each
of the vertex-disjoint paths. These link graphs are the vertex-sum of the link
graphs at the vertices on its path, see Section 1.1 for background on vertex-
sums. So the link graph at a new contraction vertex is (isomorphic to) the
vertex sum of the link graphs at the two endvertices plus various subdivision
vertices coming from the parallel graphs at internal vertices of the path. By
Subsection 3.6.4, each of these vertices in the link graph has degree strictly
less than $a$. Hence all new contraction vertices have maximum degree less
than $a$. Hence the cutvertex-degree of $C_{4}$ is strictly smaller than $a$.
So the 2-complex $C_{4}$ satisfies all the conditions to apply the induction
hypothesis except that it may not be a simplicial complex as it may have edges
that are loops or parallel edges.

Now we show how we can stretch local branches of $C_{3}$ to get a simplicial
complex $C_{3}^{\prime}$ so that the simplicial complex $C_{4}^{\prime}$
obtained from $C_{3}^{\prime}$ by contracting all the paths in ${{\cal P}}$ is
a simplicial complex. We obtain $C_{3}^{\prime}$ from $C_{3}$ by stretching at
each endvertex of a path in ${{\cal P}}$ all the branches and at each interior
vertex of a path in ${{\cal P}}$ we stretch at the 2-separator consisting of
the two branching vertices of its parallel graph. We obtain $C_{4}^{\prime}$
from $C_{3}^{\prime}$ by contracting the above defined family of paths ${{\cal
P}}$. It is straightforward to check that $C_{4}^{\prime}$ is a simplicial
complex – and is a stretching of $C$ with smaller cutvertex-degree. This
completes the induction step, and hence this proof. ∎

####  3.6.5 Proofs of Theorem 3.2.1 and Theorem 3.2.2

We conclude this section by proving the following theorems mentioned in the
Introduction.

###### Proof of Theorem 3.2.2.

Let $C$ be a simplicial complex. Recall that Theorem 3.2.2 says there is a
simplicial complex $C^{\prime\prime\prime}$ obtained from $C$ by stretching so
that $C^{\prime\prime\prime}$ is locally almost 3-connected and stretched out
or $C^{\prime\prime\prime}$ has a non-planar link; moreover $C$ has a planar
rotation system if and only if $C^{\prime\prime\prime}$ has a planar rotation
system.

By Theorem 3.6.1 there is a stretching $C^{\prime}$ of $C$ that is a
simplicial complex that is locally almost 2-connected or has a non-planar
link. As we are done otherwise, we may assume that $C^{\prime}$ is locally
almost 2-connected. By Section 3.4 there is a stretching $C^{\prime\prime}$ of
$C^{\prime}$ that is a locally almost 3-connected simplicial complex.

######  Claim .

Let $C^{\prime\prime}$ be a locally almost 3-connected simplicial complex.
Then there is a stretching $C^{\prime\prime\prime}$ of $C^{\prime\prime}$ that
has additionally the property that it is stretched out.

Proof of Claim. We say that an edge of face-degree two is _stretched out_ if
it has one endvertex that is not a subdivision of a 3-connected graph or a
parallel graph whose branch vertices have degree at least three. Note that a
simplicial complex in which every edge of degree two is stretched out is
stretched out itself. We prove this claim by induction on the number of edges
of degree two that are not stretched out. So assume there is an edge $e$ that
is not stretched out. Let $v$ be one of its endvertices.

Case 1: the link graph at $v$ is a parallel graph whose two branch vertices
$x_{1}$ and $x_{2}$ have degree at least three. Then we stretch at the
2-separator $(x_{1},x_{2})$ at $v$. This gives a simplicial complex
$\tilde{C}$ that in addition to the vertex $v$ has also one new vertex for
every component of $L(v)-x_{1}-x_{2}$. The link graphs at these new vertices
are cycles. Hence every edge of degree two incident with these new vertices is
stretched out. Thus $\tilde{C}$ has strictly less edges of degree two that are
not stretched out.

Case 2: the link graph at $v$ is a subdivision of a 3-connected graph. Then
the vertex $e$ of $L(v)$ is contained in a subdivided edge. Let $P$ be the
path of that subdivided edge, and let $x_{1}$ and $x_{2}$ be its endvertices.
Then we stretch at the 2-separator $(x_{1},x_{2})$ at $v$. The rest of the
analysis is analogue to Case 1. This completes the proof of the claim. !
$\diamondsuit$

By Subsection 3.6.5 we may assume that $C$ has a stretching
$C^{\prime\prime\prime}$ that is a locally almost 3-connected and stretched
out simplicial complex. The ‘Moreover’-part follows from the fact that
$C^{\prime\prime\prime}$ is a stretching of $C$ as shown in Subsection 3.6.3.
This completes the proof. ∎

###### Proof of Theorem 3.2.1.

Let $C$ be a simplicial complex such that the first homology group
$H_{1}(C,{\mathbb{F}}_{p})$ is trivial for some prime $p$. By Theorem 2.2.2
$C$ embeds into $\mathbb{S}^{3}$ if and only if it is simply connected and has
a planar rotation system; so from now on assume that $C$ is simply connected.

Recall that Theorem 3.2.1 says that $C$ has an embedding in 3-space if and
only if $C$ has no stretching that has a space minor in ${{\cal Y}}\cup{{\cal
T}}$. By Theorem 2.2.1 $C$ is embeddable in 3-space if and only if it has a
planar rotation system.

By Theorem 3.2.2 there is a simplicial complex $C^{\prime}$ that is a
stretching of $C$. Moreover $C$ has a planar rotation system if and only if
$C^{\prime}$ has a planar rotation system. By that theorem either the
simplicial complex $C^{\prime}$ has a non-planar link or it is locally almost
3-connected and stretched out. In the first case, by Kuratowski’s theorem,
Subsection 1.3.1 and Section 1.4, the simplicial complex $C^{\prime}$ has a
minor in the finite list ${{\cal Y}}$ – so the theorem is true in this case.
In the second case by Theorem 3.3.1 $C^{\prime}$ has a planar rotation system
if and only if it has no space minor in ${{\cal Y}}\cup{{\cal T}}$. This
completes the proof. ∎

###  3.7 Algorithmic consequences

Our proofs give a quadratic algorithm that verifies whether a given
2-dimensional simplicial complex has a planar rotation system. This gives a
quadratic algorithm that checks whether a given 2-dimensional simplicial
complex has an embedding in a (compact) orientable 3-manifold by Section 2.5
(for the general, not necessarily orientable, case see Section 2.9). In
particular, for simply connected 2-complexes this gives a quadratic algorithm
that tests embeddability in 3-space by Perelman’s theorem. The algorithm has
several components. Next we explain them in reverse order and prove the
relevant lemmas afterwards. We say that a simplicial complex $D$ is
_equivalent_ to $C$ if $D$ has a planar rotation system if and only if $C$ has
one.

  1. 4.

The locally almost 3-connected and stretched out case. This subroutine checks
whether a locally almost 3-connected and stretched out simplicial complex
admits a planar rotation system. The corresponding fact in the paper is
Subsection 3.3.2. This clearly has a linear time algorithm.

  2. 3.

Reduction of the locally almost 3-connected case to the locally almost
3-connected and stretched out case. This subroutine takes as input a locally
almost 3-connected simplicial complex $D_{2}$ and the output is a simplicial
complex $D_{3}$ equivalent to $D_{2}$ with the property that it is locally
almost 3-connected and stretched out. The corresponding fact in the paper is
Subsection 3.6.5. This clearly has a linear time algorithm.

  3. 2.

Reduction of the locally almost 2-connected case to the locally almost
3-connected case. This subroutine takes as input a locally almost 2-connected
simplicial complex $D_{1}$ and the output is a simplicial complex $D_{2}$
equivalent to $D_{1}$ and that additionally is locally almost 3-connected. The
corresponding fact in the paper is Section 3.4.

To analyse the running time, we do this step slightly differently than in the
paper. First we compute a Tutte-decomposition101010A Tutte-decomposition is a
decomposition of a graph (or matroid) into its 3-connected components along
2-separators. In the special case of graphs it is also known as the _SPQR
tree_. at every 2-connected link graph. This tells us precisely how we can
stretch that vertex along 2-separators. Doing these stretchings at different
vertices may affect the link graphs at other vertices. Indeed, it may affect
other vertices in that we coadd stars at their link graphs. However, once a
link graph is a subdivision of a 3-connected graph, it will stay that. So the
vertices we may have to look at multiple times are vertices where the link
graphs are parallel graphs. But if we need to stretch there again, the maximum
degree goes down. Using Subsection 3.7.1 below, it is straightforward to show
that this step can be done in linear time.

  4. 1.

Reduction of the general case to the locally almost 2-connected case. This
subroutine takes as input a simplicial complex $C$ and obtains a witness that
$C$ has no planar rotation system or the output is a simplicial complex
$D_{1}$ equivalent to $C$ and that additionally is locally almost 2-connected.
The corresponding fact in the paper is Theorem 3.6.1.

This is done by recursion on the cutvertex-degree $a$. So let us analyse the
step from $a$ to $a-1$ in detail. The input is a simplicial complex $C$ and we
measure its size by $\sum(deg(e)-2)$, where the sum ranges over all edges $e$
of $C$ of degree at least three. We refer to that sum as the _degree
parameter_.111111 We remark that at edges of degree at most two the
compatibility conditions for planar rotation systems is always satisfied and
hence we do not need to take them into account in the definition of the degree
parameter. Here $deg(e)$ denotes the number of faces incident with $e$.

The stretching related to Subsection 3.6.4 can be done in linear time as
computing the block-cutvertex-tree of link graphs can be done in linear time.
For the part corresponding to Subsection 3.6.4 we compute the stretching via
Tutte-decompositions as in step 3 explained above, and then we check for
planarity for each 3-connected link graph. If it is planar, we remember a
planar rotation system and if we stretch later an edge incident with that
vertex at the other endvertex we check whether this stretching is compatible
with the chosen planar rotation system. This can be done in linear time. The
construction of the set ${{\cal P}}$ of paths can clearly be done in linear
time. Hence the whole recursion step from $a$ to $a-1$ just takes linear time.
The output is the simplicial complex $C_{4}^{\prime}$ from the last paragraph
of the proof of Theorem 3.6.1.

However, with the current argument, the degree parameter of $C_{4}^{\prime}$
might be larger than the degree parameter of the input $C$. Indeed, stretching
a local branch may increase the degree parameter. Hence here we explain how we
modify the construction of the simplicial complex $C_{4}^{\prime}$ so that the
degree parameter does not increase. First note that none of the stretching
operations except for stretching a branch increases the degree parameter,
compare Subsection 3.7.1. Recall the definition of $C_{3}^{\prime}$ from the
last paragraph of the proof of Theorem 3.6.1. We obtain $C^{\prime\prime}$
from $C_{3}^{\prime}$ by contracting all edges $e[B]$ of degree at least three
that were added by stretching a local branch, and contracting the resulting
faces of size two (this has the effect of reversing the stretching operations
at those edges $e[B]$); additionally we stretch so that no edge of degree two
has both endvertices on the same path – similarly as in the construction of
stretched out in Subsection 3.6.5 (this ensures that edges of degree two do
not make a problem later. This does not increase the degree parameter). It is
easy to see that $C^{\prime\prime}$ is a simplicial complex and that $C$ has a
planar rotation system if and only if $C^{\prime\prime}$ has one. Each path
$P\in{{\cal P}}$ of $C_{3}^{\prime}$ contracts onto a closed trail of
$C^{\prime\prime}$ (in fact this closed trail is a path or a cycle as edges
incident with interior vertices of $P$ but not on $P$ have degree two and are
not contracted when going from $C_{3}^{\prime\prime}$ to $C^{\prime\prime}$ by
definition). We obtain $C_{3}^{\prime\prime}$ from $C^{\prime\prime}$ by
stretching branches for each closed trail $P\in{{\cal P}}$ as follows. Recall
that the endvertices of the path $P$ are denoted by $v$ and $w$.

Case 1: in the simplicial complex $C^{\prime\prime}$ the trail $P$ has at
least one internal vertex. Denote the edge of $P$ incident with $v$ by $e_{1}$
and the edge of $P$ incident with $w$ by $e_{2}$. Then we stretch at the link
graphs of $v$ and $w$ all branches at $e_{1}$ and $e_{2}$, respectively.

Case 2: not Case 1. Note that $P$ must consist of at least one edge by
Subsection 3.6.4. And that edge is not a loop as $C^{\prime\prime}$ is a
simplicial complex. So $P$ consists of a single edge $e$. Then in the
simplicial complex $C^{\prime\prime}$ there is no edge in parallel to $e$. We
stretch all branches of the link graph at $v$ at the vertex $e$ (but not for
$w$).

We obtain $C_{4}^{\prime\prime}$ from $C_{3}^{\prime\prime}$ by contracting
all $P\in{{\cal P}}$. It is straightforward to check that
$C_{4}^{\prime\prime}$ is a simplicial complex and that the degree parameter
of $C_{4}^{\prime\prime}$ is at most that of $C$, compare Subsection 3.7.1. By
construction the cutvertex degree of $C_{4}^{\prime\prime}$ is strictly
smaller than that of $C$. So $C_{4}^{\prime\prime}$ is a suitable output of
the recursion step. As each recursion step takes linear time, all of them
together take at most quadratic time.

This completes the description of the steps of the algorithm. Together they
form the following algorithm. The input is a simplicial complex $C$ and we
want to check whether it has a planar rotation system. In step 1, we either
obtain a witness that $C$ has no planar rotation system or the output is a
simplicial complex $D_{1}$ equivalent to $C$ and that additionally is locally
almost 2-connected. In step 2, we take $D_{1}$ has input and the output is a
simplicial complex $D_{2}$ equivalent to $D_{1}$ and that additionally is
locally almost 3-connected. Step 3 works like step 2 but here the output has
the additional property that it is stretched out. Finally in step 4, we check
the existence of a planar rotation system for locally almost 3-connected and
stretched out simplicial complexes.

####  3.7.1 Some lemmas for the algorithm above

Here we prove the lemmas referred to in the beginning of Section 3.7.

The _degree-parameter_ of a graph $G$ is $\sum(deg(v)-2)$, where the sum
ranges over all vertices.

######  Lemma .

Coadding a star at a vertex $v$ preserves the degree parameter.

###### Proof.

Let $k$ be the degree of the center of the coadded star and $v_{1},..,v_{k}$
be the leaves of the coadded star. The degree parameter of the graph before
minus the degree parameter after the coaddition is:

$deg(v)-2-\left(\sum_{i=1}^{k}(deg(v_{i})-2)+(k-2)\right)$

As $deg(v)=\sum_{i=1}^{k}deg(v_{i})-k$ the above sum evaluates to zero,
completing the proof. ∎

######  Lemma .

All stretching operations except for possibly stretching a local branch do not
increase the degree parameter.

###### Proof.

This lemma is immediate for splitting vertices and contracting reversible non-
loops. If we stretch an edge, first note that pre-stretching does not change
the degree parameter as $deg(e)=deg(e_{1})+deg(e_{2})-2$ if $e$ is stretched
to $e_{1}$ and $e_{2}$. Then note that subdivisions of faces do not change the
degree parameter.

The fact that 2-stretching does not change the degree parameter is proved
similarly as Subsection 3.7.1. ∎

######  Lemma .

The complex $C_{4}^{\prime\prime}$ is a simplicial complex whose degree
parameter is not larger than that of $C$.

###### Proof.

As mentioned above $C^{\prime\prime}$ is a simplicial complex. By Subsection
3.7.1 the degree parameter of $C^{\prime\prime}$ is not larger than that of
$C$. Hence it suffices to show for each trail $P\in{{\cal P}}$ that the
construction given in the two cases plus the contraction afterwards preserves
being a simplicial complex and does not increase the degree parameter.

First we treat Case 1; that is, $P$ has an internal vertex. In the
construction of $C^{\prime\prime}$ we never contract an edge incident with an
internal vertex of $P$ that is not on the path $P$, as they all have face-
degree two. Hence $P$ is a path in $C^{\prime\prime}$ or a cycle. Then we
stretch all the branches at the local cutvertices $e_{1}$ and $e_{2}$ in the
link graphs at $v$ and $w$, respectively. The sum of degrees of the new edges
$e[B]$ is at most $deg(e_{1})+deg(e_{2})$. So the degree parameter increased
by at most $2deg(e_{1})-4$ (as $deg(e_{1})=deg(e_{2})$). Then we contract all
edges on $P$, and resulting faces of degree two. This decreases the degree
parameter at least by that amount, as $P$ contains at least two edges. Thus in
total the degree parameter does not increase. The stretching before the
contraction ensures that all edges incident with an interior vertex of $P$
have an endvertex whose link graph is a cycle and thus on none of the paths
from ${{\cal P}}$. So we do not create parallel edges or loops. So
$C_{4}^{\prime\prime}$ is a simplicial complex.

The analysis in Case 2 is similar. Here note that $P$ is a path of length one,
and so $v\neq w$. Thus one stretching suffices to ensure that
$C_{4}^{\prime\prime}$ is a simplicial complex. ∎

### Acknowledgement

I thank Radoslav Fulek for pointing out an error in an earlier version of this
paper. I thank Arnaud de Mesmay for useful discussions that led to Section 2.9
in the extended version of [7]. I thank Nathan Bowler and Reinhard Diestel for
useful discussions on this topic.

## Bibliography

  * [1] M.A. Armstrong.  Basic Topology.  Springer-Verlag, 1983.
  * [2] R. H. Bing.  An alternative proof that 3-manifolds can be triangulated.  Ann. Math.(2), 69:37–65, 1959.
  * [3] Robert E Bixby.  A simple theorem on 3-connectivity.  Linear Algebra and its Applications, 45:123–126, 1982.
  * [4] Ulrich Brehm.  A nonpolyhedral triangulated Möbius strip.  Proc. Amer. Math. Soc., 89(3):519–522, 1983.
  * [5] Johannes Carmesin.  Embedding simply connected 2-complexes in 3-space – I. A Kuratowski-type characterisation.  Preprint, arXiv:1709.04642v3”.
  * [6] Johannes Carmesin.  Embedding simply connected 2-complexes in 3-space – I. A Kuratowski-type characterisation.  Preprint 2017, available at ”https://arxiv.org/pdf/1709.04642.pdf”.
  * [7] Johannes Carmesin.  Embedding simply connected 2-complexes in 3-space – II. Rotation systems.  Preprint 2017, available at ”https://arxiv.org/pdf/1709.04643.pdf”.
  * [8] Johannes Carmesin.  Embedding simply connected 2-complexes in 3-space – IV. Dual matroids.  Preprint 2017, available at ”https://arxiv.org/pdf/1709.04652.pdf”.
  * [9] Johannes Carmesin and Lyuben Lichev.  New constructions related to the polynomial sphere recognition problem.  Discrete & Computational Geometry, 67(4):1097–1123, 2022.
  * [10] Arnaud de Mesmay, Yo’av Rieck, Eric Sedgwick, and Martin Tancer.  Embeddability in $\mathbb{R}^{3}$ is NP-hard.  Preprint 2017, available at: ”https://arxiv.org/pdf/1708.07734”.
  * [11] Reinhard Diestel.  Graph Theory _(5th edition)_.  Springer-Verlag, 2017.
Electronic edition available at:
http://diestel-graph-theory.com/index.html.

  * [12] Radoslav Fulek and Csaba D Tóth.  Atomic embeddability, clustered planarity, and thickenability.  ACM Journal of the ACM (JACM), 69(2):1–34, 2022.
  * [13] Jim Geelen, Bert Gerards, and Geoff Whittle.  Solving Rota’s conjecture.  Notices Amer. Math. Soc., 61(7):736–743, 2014.
  * [14] Agelos Georgakopoulos and Jaehoon Kim.  2-complexes with unique embeddings in 3-space.  Bulletin of the London Mathematical Society, 55(1):156–174, 2023\.
  * [15] Agelos Georgakopoulos and George Kontogeorgiou.  Discrete group actions on 3-manifolds and embeddable cayley complexes.  arXiv preprint arXiv:2208.09918, 2022.
  * [16] H. Hadwiger.  Über eine Klassifikation der Streckenkomplexe.  Vierteljschr. Naturforsch. Ges. Zürich, 88:133–142, 1943.
  * [17] Allen Hatcher.  Notes on basic 3-manifold topology.  available at ”http://www.math.cornell.edu/ hatcher/3M/3Mfds.pdf”.
  * [18] Allen Hatcher.  Algebraic Topology.  Cambridge Univ. Press, 2002.
  * [19] Michael Heusner and Raphael Zentner.  A new algorithm for 3-sphere recognition.  Preprint 2016, available at arXiv:1610.04092.
  * [20] S. V. Ivanov.  Recognizing the 3-sphere.  Illinois J. Math., 45(4):1073–1117, 2001.
  * [21] Kazimierz Kuratowski.  Sur le probleme des courbes gauches en topologie.  Fundamenta mathematicae, 15(1):271–283, 1930.
  * [22] László Lovász.  Graph minor theory.  Bull. Amer. Math. Soc. (N.S.), 43(1):75–86, 2006.
  * [23] Jiri Matousek, Eric Sedgwick, Martin Tancer, and Uli Wagner.  Embeddability in the 3-sphere is decidable.  In Computational geometry (SoCG’14), pages 78–84. ACM, New York, 2014.  Extended version available at ”https://arxiv.org/pdf/1402.0815”.
  * [24] Jiri Matousek, Martin Tancer, and Uli Wagner.  Hardness of embedding simplicial complexes in $\mathbb{R}^{d}$.  J. Eur. Math. Soc. (JEMS), 13(2):259–295, 2011.
  * [25] B. Mohar and C. Thomassen.  Graphs on Surfaces.  Johns Hopkins, 2001.
  * [26] Edwin E. Moise.  Affine structures in 3-manifolds. V. The triangulation theorem and Hauptvermutung.  Annals of Mathematics. Second Series, 56:96–114, 1952.  ISSN 0003-486X, JSTOR 1969769, MR 0048805.
  * [27] James Oxley.  Matroid Theory _(2nd edition)_.  Oxford University Press, 2011.
  * [28] C. Papakyriakopoulos.  A new proof for the invariance of the homology groups of a complex (in greek).  Bull. Soc. Math. Grece, 22:1–154, 1946.
  * [29] C. D. Papakyriakopoulos.  On Dehn’s Lemma and the Asphericity of Knots.  Ann. Math., 66:1–26, 1957.  doi:10.2307/1970113.
  * [30] G. Perelman.  The entropy formula for ricci flow and its geometric applications.  2002, available at ”https://arxiv.org/abs/math.DG/0211159”.
  * [31] G. Perelman.  Finite extinction time for the solutions to the ricci flow on certain three-manifolds.  2003, available at ”https://arxiv.org/abs/math.DG/0307245”.
  * [32] G. Perelman.  Ricci flow with surgery on three-manifolds.  2003, available at ”https://arxiv.org/abs/math.DG/0303109”.
  * [33] J. L. Ramírez Alfonsín.  Knots and links in spatial graphs: a survey.  Discrete Math., 302(1-3):225–242, 2005.
  * [34] Neil Robertson and Paul D Seymour.  Graph minors. XX. Wagner’s conjecture.  J. Combin. Theory Ser. B, 92(2):325–357, 2004.
  * [35] Saul Schleimer.  Sphere recognition lies in np.  Low-dimensional and symplectic topology, 82:183–213, 2011.
  * [36] A. B. Skopenkov.  Geometric proof of Neuwirth’s theorem on the construction of 3-manifolds from 2-demensional [2-dimensional] polyhedra.  Math Notes, 56(2):827–829, 1994.  DOI: 10.1007/BF02110742.
  * [37] Klaus Wagner.  Über eine Eigenschaft der ebenen Komplexe.  Mathematische Annalen, 114(1):570–590, 1937.
  * [38] Uli Wagner.  Minors, embeddability, and extremal problems for hypergraphs.  pages 569–607, 2013.
  * [39] H. Whitney.  2-Isomorphic Graphs.  Amer. J. Math., 55:245–254, 1933.
  * [40] Hassler Whitney.  Congruent graphs and the connectivity of graphs.  Hassler Whitney Collected Papers, pages 61–79, 1992.
  * [41] Raphael Zentner.  Integer homology 3-spheres admit irreducible representations in SL(2,C).  Duke Math. J., 167(9):1643–1712, 2018.