lemthm lem skolemthm skolem factthm fact sublemthm sublem claimthm claim
obsthm obs propthm prop corthm cor quethm que oquethm oque oprobthm oprob
conthm con dfnthm dfn remthm rem egthm eg exercisethm exercise

Embedding simply connected 2-complexes in 3-space

Johannes Carmesin

University of Birmingham

Abstract

[2em]2emFirstly, we characterise the embeddability of simply connected locally
3-connected 2-dimensional simplicial complexes in 3-space in a way analogous
to Kuratowski’s characterisation of graph planarity, by nine excluded minors.
This answers questions of Lovász, Pardon and U. Wagner.

The excluded minors are the cones over $K_{5}$ and $K_{3,3}$, five related
constructions, and the remaining two are obtained from triangulations of the
Möbius strip by attaching a disc at its central cycle.

Secondly, we extend the above theorem to all simply connected 2-dimensional
simplicial complexes.

### Introduction

In 1930, Kuratowski proved that a graph can be embedded in the plane if and
only if it has none of the two non-planar graphs $K_{5}$ or $K_{3,3}$ as a
minor111A _minor_ of a graph is obtained by deleting or contracting edges.
Kuratowski’s theorem is stated in terms of subdivisions but here we refer to
it in the modern version in terms of minors; both statements are trivially
equivalent. The perspective in terms of the minor operation is due to K.
Wagner, who used it to prove the equivalence between the 4 Colour Theorem and
Hadwiger’s Conjecture [16] for 4 colours; and thus founded graph minor theory
[37]. [21]. The main result of this paper may be regarded as a 3-dimensional
analogue of this theorem.

Kuratowski’s theorem gives a way how embeddings in the plane could be
understood through the minor relation. A far reaching extension of
Kuratowski’s theorem is the Robertson-Seymour theorem [34]. Any minor-closed
class of graphs is characterised by the list of minor-minimal graphs not in
the class. This theorem says that this list always must be finite. The methods
developed to prove this theorem are nowadays used in many results in the area
of structural graph theory [11] – and beyond; recently Geelen, Gerards and
Whittle extended the Robertson-Seymour theorem to representable matroids by
proving Rota’s conjecture [13]. Very roughly, the Robertson-Seymour structure
theorem establishes a correspondence between minor closed classes of graphs
and classes of graphs almost embeddable in 2-dimensional surfaces.

In his survey on the Graph Minor project of Robertson and Seymour [22], in
2006 Lovász asked whether there is a meaningful analogue of the minor relation
in three dimensions. Clearly, every graph can be embedded in 3-space222Indeed,
embed the vertices in general position and embed the edges as straight lines.
.

One approach towards this question is to restrict the embeddings in question,
and just consider so called linkless embeddings of graphs, see [33] for a
survey. Instead of restricting embeddings, one could also put some additional
structure on the graphs in question. Indeed, U. Wagner asked how an analogue
of the minor relation could be defined on general simplicial complexes [38].
All simplicial complexes considered in this paper are finite, for infinite
ones see [15].

Unlike in higher dimensions, a 2-dimensional simplicial complex has a
topological embedding in 3-space if and only if it has a piece-wise linear
embedding, which in turn holds if and only if it has a differential embedding
[2, 17, 26, 28]. Matoušek, Sedgewick, Tancer and U. Wagner[23] proved that the
embedding problem for 2-dimensional simplicial complexes in 3-space is
decidable. De Mesmay, Rieck, Sedgwick and Tancer complemented this result by
showing that this problem is NP-hard [10].

Our lack of understanding NP-hard problems may suggest that a structural
characterisation of embeddability of 2-dimensional simplicial complexes333All
graphs and simplicial complexes considered in this paper are finite. in
general is out of reach. But what about structural characterisations for
natural subclasses? In fact such questions have been asked: in 2011 at the
internet forum ‘MathsOverflow’ Pardon444John Pardon confirmed in private
communication that he asked that question as the user ‘John Pardon’. asked
whether there are necessary and sufficient conditions for when contractible
2-dimensional simplicial complexes embed in 3-space. The _link graph_ at a
vertex $v$ of a simplicial complex is the incidence graph between edges and
faces incident with $v$. Pardon notes that if embeddable the link graph at any
vertex must be planar. This leads to obstructions for embeddability such as
the cone over the complete graph $K_{5}$, see Figure 1. – But there are
different obstructions of a more global character, see Figure 2. All their
link graphs are planar – yet they are not embeddable.

Figure 1: The cone over $K_{5}$. Similarly as the graph $K_{5}$ does not embed
in 2-space, the cone over $K_{5}$ does not embed in 3-space.  Figure 2: The
octahedron obstruction, depicted on the right, is obtained from the octahedron
with its eight triangular faces by adding 3 more faces of size 4 orthogonal to
the three axis. If we add just one of these 4-faces to the octahedron, the
resulting 2-complex is embeddable as illustrated on the left. A second 4-face
could be added on the outside of that depicted embedding. However, it can be
shown that the octahedron with all three 4-faces is not embeddable.

Addressing these questions, we introduce an analogue of the minor relation for
2-complexes and we use it to prove a 3-dimensional analogue of Kuratowski’s
theorem characterising when simply connected 2-dimensional simplicial
complexes (topologically) embed in 3-space.

| delete | contract
---|---|---
edge |  |
face |  |
Figure 3: For each of the four corners of the above diagram we have one space
minor operation.

More precisely, a _space minor_ of a 2-complex is obtained by successively
deleting or contracting edges or faces, and splitting vertices. See Figure 3
and Figure 4. The precise details of these definitions are given in Section
1.4; for example contraction of edges is only allowed for edges that are not
loops555 _Loops_ are edges that have only a single endvertex. While
contraction of edges that are not loops clearly preserves embeddability in
3-space, for loops this is not always the case. and we only contract faces of
size at most two.

Figure 4: The complex on the right is a space minor of the complex on the
left. To see this, delete the faces labelled $a$ and $b$, contract the edge
$e$, contract the face $f$, delete the edge $g$ and split the vertex $v$. Here
deleting an edge $g$ means that we replace $g$ by a copy for every incident
face, where the copy is only incident with a single face where it takes the
role of $g$.

It will be quite easy to see that space minors preserve embeddability in
3-space and that this relation is well-founded. The operations of face
deletion and face contraction correspond to the minor operations in the dual
matroids of simplicial complexes in the sense of [8].

######  Example .

Using space minors, we can understand why the Octahedron Obstruction (Figure
2) does not embed in 3-space. Indeed, we contract an arbitrary face of size
three to a single vertex (formally, we first contract an edge of that face,
then it gets size two. So we can contract it to an edge. Then we contract that
edge to a vertex). It turns out that the link graph at the new vertex is the
non-planar graph $K_{3,3}$. Thus this space minor is not embeddable in
3-space. As space minors preserve embeddability, we deduce that the Octahedron
Obstruction cannot be embeddable.

A construction of a simply connected 2-complex that is not embeddable in
3-space and has no space minor with a non-planar link graph can be obtained
from the Möbius strip by attaching a disc at its central cycle, see Figure 5.
We refer to these constructions as _Möbius obstructions_.

Figure 5: The Möbius-strip. Its central cycle is depicted in grey.

The main result of chapter 1 is the following. A _space restriction_ is a
space minor where we abstain from contracting edges or faces.

######  Theorem 1.

Let $C$ be a simply connected locally 3-connected 2-dimensional simplicial
complex. The following are equivalent.

  * •

$C$ embeds in 3-space;

  * •

$C$ has no space restriction from an explicit list ${{\cal Z}}$.

The list ${{\cal Z}}$ consists of cones over subdivisions of $K_{5}$ and
$K_{3,3}$, five similar constructions to which we refer to as ‘combined
cones’, see Subsection 1.3.2 below for details, and Möbius obstructions. The
set of space-minor minimal elements of ${{\cal Z}}$ consists of the cones over
$K_{5}$ and $K_{3,3}$ and a finite set of five combined cones constructions
and the finite set of minimal Möbius obstructions. In particular, this set of
space-minor minimal elements of ${{\cal Z}}$ is finite.

Here a (2-dimensional) simplicial complex is _locally 3-connected_ if all its
link graphs are 3-connected. In chapter 3, we extend Theorem 1 to simplicial
complexes that need not be locally 3-connected.

We are able to extend Theorem 1 from simply connected simplicial complexes to
those with trivial first homology group.

######  Theorem 2.

Let $C$ be a locally 3-connected 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$ embeds in 3-space;

  * •

$C$ is simply connected and has no space restriction from the explicit list
${{\cal Z}}$.

In general there are infinitely many obstructions to embeddability in 3-space.
Indeed, the following infinite family consists of obstructions of trivial
homology group that are not simply connected, and so these obstructions
directly connect to Theorem 2.

######  Example .

Given a natural number $q\geq 2$, the $q$-folded cross cap consists of a
single vertex, a single edge that is a loop and a single face traversing the
edge $q$-times in the same direction. It can be shown that $q$-folded cross
caps cannot be embedded in 3-space.

A more sophisticated infinite family of obstructions to embeddability is
constructed in [8]. Examples of follow-up works of this paper include: [14],
[15], [12], [9].

Overview over this paper. This paper is subdivided into three chapters. The
proof of Theorem 2 (which implies Theorem 1) spans chapter 1 and chapter 2.
chapter 2 is self-contained and deals with the topological aspects of this
paper.

The main result of chapter 3 is an extension of Theorem 2 dropping the
assumption of local 3-connectivity. This result can be combined with the
machinery from [8] to extend Theorem 2 beyond 2-complexes with trivial
homology group. Examples demonstrating that these results cannot be extended
much further can be found in [8].

###### Contents

  1. 1 The combinatorial part of the proof of Theorem 2
    1. 1.1 Vertex sums
    2. 1.2 Obstructions to the existence of planar rotation systems
    3. 1.3 Space restrictions
      1. 1.3.1 Cones
      2. 1.3.2 Combined cones
      3. 1.3.3 Möbius obstructions
      4. 1.3.4 Proof of Theorem 2 assuming Theorem 1.0.1
    4. 1.4 Space minors
    5. 1.5 Concluding remarks
  2. 2 The topological part of the proof of Theorem 2
    1. 2.1 Abstract
    2. 2.2 Introduction
    3. 2.3 Basic definitions
    4. 2.4 Rotation systems
    5. 2.5 Constructing piece-wise linear embeddings
    6. 2.6 Cut vertices
    7. 2.7 Local surfaces of planar rotation systems
    8. 2.8 Embedding general simplicial complexes
    9. 2.9 Non-orientable 3-manifolds
  3. 3 A refined Kuratowski-type characterisation
    1. 3.1 Abstract
    2. 3.2 Introduction
    3. 3.3 A Kuratowski theorem for locally almost 3-connected simply connected simplicial complexes
      1. 3.3.1 Torus crossing obstructions
      2. 3.3.2 Statement of Theorem 3.3.1
      3. 3.3.3 Proof of Subsection 3.3.2
      4. 3.3.4 Helicopter minors
      5. 3.3.5 Proof of Theorem 3.3.1
    4. 3.4 Stretching local 2-separators
    5. 3.5 Stretching a local branch
    6. 3.6 Increasing local connectivity
      1. 3.6.1 The operation of stretching edges
      2. 3.6.2 The operation of contracting edges
      3. 3.6.3 The definition of stretching
      4. 3.6.4 Increasing the local connectivity a bit
      5. 3.6.5 Proofs of Theorem 3.2.1 and Theorem 3.2.2
    7. 3.7 Algorithmic consequences
      1. 3.7.1 Some lemmas for the algorithm above

##  Chapter 1 The combinatorial part of the proof of Theorem 2

The proof of Theorem 2 (which implies Theorem 1) is subdivided into a
topological and combinatorial part. The connection between these parts is the
notion of ‘planar rotation systems’; roughly speaking, this is some
combinatorial data on a 2-complex. In the topological part we show that the
existence of planar rotation systems is equivalent to the existence of an
embedding; this is the topic of chapter 2. In chapter 1, we characterise
combinatorially which 2-complexes admit planar rotation systems. This is done
in several steps. In Section 1.1 we make a first step towards an excluded
minors characterisations by studying how planar rotation systems behave with
respect to contractions of edges. In Section 1.2 we use this to find in every
simply connected 2-complex without a planar rotation system an obstruction to
embeddability localised at a vertex, an edge or a face. In Section 1.3, we use
this to prove Theorem 2 – assuming a single lemma, Theorem 2.2.2, from chapter
2. In Section 1.4 we introduce space minors and prove that the list ${{\cal
Z}}$ of Theorem 2 has nine minimal elements and determine them. Concluding
remarks follow in Section 1.5.

For graphs111In this chapter graphs are allowed to have loops and parallel
edges.  we follow the notation of [11]. To read this chapter, a minimal amount
of topological background is necessary, which we summarise now.

A _2-complex_ is a graph $(V,E)$ together with a set $F$ of closed trails222A
_trail_ is sequence $(e_{i}|i\leq n)$ of distinct edges such that the
endvertex of $e_{i}$ is the starting vertex of $e_{i+1}$ for all $i<n$. A
trail is _closed_ if the starting vertex of $e_{1}$ is equal to the endvertex
of $e_{n}$., called its _faces_. We denote 2-complexes $C$ by triples
$C=(V,E,F)$. The definition of _link graphs_ naturally extends from simplicial
complexes to 2-complexes with the following modification: we add two vertices
in the link graph $L(v)$ for each loop incident with $v$. We add one edge to
$L(v)$ for each traversal of a face at $v$. In this paper we suppress from our
notation an injection from the vertices and edges of the link graph to $E$ and
$F$, respectively; and simply consider the vertices of the link graph as edges
of $C$, for instance. Throughout this paper, we denote faces of a 2-complex by
$f$, edges by $e$ and vertices by $v$. Thus we denote vertices of link graphs
by $e$ and edges of link graphs by $f$ (with the understanding that they come
from edges or faces of a 2-complex, respectively).

Rotation systems of 2-complexes play a central role in our proof of Theorem 1.
In this section we introduce them and prove some basic properties of them. A
rotation system of a graph $G$ is a family $(\sigma_{v}|v\in V(G))$ of cyclic
orientations333A _cyclic orientation_ is a bijection to an oriented cycle.
This notion is closely related to that of a ‘cyclic ordering’, which is a
bijection to a cycle (which does not come with an orientation). We stress that
in our notation it will be important to remember this orientation.
$\sigma_{v}$ of the edges incident with the vertices $v$ [25]. The
orientations $\sigma_{v}$ are called _rotators_. Whenever a graph $G$ is
embedded in an oriented (2-dimensional) surface, the cyclic orientation in
which the edges incident with a vertex $v$ appear around it (with respect to
the orientation of the surface) is a rotator at $v$. Conversely, any rotation
system of a graph $G$ induces an embedding of $G$ in an oriented surface $S$.
To be precise, we obtain $S$ from $G$ by gluing faces onto (the geometric
realisation of) $G$ along closed walks of $G$ as follows. Each directed edge
of $G$ is in one of these walks. Here the direction $\vec{a}$ is directly
before the direction $\vec{b}$ in a face $f$ if the endvertex $v$ of $\vec{a}$
is equal to the starting vertex of $\vec{b}$ and $b$ is just after $a$ in the
rotator at $v$. The rotation system is _planar_ if that surface $S$ is a
disjoint union of 2-spheres. Note that if the graph $G$ is connected, then for
any rotation system of $G$, also the surface $S$ is connected.

A _rotation system of a (directed 444A _directed_ 2-complex is a 2-complex
together with a choice of direction at each of its edges and a choice of one
of the two orientations of each of the closed trails corresponding to the
faces. All 2-complexes considered in this paper are directed. In order to
simplify notation we will not always say that explicitly. ) 2-complex_ $C$ is
a family $(\sigma_{e}|e\in E(C))$ of cyclic orientations $\sigma_{e}$ of the
faces incident555Recall that a face of a 2-complex traverses each edge at most
one by definition. with each edge $e$. A rotation system of a 2-complex $C$
_induces_ a rotation system at each of its link graphs $L(v)$ by restricting
to the edges that are vertices of the link graph $L(v)$; here we take
$\sigma(e)$ if $e$ is directed towards $v$ and the reverse of $\sigma(e)$
otherwise. Here we follow the convention that a loop $e$ at a vertex $v$ is
oriented from one attachment at $v$ to the other and hence its rotator
projects to $\sigma(e)$ in $L(v)$ at the copy of $e$ corresponding to the
attachment it is directed towards and the reverse of $\sigma(e)$ at the other
copy.

A rotation system of a 2-complex is _planar_ if the induced rotation system on
each link graph is planar.

######  Example .

Like embeddings of graphs in oriented surfaces induce rotation systems,
embeddings of 2-complexes $C$ in oriented 3-manifolds induce planar rotation
systems of $C$. Indeed, the cyclic orderings in which the faces appear around
each edge $e$ (with respect to the orientation) form a rotator, and planarity
follows from the fact that vertices of the 2-complex are embedded to points of
a 3-manifold.

In chapter 2 we prove the following, which we use in the proof of Theorem 1.

######  Theorem 1.0.1.

[Theorem 2.2.1] A simply connected simplicial complex has an embedding in
$\operatorname{\mathbb{S}}^{3}$ if and only if it has a planar rotation
system.

###  1.1 Vertex sums

In this short section we prove some elementary facts about an operation we
call ‘vertex sum’ which is used in the proof of Theorem 1.

Let $H_{1}$ and $H_{2}$ be two graphs with a common vertex $v$ and a bijection
$\psi$ between the edges incident with $v$ in $H_{1}$ and $H_{2}$. The _vertex
sum_ of $H_{1}$ and $H_{2}$ over $v$ with respect to $\psi$ is the graph
obtained from the disjoint union of $H_{1}$ and $H_{2}$ by deleting $v$ in
both $H_{i}$ and adding an edge between any pair $(v_{1},v_{2})$ of vertices
$v_{1}\in V(H_{1})$ and $v_{2}\in V(H_{2})$ such that $v_{1}v$ and $v_{2}v$
are mapped to one another by $\psi$, see Figure 1.1.

Figure 1.1: The vertex sum of the two graphs on the left is the graph on the
right.

Let $C=(V,E,F)$ be a 2-complex and let $e$ be a non-loop edge of $C$, the
2-complex obtained from $C$ by _contracting $e$_ (denoted by $C/e$) is
obtained from $C$ by identifying the two endvertices of $e$, removing $e$ from
all faces and then removing $e$, formally: $C/e=((V,E)/e,\\{f-e|f\in F\\})$.

######  Observation .

The link graph of $C/e$ at $e$ is the vertex sum of the link graphs $L(v)$ and
$L(w)$ over the common vertex $e$.

###### Proof.

For $\psi$ take the following bijection: given a face $f$ traversing $e$, this
traversal corresponds to a unique edge in $L(v)$ and $L(w)$, and these two
edges are in bijection via $\psi$. ∎

######  Lemma .

Let $G$ be a graph that is a vertex sum of two graphs $H_{1}$ and $H_{2}$ over
the common vertex $v$. Let $(\sigma_{x}^{i}|x\in V(H_{i}))$ be a planar
rotation system of $H_{i}$ for $i=1,2$ such that $\sigma_{v}^{1}$ is the
reverse of $\sigma_{v}^{2}$. Then $(\sigma_{x}^{i}|x\in V(H_{i})-v,i=1,2)$ is
a planar rotation system of $G$.

###### Proof sketch..

This is a consequence of the topological fact that the connected sum of two
spheres is the sphere. ∎

######  Lemma .

Let $G$ be a graph that is a vertex sum of two graphs $H_{1}$ and $H_{2}$ over
the common vertex $v$. Assume that the vertex $v$ is not a cutvertex of
$H_{1}$ or $H_{2}$. Assume that $G$ has a planar rotation system $\Sigma$.
Then there are planar rotation systems of $H_{1}$ and $H_{2}$ that agree with
$\Sigma$ at the vertices in $V(G)\cap V(H_{i})$ and that are reverse at $v$.

###### Proof.

Since the vertex $v$ is not a cutvertex of the graph $H_{2}$, the graph
$H_{1}$ can be obtained from the graph $G$ by contracting the connected vertex
set $V(H_{2})-v$ onto a single vertex. Now let a plane embedding $\iota$ of
$G$ be given that is induced by the rotation system $\Sigma$. Since
contractions can be performed within the plane embedding $\iota$, there is a
planar rotation system $\Sigma_{1}$ of the graph $H_{1}$ that agrees with
$\Sigma$ at all vertices in $V(H_{1})-v$.

Since the vertex $v$ is not a cutvertex of $H_{1}$ or $H_{2}$, the cut $X$ of
$G$ consisting of the edges between $V(H_{1})-v$ and $V(H_{2})-v$ is actually
a bond666Given a bipartition of the vertex set of a graph, its _cut_ is the
set of edges between these two biparition classes. A _bond_ is a minimal
nonempty cut. It is easy to see that a cut is a bond if and only if both its
paritition classes are connected vertex sets. of the graph $G$. The bond $X$
is a circuit $o$ of the dual graph of $G$ with respect to the embedding
$\iota$; and the rotator at $v$ of the planar rotation system $\Sigma_{1}$ is
equal (up to reversing) to the cyclic orientation of the edges on the circuit
$o$. Similarly, we construct a planar rotation system $\Sigma_{2}$ of $H_{2}$
that agrees with $\Sigma$ at all vertices in $V(H_{2})-v$, and the rotator at
the vertex $v$ is the other orientation of the circuit $o$. This completes the
proof. ∎

Let $C$ be a 2-complex and $e$ be a non-loop edge of $C$, and
$\Sigma=(\sigma_{x}|x\in E(C))$ be a rotation system of $C$. The _induced_
rotation system of $C/e$ is $\Sigma_{e}=(\sigma_{x}|x\in E(C)-x)$. This is
well-defined as the incidence relation between edges of $C/e$ and faces is the
same as in $C$. Planarity of rotation systems is preserved under contractions:

######  Lemma .

Let $e$ be a nonloop edge. If a rotation system $\Sigma$ is planar, then its
induced rotation system $\Sigma_{e}$ is planar.

Conversely, for any planar rotation system $\Sigma^{\prime}$ of $C/e$ so that
$e$ is not a cutvertex of any of the two link graphs at its endvertices in
$C$, there is a planar rotation system of $C$ inducing $\Sigma^{\prime}$.

###### Proof.

If a rotation system $\Sigma$ is planar, then by Section 1.1 and Section 1.1
its induced rotation system $\Sigma_{e}$ is planar. Conversely, for any planar
rotation system $\Sigma^{\prime}$ of $C/e$ so that $e=vw$ is not a cutvertex
of any of the two link graphs at its endvertices in $C$, by Section 1.1
applied to the planar rotation system $\Sigma^{\prime}$ induces on the link
graph $L(e)$ in $C/e$, there are planar rotation systems on the link graphs
$L(v)$ and $L(w)$ that are compatible along the edge $e$ and equal to
$\Sigma^{\prime}$ at other edges, and so $\Sigma^{\prime}$ together with the
rotator at $e$ obtained from Section 1.1 defines a planar rotation system of
$C$ inducing $\Sigma^{\prime}$. ∎

######  Lemma .

Let $G$ be a graph that is a vertex sum of two graphs $H_{1}$ and $H_{2}$ over
the common vertex $v$. Let $k\geq 2$. If $H_{1}$ and $H_{2}$ are
$k$-connected777Given $k\geq 2$, a graph with at least $k+1$ vertices is _$k$
-connected_ if the removal of less than $k$ vertices does not make it
disconnected. Moreover it is not allowed to have loops and if $k>2$, then it
is not allowed to have parallel edges. Whilst $K_{2}$ is not 2-connected,
every graph with two vertices, no loops and at least two parallel edges is
2-connected, all other graphs on less than $k+1$ vertices are not
$k$-connected for every $k$., then so is $G$.

###### Proof.

Let $Y$ be the set of edges incident with $v$ (suppressing the bijection
between the edges incident with $v$ in $H_{1}$ and $H_{2}$ in our notation).
We shall also consider $Y$ as an edge set of $G$.

######  Claim .

If $Y$ does not contain a matching of size $k$, then $G$ is $k$-connected.

Proof of Claim. As $H_{1}$ is $k$-connected, the set $Y$ contains at least $k$
edges. If $k>2$, then since no $H_{i}$ has parallel edges, in the graph $G$ no
two edges in $Y$ share a vertex. So we may assume that $k=2$. If in $G$ the
set $Y$ does not contain a matching of size two, there is a vertex $x$
covering $Y$. By symmetry assume $x\in V(H_{1})$. Then all edges of $Y$ are in
parallel between the vertices $x$ and $v$. Since $x$ is not a cutvertex of
$H_{1}$, the graph $H_{1}$ can only have the vertices $x$ and $v$. So
$G=H_{2}$ by the definition of vertex-sum. So $G$ is 2-connected. !
$\diamondsuit$

By Section 1.1, assume that $Y$ contains a set $Y^{\prime}$ of $k$ edges that
form a matching in the graph $G$. Suppose for a contradiction that there is a
set of less than $k$ vertices of $G$ such that $G\setminus X$ is disconnected.
Hence by the pigeonhole principle, there is an edge $e$ in $Y^{\prime}$ such
that no endvertex of $e$ is in $X$. Let $C$ be the component of $G\setminus X$
that contains $e$. Let $C^{\prime}$ be a different component of $G\setminus
X$. Let $i$ be such that $H_{i}$ contains a vertex $w$ of $C^{\prime}$.

In $H_{i}$ this vertex $w$ and an endvertex of $e$ are separated by $X+v$. As
$H_{i}$ is $k$-connected, we deduce that all vertices of $X$ are in $H_{i}$.
Then the connected graph $H_{i+1}$ is a subset of $C$. Hence the vertex $w$
and an endvertex of $e$ are separated by $X$ in $H_{i}$. This is a
contradiction to the assumption that $H_{i}$ is $k$-connected. ∎

###  1.2 Obstructions to the existence of planar rotation systems

In this section we prove Section 1.2 below, which is used in the proof of
Theorem 1. Intuitively, this lemma characterises simply connected locally
3-connected 2-complexes admitting planar rotation systems in terms of three
obstruction; these obstructions to the existence of a planar rotation system
are firstly a non-planar link graph, secondly an edge $e$ such that after
contraction of $e$ the link graph at the contraction vertex is non-planar, and
finally an obstruction spread around the boundary of a face, roughly speaking.
We start with some preparation. Recall that 3-connected graphs have no
parallel edges.

######  Lemma .

Let $C$ be a 2-complex with an edge $e$ with endvertices $v$ and $w$. Assume
that the link graphs $L(v)$ and $L(w)$ are 3-connected and that the link graph
$L(e)$ of $C/e$ at $e$ is planar. Then for any two planar rotation systems of
$L(v)$ and $L(w)$ the rotators at $e$ are reverse of one another or agree.

###### Proof.

Let $\Sigma=(\sigma_{x}|x\in(L(v)\cup L(w))-e)$ be a planar rotation system of
$L(e)$. By Section 1.1 there is a rotator $\tau_{e}$ at $e$ such that
$(\sigma_{x}|x\in L(v)-e)$ together with $\tau_{e}$ is a planar rotation
system of $L(v)$ and $(\sigma_{x}|x\in L(w)-e)$ together with the reverse of
$\tau_{e}$ is a planar rotation system of $L(w)$.

Recall that Whitney proved that a 3-connected planar graph admits a planar
rotation system that is unique up to reversing all rotators [40, 39]. Since
$L(v)$ and $L(w)$ are 3-connected, their planar rotation system are unique up
to reversing and hence the lemma follows. ∎

A _rotation framework_ of a 2-complex $C$ is a choice of planar rotation
system at each link graph of $C$ such that for every edge $e=vw$ the two
rotators at $e$, considered as a vertex in the link graphs $L(v)$ and $L(w)$,
are the same or reverse of one another. Given a 2-complex $C$ with a rotation
framework. We colour an edge $e$ of $C$ _green_ (with respect to a rotation
framework) if the two rotators at $e$ are reverse; otherwise we colour it
_red_.

######  Example .

Edges incident with just two faces are always coloured green.

A rotation framework of a 2-complex $C$ is _even_ if on every cycle of $C$ the
number of red edges is even; otherwise it is _odd_.

######  Lemma .

Assume that every edge is incident with at least three faces. A 2-complex
admits a planar rotation system if and only if it admits an even rotation
framework.

###### Proof.

Given a planar rotation system of $C$, the planar rotation systems it induces
at the link graphs of $C$ form a rotation framework. All edges of $C$ are
coloured green, so this rotation framework is even.

Conversely, let an even rotation framework of $C$ be given. Reversing the
planar rotation system at a single vertex $v$ yields a rotation framework
where the colours at all edges incident with $v$ swap – since all vertices of
$L(v)$ have degree at least three by assumption. So this new rotation
framework inherits the property that it is even. We refer to this operation as
a _flip_. Now assume that $C$ is connected and pick a rooted spanning tree $T$
of (the 1-skeleton of) $C$. Each vertex of $T$ aside from the root has a
unique edge to it from the direction of the root. Starting at the neighbours
of the root, we recursively do flips if necessary to ensure that the unique
path in $T$ from the root to any vertex contains only green edges. So $C$ has
an even rotation framework so that all edges of $T$ are green. Each edge
outside $T$ forms a fundamental circuit with edges of $T$, and by evenness
also must be green. So $C$ has a rotation framework where all edges are green.
This defines a planar rotation system as follows: for every directed edge
$\vec{e}$ of $C$ directed to $v$, denote by $\sigma_{e}$ the rotator in $L(v)$
at the vertex $e$. Now $(\sigma_{e}|e\in E(C))$ is a planar rotation system. ∎

######  Lemma .

A locally 3-connected 2-complex that does not admit a planar rotation system
has a vertex $v$ such that its link graph $L(v)$ is non-planar, has an edge
$e$ such that in $C/e$ the link graph $L(e)$ at the contraction vertex $e$ is
non-planar or $C$ admits a rotation framework so that there is a cycle
containing an odd number of red edges.

###### Proof.

Assume that all link graphs of $C$ at vertices are planar and that also for
every edge $e$ the link graphs $L(e)$ are planar. So for each vertex $v$ of
$C$ we can pick a planar rotation system of the link graph $L(v)$. By Section
1.2, this defines a rotation framework. Since $C$ does not have a planar
rotation system, by Section 1.2 this rotation framework must be odd. ∎

######  Remark .

If a 2-complex satisfies one of the three outcomes of Section 1.2, then it
does not admit a planar rotation system. So Section 1.2 is a characterisation
of 2-complexes admitting planar rotation systems. We will not use this remark
in our proofs.

The next lemma is like Section 1.2 under the additional assumption of simply
connectedness and this makes us find the cycle with an odd number of red edges
as a face boundary.

######  Lemma .

A simply connected locally 3-connected 2-complex that does not admit a planar
rotation system has a vertex $v$ such that its link graph $L(v)$ is non-
planar, has an edge $e$ such that in $C/e$ the link graph $L(e)$ at the
contraction vertex $e$ is non-planar or $C$ admits a rotation framework so
that there is a face boundary containing an odd number of red edges.

###### Proof.

By simply connectedness the face boundaries generate all cycles over the field
${\mathbb{F}}_{2}$. The _red parity_ of an edge set is the parity of its
number of red edges. Red parity is _additive_ ; that is, the red parity of the
sum (of two edge sets over ${\mathbb{F}}_{2}$) is equal to the sum of the red
parities of the summands. So take a cycle contains with odd red parity and
write it as a sum of face boundaries. One of these summands must have odd
parity. So this lemma follows from Section 1.2. ∎

###  1.3 Space restrictions

In this section we define space restrictions and prove Theorem 2.

Let $C$ be a 2-complex. Given a face $f$ of $C$, we denote by $C-f$ the
2-complex obtained from $C$ by deleting the face $f$. Given an edge $e$ of
$C$, the 2-complex888Recall that the boundary of a 2-complex is a closed trail
and as such contains each edge at most once. obtained from $C$ by
_(topologically) deleting the edge $e$_ is obtained from $C$ by replacing $e$
by parallel edges, one for each face incident with $e$ in such a way that the
incidence of $e$ with a face is inherited by the copy corresponding to that
face; for an example see the deletion of the edge $g$ in Figure 4).

######  Remark .

We think about ‘deleting an edge’ topologically; that is, in the geometric
realisation of a simplicial complex we delete the points on that edge. The
resulting topological space would not be a simplicial complex as the faces
incident with the deleted edge would no longer be bounded by cycles. Thus we
add a private edge to each such face to repair this defect.

Given a vertex $v$, the _splitting_ of $C$ at $v$ is obtained by replacing $v$
by one copy for each component of the link graph $L(v)$ such that each
incidence of $v$ is inherited by the copy whose link graph contains the face
or edge as an edge or vertex, respectively. We refer to these copies of $v$ as
_splitters_.

A _space restriction_ of $C$ is a 2-complex obtained from $C$ by deleting
faces, edges and isolated999A vertex is _isolated_ if it has no incidences.
vertices and splitting vertices in an arbitrary order.

######  Remark .

We regard deleting an isolated vertex as a special case of splitting that
vertex. Deleting an isolated101010An edge is _isolated_ if it is not incident
with a face. edge makes this edge disappear. Deleting edges and faces
commutes.

In the context of locally connected 2-complexes, it is natural to require that
after deletion of faces or edges one always splits all vertices, then these
enhanced operations still commute, and there would be only two space
restriction operations.

######  Observation .

Space restrictions of 2-complexes embeddable in 3-space are embeddable in
3-space.∎

The next lemma gives a condition when topologically deleting edges can be
combined with splitting vertices so that no parallel edges remain.

######  Lemma .

Let $C$ be a simplicial complex and $W\subseteq V(C)$ a vertex set. Let $X$ be
the set of those vertices of $V(C)\setminus W$ not contained in a face
containing two vertices of $W$. Let $C^{\prime}$ be the 2-complex obtained
from $C$ by topologically deleting all edges with an endvertex in $X$ and no
endvertex in $W$ and then splitting all vertices in $X$.

Then $C^{\prime}$ is a simplicial complex and the link graph at splitters
$x^{\prime}$ of vertices in $X$ is a nontrivial111111A star is _nontrivial_ if
it contains at least one edge. star. Moreover, every splitter $x^{\prime}$
that is in $N(W)$ sends a unique edge to $W$ and all other edges incident with
$x^{\prime}$ are incident with a single face.

###### Proof.

Let $x$ be a vertex of $X$. The link graph at $x$ after topologically deleting
the edges as described (but not yet split at $x$), is a disjoint union of
stars, and all those stars that are not single edges are centred at a vertex
whose corresponding edge has an endvertex in $W$. Recall that since $C$ is
simplicial, no two of its faces share two edges. Hence for each edge incident
with $x$ that we topologically delete, all its copies correspond to vertices
in $L(x)$ that are in different components.

Thus $C^{\prime}$ has no parallel edges and thus is a simplicial complex.
Above we have shown that the link graphs at splitters are as desired. ∎

####  1.3.1 Cones

The goal of this subsection is to find in a simplicial complex with a non-
planar link graph a cone over a subdivision of $K_{5}$ or $K_{3,3}$ as a space
restriction, compare Subsection 1.3.1. Given a graph $G$ without loops, the
_cone_ over $G$ is the 2-complex whose vertex set is $V(G)$ together with one
additional vertex, to which we refer to as the _top_. Its edge set is $E(G)$
together with one edge for every vertex $v$ of $G$ joining $v$ with the top.
Its set of faces consists of one face for every edge $e$ of $G$ that is
incident $e$ and the two edges from the endvertices of $e$ to the top. Note
that if $G$ has no parallel edges, then its cone is a simplicial complex.

######  Lemma .

Let $D$ be a simplicial complex with a vertex $v$. Assume that each edge not
incident with $v$ is in a single face, and that this face contains $v$, and
that the link graph at every vertex except for $v$ is a star whose centre
corresponds to an edge from that vertex to $v$. Then $D$ is equal to the cone
over the link graph at $v$.

###### Proof.

$D$ has the same vertex set as the cone over $L(v)$, and the same sets of
edges and faces. ∎

######  Lemma .

Let $C$ be a simplicial complex with a vertex $v$. Then $C$ has a space
restriction that is the cone over $L(v)$.

###### Proof.

First delete all faces that do not contain the vertex $v$. Then apply Section
1.3 with $W=\\{v\\}$ to the resulting simplicial complex. We conclude by
Subsection 1.3.1. ∎

######  Observation .

Let $C$ be a cone over the graph $G$. For every edge $f$ of $G$, the cone over
$G-f$ is a space restriction of $C$.

###### Proof.

Delete the face corresponding to the edge $f$. ∎

######  Corollary .

Let $C$ be a cone over a non-planar graph $G$. Then $C$ has a space
restriction that is a cone over a subdivision of $K_{5}$ or $K_{3,3}$.

###### Proof.

By Kuratowski’s theorem $G$ has a subgraph that is a subdivision of $K_{5}$ or
$K_{3,3}$. Now apply Subsection 1.3.1. ∎

######  Lemma .

Let $C$ be a simplicial complex with a vertex $v$ whose link graph is non-
planar. Then $C$ has a space restriction that is the cone over a subdivision
of $K_{5}$ or $K_{3,3}$.

###### Proof.

Combine Subsection 1.3.1 with Subsection 1.3.1. ∎

####  1.3.2 Combined cones

This subsection is structured similar to the previous subsection with a few
bells and whistles attached, and its goal is to find in every simplicial
complex $C$ with an edge $e$ so that in $C/e$ the link graph $L(e)$ at the
contraction vertex $e$ is non-planar, a space restriction similar to that of a
cone over $K_{5}$ or $K_{3,3}$. To formalise this we introduce ‘combined
cones’. This subsection culminates in Subsection 1.3.2 below.

Given two 2-complexes $C$ and $D$ together with a bijection $f$ between two
subsets of their vertices, the 2-complex obtained from $C$ by _simplicial
gluing_ $D$ via $f$ is obtained from the disjoint union of $C$ and $D$ by
identifying vertices via the bijection $f$, as well as edges and faces all of
whose vertices are in the image of $f$ and that after the identification of
the vertices would have the same vertex-sets. Note that gluings of simplicial
complexes are simplicial complexes. Given a vertex-sum
$G=G_{1}\oplus_{e}G_{2}$, the _simplicial combined cone_ over this vertex-sum
is obtained from the cone over $G_{1}$ by gluing the cone over $G_{2}$ via the
vertex set consisting of the vertices in faces that are incident with the edge
$e$; here we denote the unique vertex in a face $f$ not incident with $e$ by
$v_{f}$. The gluing bijection identifies the vertices $v_{f}$ from both cones
and identifies the endvertices of $e$ in such a way that the endvertex of $e$
that is a top in one cone is identified with the endvertex of $e$ from the
other cone that is not the top there.

######  Example .

Here we provide an alternative construction of the simplicial cone over
$G=G_{1}\oplus_{e}G_{2}$. Let $b$ denote the cut in $G$ that separates the
vertex sets of $G_{1}$ and $G_{2}$. Let the vertex set of $C$ consist of the
endvertices of $e$ together with the vertex set of $G/b$; that is, the graph
obtained from $G$ by contracting the edges of $b$. The edge set of $C$
consists of $e$ together with an edge for every vertex of $G$ from its
contraction vertex in $G/b$ to the endvertex of $e$ corresponding to the graph
$G_{i}$ that contains that vertex. We also add all edges of the graph $G/b$.
We add a face for every edge of $G$. If the edge is in $b$, its boundary
consists of the edge $e$ and the two edges to the contraction vertex of $G/b$
of that edge. If the edge is not in $b$, it is an edge of $G/b$ and the
boundary of the face is that edge together with the two edges to the graph
$G_{i}$ that are incident with that edge.

We remark that the construction of $C$ only relies on the graph $G$ and the
cut $b$ but not on the gluing isomorphism. Since this is an alternative
definition of the simplicial combined cone, it follows that two simplicial
combined cones are isomorphic if they have the same graph $G$ and within the
same cut $b$.

######  Lemma .

Let $D$ be a simplicial complex with an edge $e=vw$ so that all its faces and
edges contain $v$ or $w$ and all its vertices are adjacent to $v$ or $w$, and
if they are adjacent to both, then they are in common face with both of them.
Assume that for each $u\in\\{v,w\\}$ the simplicial complex $D$ restricted to
the vertex set consisting of $u$ and its neighbours and the faces and edges
containing containing $u$ is equal to the cone over $L(u)$.

Then $D$ is the simplicial combined cone over $L(v)\oplus_{e}L(w)$.

###### Proof.

$D$ has the same vertex set as the simplicial combined cone over
$L(v)\oplus_{e}L(w)$, and the same sets of edges and faces. ∎

######  Lemma .

Let $C$ be a simplicial complex with an edge $e=vw$. Then $C$ has a space
restriction that is a simplicial combined cone over the vertex-sum
$L(e)=L(v)\oplus_{e}L(w)$.

###### Proof.

First delete all faces that do not contain an endvertex of the edge $e$, and
all vertices and edges that afterwards are not in a face. Then apply Section
1.3 with $W=\\{v,w\\}$ to the resulting simplicial complex. This lemma gives a
space restriction $D$, which is a simplicial complex. Let $X$ be the set of
vertices of $D$ that are not in a face with the edge $e$. By that lemma the
link graph at every vertex $x$ of $X$ is a star, whose centre is an edge of
$D$ from $x$ to $v$ or $w$.

We obtain $D_{v}$ from $D$ by restricting to the vertex $v$ and its neighbours
and the faces and edges containing $v$.

######  Claim .

$D_{v}$ is the cone over $L(v)$.

Proof of Claim. Let $y$ be a vertex of $D_{v}$ other than $v$. By definition
of $D_{v}$, the vertex $y$ is a neighbour of $v$. If $y\in X$ its link graph
is a star, whose centre is an edge of $D_{v}$ from $y$ to $v$ or $w$. Now let
$y$ be outside $X$. By construction of $D_{v}$, all faces containing $y$ also
contain the vertex $v$ and thus the edge $yv$. Since $D_{v}$ is a simplicial
complex, the link graph at $y$ is a star centred at the vertex corresponding
to the edge $yv$. It follows that every edge not incident with $v$ has degree
one in a link graph and thus is in a single face. So by Subsection 1.3.1
$D_{v}$ is the cone over $L(v)$. ! $\diamondsuit$

We define ‘$D_{w}$’ like ‘$D_{v}$’ with ‘$w$’ in place of ‘$v$’. Like
Subsection 1.3.2, one proves that $D_{w}=L(w)$. By Subsection 1.3.2 $D$ is the
simplicial combined cone over $L(v)\oplus_{e}L(w)$. ∎

######  Observation .

Let $C$ be a simplicial combined cone over the vertex-sum
$G=G_{1}\oplus_{e}G_{2}$. For every edge $f$ of $E(G_{1})\setminus E(G_{2})$
or of $E(G_{1})\cap E(G_{2})$, the simplicial combined cone $C$ has the
simplicial combined cone over $G-f=(G_{1}-f)\oplus_{e}G_{2}$ or
$G-f=(G_{1}-f)\oplus_{e}(G_{2}-f)$, respectively, as a space restriction.

###### Proof.

Delete the face corresponding to the edge $f$ in the simplicial combined cone
over $G=G_{1}\oplus_{e}G_{2}$, and resulting edges or vertices not incident
with any face. Since deletion of $f$ commutes with the gluing, we obtain a
simplicial combined cone over $G-f$. ∎

######  Corollary .

Let $C$ be a simplicial combined cone over the vertex-sum
$G=G_{1}\oplus_{e}G_{2}$ such that $G$ is non-planar but $G_{1}$ and $G_{2}$
are planar. Then $C$ has a space restriction that is the simplicial combined
cone over a vertex-sum $H=H_{1}\oplus_{e}H_{2}$, where $H$ is a subdivision of
$K_{5}$ or $K_{3,3}$ and $H_{1}$ and $H_{3}$ have both at least three vertices
of degree at least three.

###### Proof.

By Kuratowski’s theorem $G$ has a subdivision of $K_{5}$ or $K_{3,3}$. So via
Subsection 1.3.2 and by taking a suitable space restriction if necessary,
assume that $G$ is a subdivision of one of these two graphs. Now consider the
edges of $G$ that correspond to edges of $G_{1}$ that in there are incident to
the vertex-sum vertex $e$. By the definition of vertex sum, these edges form a
cut in $G$. If this cut contains only two edges or has only one vertex of
degree at least three on one side, then $G_{1}$ or $G_{2}$ has one of the
graphs $K_{5}$ or $K_{3,3}$ as a minor (indeed, these 3-connected minors live
entirely one side of such a small cut), and thus is non-planar. So we may
assume that each side of the cut contains at least two vertices of degree
three, and that $e$ has degree at least three in $G_{1}$ and $G_{2}$. So
$G_{1}$ and $G_{2}$ both have at least three vertices of degree at least
three. ∎

######  Lemma .

Up to subdivision, there are exactly five vertex-sums as in Subsection 1.3.2,
one for $K_{5}$ and four for $K_{3,3}$.

###### Proof.

By Subsection 1.3.2 the simplicial combined cones over
$G=G_{1}\oplus_{e}G_{2}$ are uniquely determined by the graph $G$ and the cut
$b$ between the vertex sets of $G_{1}$ and $G_{2}$. While $K_{5}$ has only one
such cut with at least two vertices on either side, the number of non-atomic
nonempty cuts in $K_{3,3}$ is four: there are two cuts with 2 vertices versus
4 vertices and there are two cuts with 3 vertices versus 3 vertices. ∎

######  Lemma .

Let $C$ be a simplicial complex so that there is an edge $e=vw$ so that in
$C/e$ the link graph $L(e)$ at the contraction vertex $e$ is non-planar but
the link graphs at $v$ and $w$ in $C$ are planar. Then $C$ has a space
restriction that is a simplicial combined cone over from one of the five
classes in Subsection 1.3.2.

###### Proof.

Combine Subsection 1.3.2 with Subsection 1.3.2. Then use the explicit
description of Subsection 1.3.2. ∎

####  1.3.3 Möbius obstructions

We call a face $f$ of a 2-complex $C$ _red_ if $C$ admits a rotation framework
so that the boundary of $f$ contains an odd number of red edges; this is the
last outcome of Section 1.2, and in the previous two subsection we dealt with
the other two outcomes of that lemma. In this section we deal with this final
outcome. This subsection culminates in Subsection 1.3.3 below.

A _Möbius framework_ of a simplicial complex $C$ consists of a face $f$ of $C$
with vertices $v_{1}$, $v_{2}$, $v_{3}$ and a collection of six paths
$(P_{i}|i\in[6])$ such that $P_{i}$ and $P_{i+3}$ are vertex-disjoint paths in
the link graph at $v_{i}$ for $i\in[3]$ and do not contain any of the vertices
corresponding to edges of $f$, and so that the endvertex of $P_{i}$ and the
start vertex of $P_{i+1}$ correspond to edges that together with the edge
$v_{i}v_{i+1}$ form a face of $C$. We refer to the six faces obtained in this
way as the _witnesses_ of the Möbius framework. We denote Möbius frameworks by
tuples $(f,v_{1},v_{2},v_{3},(P_{i}|i\in[6]))$.

######  Lemma .

A locally 3-connected simplicial complex $C$ with a red face $f$ admits a
Möbius framework.

###### Proof.

For $i\in[3]$, let $v_{i}$ be one of the three vertices of the face $f$. By
assumption the link graph $L(v_{i})$ at $v_{i}$ is 3-connected. In there the
vertices corresponding to the edges $v_{i}v_{i+1}$ and $v_{i}v_{i-1}$ are
joined by an edge corresponding to $f$; recall that we denote this edge by
$f$. By assumption the link graph $L(v_{i})$ is planar and pick a plane
embedding. Let $D$ and $D^{\prime}$ be the two face boundaries of that
embedding that include the edge $f$. Since $L(v_{i})$ is 2-connected, the sets
$D$ and $D^{\prime}$ are cycles [25]. We obtain the two paths $P_{i}$ and
$P_{i+3}$ from $D$ and $D^{\prime}$, respectively, by deleting the two
endvertices of $f$. Any vertex in the intersection of $P_{i}$ and $P_{i+3}$
together with the edge $f$ separates the graph $L(v_{i})$. Since this graph is
3-connected by assumption, this is not possible, so $P_{i}$ and $P_{i+3}$ and
are vertex-disjoint.

By construction the endvertices of these two paths correspond to edges of $C$
that together with one of the edges $v_{i}v_{i\pm 1}$ lie in a common face. We
pick a direction on these paths so that the start vertex lies in a common face
with $v_{i}v_{i-1}$, whilst the endvertex lies in a common face with
$v_{i}v_{i+1}$. These common faces are adjacent to $f$ in the rotators at
$v_{i}v_{i-1}$ and $v_{i}v_{i+1}$, respectively.

Now assume that $C$ admits a rotation framework. Then in the link graphs
$L(v_{i})$ and $L(v_{i+1})$ at the rotator at the vertex $v_{i}v_{i+1}$ the
edge $f$ has the same two neighbours. So by exchanging the roles of $P_{2}$
and $P_{5}$ if necessary, we ensure that the endvertex of $P_{1}$ and the
start vertex of $P_{2}$ correspond to edges that together with the edge
$v_{1}v_{2}$ form a face of $C$. Similarly, we ensure that the endvertex of
$P_{2}$ and the start vertex of $P_{3}$ correspond to edges that together with
the edge $v_{2}v_{3}$ form a face of $C$.

Given $i\in{\mathbb{Z}}_{6}$, denote by $D_{i}$ the disc of the embedding of
the link graph $L(v_{j})$ with $j=i\ mod\ 3$ that has the path $P_{i}$ and the
edge $f$ in its boundary (by 3-connectivity this disc is uniquely determined
and referred to $D$ or $D^{\prime}$ in the above construction).

Recall that $C$ is a directed 2-complex and so the face $f$ is equipped with
an orientation. When we consider the face $f$ as an edge in link graphs, this
orientation induces a direction of the edge $f$. So the _left side_ and the
_right side_ of the edge $f$ are well-defined.

######  Claim .

In embeddings of the link graphs $L(v_{i})$ and $L(v_{i+1})$ the discs $D_{i}$
and $D_{i+1}$ are on the same side of the edge $f$ if and only if the rotators
at the vertex $v_{i}v_{i+1}$ are reverse.

Proof of Claim. The edge $f$ is incident with the vertex $v_{i}v_{i+1}$ in
both link graphs $L(v_{i})$ and $L(v_{i+1})$. We have already constructed a
face so that its edges in the link graphs $L(v_{i})$ and $L(v_{i+1})$ are
incident with the vertex $v_{i}v_{i+1}$ and in both discs $D_{i}$ and
$D_{i+1}$; we denote this face by $g$. So $g$ – considered as an edge of the
link graphs $L_{(}v_{i})$ and $L(v_{i+1})$ – is on the same side of $f$ if and
only if $D_{i}$ and $D_{i+1}$ are on the same side of $f$. So the rotators at
the vertex $v_{i}v_{i+1}$ determine on which side of $f$ the edge $g$ is. !
$\diamondsuit$

Now assume that $C$ admits a rotation framework $\Sigma$ so that the boundary
of $f$ contains an odd number of red edges. Applying Subsection 1.3.3
recursively at all edges of $f$ and using the fact that $f$ contains an odd
number of red edges implies that the endvertex of $P_{3}$ and the start vertex
of $P_{4}$ correspond to edges that together with the edge $v_{1}v_{2}$ form a
face of $C$. A similar statement is true for $P_{1}$ and $P_{6}$. It follows
that $(f,v_{1},v_{2},v_{3},(P_{i}|i\in[6]))$ is a Möbius framework. ∎

######  Lemma .

In a simplicial complex $C$ with a Möbius framework, every rotation framework
has a red face.

###### Proof.

Let $(f,v_{1},v_{2},v_{3},(P_{i}|i\in[6]))$ be a Möbius framework of $C$. We
claim that $f$ is red with respect to every rotation framework of $C$. Suppose
for a contradiction that $C$ admits a rotation framework where $f$ is not red.
Then we can flip the embeddings at the link graphs at vertices of $f$ so that
all three edges of $f$ are green. By symmetry assume that in the embedding of
the link graph $L(v_{1})$ the path $P_{1}$ is on the left of $f$, and $P_{4}$
is on its right. Since the edge $v_{1}v_{2}$ is green, $P_{2}$ is on the left
of $f$ in the embedding of $L(v_{2})$. Since $v_{2}v_{3}$ is green, $P_{3}$ is
on the left of $f$. Since $v_{3}v_{1}$ is green, we conclude that $P_{4}$ is
on the left of $f$, a contradiction to our assumption. ∎

A triangulation of the Möbius-strip is _nice_ if it has a central cycle of
length three and all edges of face degree two are on the central cycle or have
exactly one endvertex on the central cycle. A _Möbius obstruction_ is obtained
from a nice triangulation of the Möbiusstrip by attaching a face at the
central cycle. A Möbius obstruction is an example of a torus crossing
obstruction and as such does not embed in 3-space, see chapter 3 for a proof.

######  Lemma .

A Möbius obstruction admits a Möbius framework.

###### Proof.

Take the face bounded by the central cycle as the face $f$ of the Möbius
framework and the link graphs at its endvertices are parallel graphs121212A
_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. whose branching vertices
have degree three and take the unique choices possible for the paths $P_{i}$.
This defines a Möbius framework. ∎

######  Corollary .

A Möbius obstruction admits no planar rotation system.

###### Proof.

By Subsection 1.3.3 this follows from Subsection 1.3.3. ∎

######  Lemma .

[[1]] Let $S$ be a connected surface with boundary that admits a triangulation
$T$ so that the Euler-characteristic $V-E-F$ is zero. If $S$ has a single
boundary component, it is the Möbius strip. If it has two boundary components
it is an untwisted strip (so homeomorphic to a disc with a hole).

######  Corollary .

Let $S$ be a connected surface with nontrivial boundary131313Recall that
boundaries of 2-manifolds with boundary are always 1-dimensional, so
homeomorphic to $\operatorname{\mathbb{S}}^{1}$. that admits a triangulation
$T$ so that there is a cycle $o$ such that all edges of face degree two in $T$
are on $o$ or have exactly one endvertex on $o$, and no point on $o$ is on the
boundary. Then $S$ is homeomorphic to a Möbius-strip or an untwisted strip.

###### Proof.

$S\setminus o$ has one or two components. So $S$ has at most two boundary
components, and at least one by assumption. So by Subsection 1.3.3, it
suffices to show that $V-E+F=0$. All vertices lie on the central cycle $o$ or
on one of the boundary cycles. We split the edges into two sets, those that
lie on $o$ or on the boundary – the number of them is equal to the number of
vertices – and the edges between $o$ and the boundary. All edges of the second
type lie in exactly two faces and each face contains precisely two edges of
type two. So $V-E+F=0$. ∎

######  Lemma .

If $C$ has a Möbius framework, it has a Möbius obstruction as a space
restriction.

###### Proof.

Let a Möbius framework $(f,v_{1},v_{2},v_{3},(P_{i}|i\in[6]))$ be given. We
obtain $D$ from $C$ by deleting all faces except for $f$, the six witnesses of
the Möbius framework and those faces corresponding to edges of the paths
$P_{i}$. Then we topologically delete all edges except for those of $f$ and
those corresponding to vertices of the graphs $P_{i}$. We complete the
definition of $D$ by splitting all vertices.

We claim that $D$ is a Möbius obstruction. For this, it remains to show that
$D-f$ is a triangulation of a Möbius-strip. Since $D-f$ is locally connected
by construction, we deduce that $D-f$ is a triangulation of some connected
surface with nontrivial boundary; note that splitting vertices ensures that
the boundary is 1-dimensional. Let $o$ be the boundary cycle of $f$. As a
small neighbourhood of $o$ includes a Möbius-strip in $D-f$, the geometric
realisation of $D-f$ is not an untwisted strip . So by Subsection 1.3.3, $D-f$
is a triangulation of a Möbius-strip. ∎

######  Lemma .

If a locally 3-connected simplicial complex has a red face, then it has a
Möbius obstruction as a space restriction.

###### Proof.

Combine Subsection 1.3.3 with Subsection 1.3.3. ∎

####  1.3.4 Proof of Theorem 2 assuming Theorem 1.0.1

We denote by ${{\cal Z}}$ the following list:

  1. 1.

cones over subdivisions of $K_{5}$ or $K_{3,3}$;

  2. 2.

simplicial combined cones from the five families of Subsection 1.3.2;

  3. 3.

Möbius obstructions.

######  Remark .

All members of ${{\cal Z}}$ are simply connected simplicial complexes.

######  Theorem 1.3.1.

Let $C$ be a simply connected locally 3-connected 2-dimensional simplicial
complex. Then $C$ has a planar rotation system if and only if $C$ has no space
restriction from the list ${{\cal Z}}$.

###### Proof.

First we verify that the finitely many members of ${{\cal Z}}$ do that admit a
planar rotation system. Clearly, cones over subdivisions of $K_{5}$ or
$K_{3,3}$ do not admit planar rotation systems. If $C$ is a simplicial
combined cone from ${{\cal Z}}$ then it has an edge $e$ so that the link graph
$L(e)$ at the contraction vertex $e$ is not planar. Since the existence of
planar rotation system is preserved by contracting non-loop edges by Section
1.1, such $C$ also do not admit planar rotation system. Finally a Möbius
obstruction does not admit a planar rotation systems by Subsection 1.3.3.
Since having a planar rotation system is preserved under taking space
restrictions, it follows that if $C$ has a space restriction from ${{\cal
Z}}$, then it does not admit a planar rotation system.

Conversely, assume that $C$ has no planar rotation system. Our aim is to find
a space restriction from ${{\cal Z}}$. By Section 1.2, $C$ has a vertex $v$
such that its link graph $L(v)$ is non-planar, has an edge $e$ such that in
$C/e$ the link graph $L(e)$ at the contraction vertex $e$ is non-planar or $C$
admits a rotation framework so that there is a face boundary containing an odd
number of red edges. In these three cases we find a member of ${{\cal Z}}$ by
applying Subsection 1.3.1, Subsection 1.3.2 and Subsection 1.3.3,
respectively. ∎

###### Proof of Theorem 1..

By Theorem 1.0.1 a simply connected simplicial complex is embeddable in
$\operatorname{\mathbb{S}}^{3}$ if and only if it has a planar rotation
system. So Theorem 1 is implied by Theorem 1.3.1. ∎

###### Proof of Theorem 2..

By Theorem 2.2.2 a simplicial complex with $H_{1}(C,{\mathbb{F}}_{p})=0$ is
embeddable if and only if it is simply connected and it has a planar rotation
system. So Theorem 2 is implied by Theorem 1.3.1. ∎

###  1.4 Space minors

In this section we introduce the space minor relation, prove a few basic
properties and show that the subset of ${{\cal Z}}$ of its space minor-minimal
elements is finite.

A _space minor_ of a 2-complex is obtained by successively performing one of
the five operations.

  1. 1.

contracting an edge that is not a loop;

  2. 2.

deleting a face (and all edges or vertices only incident with that face);

  3. 3.

contracting a face of size one141414Although we do not need it in our proofs,
it seems natural to allow contractions of faces of size one. This simply
removes this face from $C$ and removes its unique edge from all other faces.
or two if its two edges are not loops;

  4. 4.

splitting a vertex;

  5. 5.

topologically deleting an edge.

######  Remark .

A little care is needed with contractions of faces. This can create faces
traversing edges multiple times. In this paper, however, we do not contract
faces consisting of two loops and we only perform these operations on
2-complexes whose faces have size at most three. Hence it could only happen
that after contraction some face traverses an edge twice but in opposite
direction. Since faces have size at most three, these traversals are adjacent.
In this case we omit the two opposite traversals of the edge from the face. We
delete faces incident with no edge. This ensures that the class of 2-complexes
with faces of size at most three is closed under face contractions.

A 2-complex is _3-bounded_ if all its faces are incident with at most three
edges. The closure of the class of simplicial complexes by space minors is the
class of 3-bounded 2-complexes.

It is easy to see that the space minor operations preserve embeddability in
$\operatorname{\mathbb{S}}^{3}$ (or in any other 3-dimensional manifold), see
Section 1.4 below, and the first three commute when well-defined.151515In
order for the contraction of a face to be defined we need the face to have at
most two edges. This may force contractions of edges to happen before the
contraction of the face.

######  Lemma .

The space minor relation is well-founded161616A partial order is _well-
founded_ if every strictly decreasing chain is finite. For example, a well-
ordering is a well-founded total order..

###### Proof.

The _face degree_ of an edge $e$ is the number of faces incident with $e$. We
consider the sum $S$ of all face degrees ranging over all edges. None of the
five above operations increases $S$. And 1, 2 and 3 always strictly decrease
$S$. Hence we can apply 1, 2 or 3 only a bounded number of times.

Note that operations 4 and 5 do not create isolated vertices or edges. Thus
after a finite number of steps, we may assume that we do not attempt any
further operations 4 or 5 to isolated vertices or edges. Applying splitting to
a vertex with connected link graph and applying topological deletion of an
edge to an edge incident with a single face is the identity operation. We
refer to such applications of 4 and 5 as _trivial_.

Since no operation increases the sizes of the faces, the total number of
vertices and edges incident with faces is bounded. Operation 4, when not the
identity, increases the number of vertices and preserves the number of edges.
For operation 5 it is the other way round. Hence all operations of 4 and 5 can
only be nontrivially applied a bounded number of times. ∎

Figure 1.2: The operation that in the link graph corresponds to contracting a
face $f$ only incident with a single edge $\ell$. The edge $\ell$ must be a
loop. Hence in the link graph we have two vertices for $\ell$ which are joined
by the edge $f$. On the left we depicted that configuration. Contracting $f$
in the complex yields the configuration on the right. Formally, we delete $f$
and both its endvertices and add for each face $x$ of size at least two
traversing $\ell$ an edge as follows. Before the contraction, the link graph
contains two edges corresponding to the traversal of $x$ of $\ell$. These
edges have precisely two distinct endvertices that are not vertices
corresponding to $\ell$. We add an edge between these two vertices.

######  Lemma .

If a 2-complex $C$ has a planar rotation system, then all its space minors do.

###### Proof.

By Section 1.1 existence of planar rotation systems is preserved by
contracting edges that are not loops. Clearly the operations 2, 4 and 5
preserve planar rotation systems as well. Since contracting a face of size two
corresponds to locally in the link graph contracting the corresponding edges,
contracting faces of size two preserves planar rotation systems as noted after
Subsection 3.3.4. The operation that corresponds to contracting a face of size
one in the link graph is explained in Figure 1.2. Now let $f$ be an edge in
the link graph corresponding to a face of size one. Since the rotators at the
two endvertices of $f$ are reverse of one another (by the definition of planar
rotation systems of link graphs at vertices incident with loops), contracting
$f$ as a face of $C$ preserves the embedding of the link graph at the unique
vertex incident with $f$ in the plane. Thus contracting a face of size one
preserves planar rotation systems. ∎

######  Remark .

For all space minor operations, a topological way to prove that they preserve
embeddability is to remove from the embedding a small neighbourhood of the
region where a single operation takes place, do the operation in there and
glue it back on. However, there are also algebraic proofs, which perhaps are
less intuitive but easier to verify. We illustrate this by formally proving
that contracting a face of size one, contraction of an edge and splitting a
vertex preserves embeddability.

Firstly, let $C$ be a 2-complex with a face $f$ of size one embedded in
$\operatorname{\mathbb{S}}^{3}$. Extend $C$ to a simply connected 2-complex
embedded in $\operatorname{\mathbb{S}}^{3}$ by Theorem 2.8.1 (making $C$
locally connected can easily be done by considering a ‘thickening’); call it
$D$. Now $D/f$ has a planar rotation system by Section 1.4 and is simply
connected, so by Theorem 2.2.1 is embeddable in
$\operatorname{\mathbb{S}}^{3}$; thus $C/f$ is embeddable.

Secondly, let $C$ be a 2-complex with a nonloop $e$. Then $C$ embeds in
$\operatorname{\mathbb{S}}^{3}$ if and only if $C/e$ embeds in
$\operatorname{\mathbb{S}}^{3}$. We can argue similar as above via Theorem
2.8.1, refering to Section 1.1 and Section 1.1 in place of Section 1.4

Thirdly, let $D$ be a 2-complex obtained from an embedded complex $C$ by
splitting a vertex $v$. We obtain $D^{\prime}$ from $D$ by adding a new vertex
and introducing new edges from it to all splitters of $v$. It suffices to show
that $D^{\prime}$ is embeddable. Contracting the newly added edges from
$D^{\prime}$ yields the 2-complex $C$. Now use the above fact that a 2-complex
$X$ with a nonloop edge $e$ embeds in $\operatorname{\mathbb{S}}^{3}$ if and
only if $X/e$ embeds in $\operatorname{\mathbb{S}}^{3}$. Since $C$ is obtained
from $D^{\prime}$ by contracting a tree, we deduce that $D^{\prime}$ embeds in
$\operatorname{\mathbb{S}}^{3}$. Hence the subcomplex $C$ embeds in
$\operatorname{\mathbb{S}}^{3}$.

######  Lemma .

Let $H$ and $G$ be graphs without loops so that $H$ is a minor of $G$. The
cone over $G$ has the cone over $H$ as a space minor.

###### Proof.

By Subsection 1.3.1, in order to make an inductive proof work it suffices to
consider the case that $H=G/f$ for some edge $f$ of $G$. Now in the cone over
$G$, let $f$ be the face corresponding to the edge $f$ in the link graph at
the top. Let $e$ be the edge of $f$ that is not incident with the top. Now
contract $e$ and then the face $f$ gets size two, and also contract it onto an
edge. The resulting 2-complex is the cone over $H$. ∎

######  Remark .

(Motivation) Simplicial combined cones do not work so well with space minors.
The problem is Section 1.4 is not true for combined cones. To see this, note
that the simplicial combined over an edge $e$ can contain a tetrahedron at the
edge $e$, where the two faces containing $e$ are in both cones and each cone
contributes one of the remaining two faces. Combined cones over
$G_{1}\oplus_{e}G_{2}$ where every edge of $G_{2}$ is subdivided cannot
contain tetrahedra, and in fact when embedded in 3-space the embedding has
only one chamber. So such 2-complexes cannot have a space minor where the
embedding has more than one chamber; for example, when the 2-complex includes
a tetrahedron. This example shows that the minimal members of the five
families of Subsection 1.3.2 are a little bit nasty to compute – although they
are clearly finite.

However, this is completely artificial and we can reduce the constructions
from Subsection 1.3.2 to five excluded minors if we give up that we want the
excluded minors to be simplicial complexes, as follows.

Given two 2-complexes $C$ and $D$ with isomorphic subcomplexes $C^{\prime}$
and $D^{\prime}$, respectively, the 2-complex obtained from $C$ by _gluing_
$D$ at $C^{\prime}$ is obtained from the disjoint union of $C$ and $D$ by
identifying $C^{\prime}$ and $D^{\prime}$ via their isomorphism. Given a
vertex-sum $G=G_{1}\oplus_{e}G_{2}$, the _combined cone_ over this vertex-sum
is obtained from the cone over $G_{1}$ by gluing the cone over $G_{2}$ via the
subcomplex consisting of the edge $e$ and its incident faces in both cones
such that in the resulting complex the tops of the cones are glued onto
distinct endvertices of $e$.

######  Remark .

While simplicial combined cones are always simplicial complexes, the gluing
process for combined cones may create parallel edges.

It is straightforward to minor simplicial combined cones down to combined
cones over the same graphs:

######  Lemma .

Let $C$ be a simplicial combined cone over $G=G_{1}\oplus_{e}G_{2}$. Let $D$
be the 2-complex obtained from $C$ by topologically deleting all edges not
incident with an endvertex of $e$. Then $D$ is equal to the combined cone
$G=G_{1}\oplus_{e}G_{2}$. ∎

######  Lemma .

Let $G$ be obtained from $H$ by subdividing an edge. Let $C$ be the combined
cone over $G=G_{1}\oplus_{e}G_{2}$ such that the vertex $e$ has degree more
than two. Then there is a subdivision edge $f$ of $G$ such that $C$ has a
space minor over one of the vertex-sums $H=(G_{1}/f)\oplus_{e}G_{2}$ or
$H=G_{1}\oplus_{e}(G_{2}/f)$.

###### Proof.

Since the vertex $e$ has degree more than two, one of the subdivision edges is
not incident with $e$; denote that edge by $f$ and assume $f$ is an edge of
$G_{1}$. Note that $H=(G_{1}/f)\oplus_{e}G_{2}$. Let $x$ be the unique edge of
the face $f$ that is not incident with an endvertex of the edge $e$. Now in
$C$ contract $x$ and then the face $f$ gets size two, and also contract it
onto an edge. The resulting 2-complex is the combined cone over
$H=(G_{1}/f)\oplus_{e}G_{2}$. ∎

Figure 1.3: The only two nice space minor minimal triangulations of the Möbius
strip.

######  Lemma .

There are only two nice space minor minimal triangulations of the Möbius
strip; these are depicted in Figure 1.3

###### Proof.

Let $C$ be a nice triangulation of the Möbius strip that is space minor
minimal. So all vertices are on the central cycle $o$ or on the boundary
cycle, which we call $b$. We give $b$ the structure of a directed cycle. Since
$C$ is a triangulation, it is uniquely determined by the sequence of degrees
of the vertices on $b$, read in the order in which they appear on $b$. Since
$o$ contains exactly three vertices, each vertex of $b$ has degree at most 5.
If a vertex of $b$ has degree three, contract one of its incident edges on $b$
and the resulting face of size two. We obtain a simplicial complex and thus a
smaller Möbius obstruction. So by minimality of $C$, all vertices of $b$ have
degree at least 4. If two vertices that are adjacent on $b$ have degree four,
then we can contract the edge joining them and the resulting face of size two
and obtain a simplicial complex, and thus a smaller Möbius obstruction. So by
minimality of $C$, on $b$ no two vertices of degree 4 are adjacent. We denote
by $d_{5}$ the number of degree five vertices of $b$ and by $d_{4}$ the number
of degree four vertices of $b$.

######  Claim .

$12-d_{5}=3d_{5}+2d_{4}$.

Proof of Claim. We count the edges between $o$ and $b$ in two different ways.
Since every degree five vertex of $b$ contributes three edges and every degree
four vertex of $b$ contributes two edges, this number is $3d_{5}+2d_{4}$.

Now let $v$ be a vertex of $o$, and let $N$ be a small open neighbourhood
around the point $v$ in the Möbius strip. The cycle $o$ divides $N$ into two
components; we shall refer to these components as _top_ and _bottom_. The _top
degree_ of $v$ is the number of edges incident with $v$ that are in the top
component. If the top degree of a vertex of $o$ is more than two, since its
top-degree neighbours are consecutive on $b$, it has a degree three neighbour,
which is not possible as shown above. So the top degree is at most two. The
top degree cannot be zero as $o$ does not bound a disc as the triangulation is
nice. So the top degree is one or two. If the top degree is one, then the
unique top-neighbour $x$ on $b$ has degree five and the edge from $v$ to $x$
is its middle edge in the rotator of $x$ in the embedding. Similarly we
defined the _bottom degree_ , and do these same analysis. Let $t$ be the
number of vertices on $o$ whose top degrees are one plus the number of
vertices on $o$ whose bottom degree are one. By the above $t=d_{5}$. So the
number of edges across is $12-d_{5}$ (indeed, we have 3 top-degrees and 3
bottom-degrees and if $d_{5}=0$ all count twice). ! $\diamondsuit$

Rearranging the equation of Section 1.4 yields $6=2d_{5}+d_{4}$. This equation
has the non-negative integer solutions $(d_{5}=3,d_{4}=0)$ and
$(d_{5}=2,d_{4}=2)$. Since $b$ has length at least three, we have that the
additional constraint that $d_{5}+d_{4}\geq 3$ and since no two degree four
vertices can be adjacent on $b$, we conclude that $d_{5}\geq 2$. So there are
no other solutions that are relevant to us.

The solution $(d_{5}=3,d_{4}=0)$ gives the sequence $5,5,5$ of degrees, which
corresponds to the right triangulation of Figure 1.3. Since no two vertices of
degree four can be adjacent on $b$, the solution $(d_{5}=2,d_{4}=2)$ can only
give the (cyclic) sequence $5,4,5,4$; this sequence corresponds to the left
triangulation of Figure 1.3.

∎

######  Corollary .

There are only two space minor minimal Möbius obstructions; these are obtained
from the simplicial complexes of Figure 1.3 by attaching a face at the central
cycle.∎

Let ${{\cal Z}}^{\prime}$ consist of the cones over $K_{5}$ and $K_{3,3}$, the
five combined cones over $K_{5}$ and $K_{3,3}$ (compare Subsection 1.3.2) and
the Möbius obstructions from Section 1.4.

######  Lemma .

Every element of ${{\cal Z}}$ has a space minor in ${{\cal Z}}^{\prime}$. The
set ${{\cal Z}}^{\prime}$ has only nine elements.

###### Proof.

Recall that the list ${{\cal Z}}$ is the combination of the lists given in
Subsection 1.3.1, Subsection 1.3.2 and Subsection 1.3.3. Now apply to these
lists Section 1.4, Section 1.4 and Section 1.4, respectively. Finally,
$|{{\cal Z}}^{\prime}|=2+5+2=9$. ∎

###  1.5 Concluding remarks

In an earlier version of this paper, which is available on arxiv [5], we use
Section 1.2 instead of Section 1.2 to compute the excluded minors. The
disadvantage of this earlier approach is that it is much more complicated and
the list of excluded minors is much longer (in fact in that earlier version we
did not manage to preserve simple connectedness and being a simplicial complex
for all the obstructions, which added clutter to the list). However, the
advantage is that with the old way one can characterise the existence of a
planar rotation system combinatorically in terms of finitely many obstructions
– without the assumption of simple connectedness; details can be found in [5,
Theorem 7.1]. For general (not necessarily locally 3-connected) simply
connected simplicial complexes, we take the road via Section 1.2 (as the
stronger assumptions of Section 1.2 do not seem available to us in this more
general context), see chapter 3 for details.

Theorem 2 is a structural characterisation of which locally 3-connected
2-dimensional simplicial complex $C$ with trivial first homology group embed
in 3-space. Does this have algorithmic consequences? The methods of this
chapter give an algorithm that checks in linear171717Linear in the number of
faces of $C$. time whether a locally 3-connected 2-dimensional simplicial
complex has a planar rotation system. For general 2-dimensional simplicial
complex we obtain a quadratic algorithm, see chapter 3 for details. But how
easy is it to check whether $C$ is simply connected? For simplicial complexes
in general this is not decidable; indeed for every finite presentation of a
group one can build a 2-dimensional simplicial complex that has that
fundamental group. However, for simplicial complexes that embed in some
(oriented) 3-manifold; that is, that have a planar rotation system, this
problem is known as the sphere recognition problem. Recently it was shown that
sphere recognition lies in NP [20, 35] and co-NP assuming the generalised
Riemann hypothesis [19, 41]. It is an open question whether there is a
polynomial time algorithm.

##  Chapter 2 The topological part of the proof of Theorem 2

###  2.1 Abstract

We prove that 2-dimensional simplicial complexes with trivial first homology
group have topological embeddings in 3-space if and only if there are
embeddings of their link graphs in the plane that are compatible at the edges
and they are simply connected.

###  2.2 Introduction

Here we give combinatorial characterisations for when certain simplicial
complexes embed in 3-space. This completes the proof of a 3-dimensional
analogue of Kuratowski’s characterisation of planarity for graphs, started in
chapter 1.

A (2-dimensional) simplicial complex has a topological embedding in 3-space if
and only if it has a piece-wise linear embedding if and only if it has a
differential embedding [2, 17, 28].111However this is not equivalent to having
a linear embedding, see [4], and [24] for further references.  Perelman proved
that every compact simply connected 3-dimensional manifold is isomorphic to
the 3-sphere $\operatorname{\mathbb{S}}^{3}$ [30, 31, 32]. In this chapter we
use Perelman’s theorem to prove a combinatorial characterisation of which
simply connected simplicial complexes can be topologically embedded into
$\operatorname{\mathbb{S}}^{3}$ as follows.

The _link graph_ at a vertex $v$ of a simplicial complex is the graph whose
vertices are the edges incident with $v$ and whose edges are the faces
incident with $v$ and the incidence relation is as in $C$, see Figure 2.1.

Figure 2.1: The link graph at the vertex $v$ is indicated in grey. The edge
$e$ projects down to a vertex in the link graph. The faces incident with $e$
project down to edges.

Roughly, a _planar rotation system_ of a simplicial complex $C$ consists of
cyclic orientations $\sigma(e)$ of the faces incident with each edge $e$ of
$C$ such that there are embeddings in the plane of the link graphs such that
at vertices $e$ the cyclic orientations of the incident edges agree with the
cyclic orientations $\sigma(e)$. It is easy to see that if a simplicial
complex $C$ has a topological embedding into some oriented 3-dimensional
manifold, then it has a planar rotation system. Conversely, for simply
connected simplicial complexes the existence of planar rotation systems is
enough to characterise embeddability into $\operatorname{\mathbb{S}}^{3}$:

######  Theorem 2.2.1.

Let $C$ be a simply connected simplicial complex. Then $C$ has a topological
embedding into $\operatorname{\mathbb{S}}^{3}$ if and only if $C$ has a planar
rotation system.

A related result has been proved by Skopenkov for general 3-manifolds (not
necessarily compact) [36]. The main result of this chapter is the following
extension of Theorem 2.2.1.

######  Theorem 2.2.2.

Let $C$ be a simplicial complex such that the first homology group
$H_{1}(C,{\mathbb{F}}_{p})$ is trivial for some prime $p$. Then $C$ has a
topological embedding into $\operatorname{\mathbb{S}}^{3}$ if and only if $C$
is simply connected and it has a planar rotation system.

This implies characterisations of topological embeddability into
$\operatorname{\mathbb{S}}^{3}$ for the classes of simplicial complexes with
abelian fundamental group and simplicial complexes in general, see Section 2.8
for details.

This chapter is organised as follows. After reviewing some elementary
definitions in Section 2.3, in Section 2.4, we introduce rotation systems,
related concepts and prove basic properties of them. In Sections 2.5 and 2.6
we prove Theorem 2.2.1. The proof of Theorem 2.2.2 in Section 2.7 makes use of
Theorem 2.2.1. Further extensions are derived in Section 2.8. In Section 2.9
we discuss how one could characterise embeddability of 2-complexes in general
3-manifolds combinatorially.

###  2.3 Basic definitions

In this short section we recall some elementary definitions that are important
for this chapter.

A _closed trail_ in a graph is a cyclically ordered sequence
$(e_{n}|n\in{\mathbb{Z}}_{k})$ of distinct edges $e_{n}$ such that the
starting vertex of $e_{n}$ is equal to the endvertex of $e_{n-1}$. An
(abstract) (2-dimensional) _complex_ is a graph222In this paper graphs are
allowed to have parallel edges and loops. All graphs and 2-complexes
considered in this paper are finite. $G$ together with a family of closed
trails in $G$, called the _faces_ of the complex. We denote complexes $C$ by
triples $C=(V,E,F)$, where $V$ is the set of _vertices_ , $E$ the set of
_edges_ and $F$ the set of faces. We assume furthermore that every vertex of a
complex is incident with an edge and every edge is incident with a face. The
_1-skeleton_ of a complex $C=(V,E,F)$ is the graph $(V,E)$. A _directed_
complex is a complex together with a choice of direction at each of its edges
and a choice of orientation at each of its faces. For an edge $e$, we denote
the direction chosen at $e$ by $\vec{e}$. For a face $f$, we denote the
orientation chosen at $f$ by $\vec{f}$.

Examples of complexes are (abstract) (2-dimensional) simplicial complexes. In
this paper all simplicial complexes are directed – although we will not always
say it explicitly. A _(topological) embedding_ of a simplicial complex $C$
into a topological space $X$ is an injective continuous map from (the
geometric realisation of) $C$ into $X$. In our notation we suppress the
embedding map and for example write ‘$\operatorname{\mathbb{S}}^{3}\setminus
C$’ for the topological space obtained from $\operatorname{\mathbb{S}}^{3}$ by
removing all points in the image of the embedding of $C$. A 2-complex is
_reasonable_ if each vertex or edge is incident with a face.

######  Example .

Simply connected 2-complexes are reasonable.

######  Remark .

All 2-complexes considered in this paper are reasonable, and we add this
assumption to all lemmas of this paper. This assumption is necessary for
various constructions and we believe it is much simpler for the reader to
assume it throughout than having to carry it along all the time, and add a few
technical details to some otherwise fairly natural proofs. Graph theoretically
speaking, this just means that 2-complexes and their link graphs have no
isolated vertices.

In this paper, a _surface_ is a compact 2-dimensional manifold (without
boundary)333We allow surfaces to be disconnected. . Given an embedding of a
graph in an oriented surface, the _rotation system_ at a vertex $v$ is the
cyclic orientation444A _cyclic orientation_ is a choice of one of the two
orientations of a cyclic ordering. of the edges incident with $v$ given by
‘walking around’ $v$ in the surface in a small circle in the direction of the
orientation. Conversely, a choice of rotation system at each vertex of a graph
$G$ defines an embedding of $G$ in an oriented surface as explained in chapter
1.

A _cell complex_ is a graph $G$ together with a set of directed walks such
that each direction of an edge of $G$ is in precisely one of these directed
walk es. These directed walks are called the _cells_. The geometric
realisation of a cell complex is obtained from (the geometric realisation of)
its graph by gluing discs so that the cells are the boundaries of these discs.
The geometric realisation is always an oriented surface. Note that cell
complexes need not be complexes as cells are allowed to contain both
directions of an edge. The _rotation system of_ a cell complex $C$ is the
rotation system of the graph of $C$ in the embedding in the oriented surface
given by $C$.

###  2.4 Rotation systems

In this section we introduce rotation systems of complexes and some related
concepts.

The _link graph_ of a simplicial complex $C$ at a vertex $v$ is the graph
whose vertices are the edges incident with $v$. The edges are the faces
incident555A face is incident with a vertex if there is an edge incident with
both of them. with $v$. The two endvertices of a face $f$ are those vertices
corresponding to the two edges of $C$ incident with $f$ and $v$. We denote the
link graph at $v$ by $L(v)$.

A _rotation system_ of a directed complex $C$ consists of for each edge $e$ of
$C$ a cyclic orientation666If the edge $e$ is only incident with a single
face, then $\sigma(e)$ is empty. $\sigma(e)$ of the faces incident with $e$.

Important examples of rotation systems are those _induced_ by topological
embeddings of 2-complexes $C$ into $\operatorname{\mathbb{S}}^{3}$ (or more
generally in some oriented 3-manifold); here for an edge $e$ of $C$, the
cyclic orientation $\sigma(e)$ of the faces incident with $e$ is the ordering
in which we see the faces when walking around some midpoint of $e$ in a circle
of small radius777Formally this means that the circle intersects each face in
a single point and that it can be contracted onto the chosen midpoint of $e$
in such a way that the image of one such contraction map intersects each face
in an interval. – in the direction of the orientation of
$\operatorname{\mathbb{S}}^{3}$. It can be shown that $\sigma(e)$ is
independent of the chosen circle if small enough and of the chosen midpoint.

Such rotation systems have an additional property: let $\Sigma=(\sigma(e)|e\in
E(C))$ be a rotation system of a simplicial complex $C$ induced by a
topological embedding of $C$ in the 3-sphere. Consider a 2-sphere of small
diameter around a vertex $v$. We may assume that each edge of $C$ intersects
this 2-sphere in at most one point and that each face intersects it in an
interval or not at all. The intersection of the 2-sphere and $C$ is a graph:
the link graph at $v$. Hence link graphs of 2-complexes with rotation systems
induced from embeddings in 3-space must always be planar. Even more is true:
the cyclic orientations $\sigma(e)$ at the edges of $C$ form – when projected
down to a link graph to rotators at the vertices of the link graph – a
rotation system at the link graph, see Figure 2.2.

Figure 2.2: The cyclic orientation $\sigma(e)$ of the faces incident with the
edge $e$ of $C$ projects down to rotators at $e$ in the link graphs at either
endvertex of $e$. In these link graphs, the projected rotators at $e$ are
reverse.

Next we shall define ‘planar rotation systems’ which roughly are rotation
systems satisfying such an additional property. The cyclic orientation
$\sigma(e)$ at the edge $e$ of a rotation system defines a rotation system
$r(e,v,\Sigma)$ at each vertex $e$ of a link graph $L(v)$: if the directed
edge $\vec{e}$ is directed towards $v$ we take $r(e,v,\Sigma)$ to be
$\sigma(e)$. Otherwise we take the reverse of $\sigma(e)$. As explained in
Section 2.3, this defines an embedding of the link graph into an oriented
surface. The _link complex_ for $(C,\Sigma)$ at the vertex $v$ is the cell
complex obtained from the link graph $L(v)$ by adding the faces of the above
embedding of $L(v)$ into the oriented surface. By definition, the geometric
realisation of the link complex is always a surface. To shortcut notation, we
will not distinguish between the link complex and its geometric realisation
and just say things like: ‘the link complex is a sphere’. A _planar rotation
system_ of a directed simplicial complex $C$ is a rotation system such that
for each vertex $v$ all link complexes are spheres – or disjoint unions of
spheres (if the link graph is not connected). The paragraph before shows the
following. We say that a simplicial complex $C$ is _locally connected_ if all
link graphs are connected.

######  Observation .

Rotation systems induced by topological embeddings of locally connected888
Section 2.4 is also true without the assumption of ‘local connectedness’. In
that case however the link complex is disconnected. Hence it is no longer
directly given by the drawing of the link graph on a ball of small radius as
above. simplicial complexes in the 3-sphere are planar. ∎

Next we will define the _local surfaces of a topological embedding_ of a
simplicial complex $C$ into $\operatorname{\mathbb{S}}^{3}$. The local surface
at a connected component of $\operatorname{\mathbb{S}}^{3}\setminus C$ is the
following. Pour concrete into this connected component. The surface of the
concrete is a 2-dimensional manifold. The local surface is the simplicial
complex drawn at the surface by the vertices, edges and faces of $C$. Note
that if an edge $e$ of $G$ is incident with more than two faces that are on
the surface, then the surface will contain at least two clones of the edge
$e$, see Figure 2.3.

Figure 2.3: On the left we depicted the torus with an additional face attached
on a genus reducing curve in the inside. On the right we depicted the local
surface of its inside component. It is a sphere and contains two copies of the
newly added face (and its incident edges).

Now we will define _local surfaces for a pair $(C,\Sigma)$_ consisting of a
complex $C$ and one of its rotation systems $\Sigma$. Section 2.4 below says
that under fairly general circumstances the local surfaces of a topological
embedding are the local surfaces of the rotation system induced by that
topological embedding. The set of faces of a local surface will be an
equivalence class of the set of orientations of faces of $C$. The _local-
surface-equivalence relation_ is the symmetric transitive closure of the
following relation. An orientation $\vec{f}$ of a face $f$ is _locally
related_ via an edge $e$ of $C$ to an orientation $\vec{g}$ of a face $g$ if
$f$ is just before $g$ in $\sigma(e)$ and $e$ is traversed positively by
$\vec{f}$ and negatively by $\vec{g}$ and in $\sigma(e)$ the faces $f$ and $g$
are adjacent. Here we follow the convention that if the edge $e$ is only
incident with a single face, then the two orientations of that face are
related via $e$. Given an equivalence class of the local-surface-equivalence
relation, the _local surface_ at that equivalence class is the following
complex whose set of faces is (in bijection with) the set of orientations in
that equivalence class. We obtain the complex from the disjoint union of the
faces of these orientations by gluing together two of these faces $f_{1}$ and
$f_{2}$ along two of their edges if these edges are copies of the same edge
$e$ of $C$ and $f_{1}$ and $f_{2}$ are related via $e$. Of course, we glue
these two edges in a way that endvertices are identified only with copies of
the same vertex of $C$. Hence each edge of a local surface is incident with
precisely two faces. Hence its geometric realisation is always a is a surface.
Similarly as for link complexes, we shall just say things like ‘the local
surface is a sphere’.

######  Observation .

Local surfaces of planar rotation systems are always connected. ∎

A _(2-dimensional) orientation_ of a complex $C$ such that each edge is in
precisely two faces is a choice of orientation of each face of $C$ such that
each edge is traversed in opposite directions by the chosen orientation of the
two incident faces. Note that a complex whose geometric realisation is a
surface has an orientation if and only its geometric realisation is
orientable.

######  Observation .

The set of orientations in a local-surface-equivalence class defines an
orientation of its local surface.

In particular, local surfaces are cell complexes. ∎

We will not use the following lemma in our proof of Theorem 2.2.1 However, we
think that it gives a better intuitive understanding of local surfaces.

######  Lemma .

Let $C$ be a connected and locally connected complex embedded into
$\operatorname{\mathbb{S}}^{3}$ and let $\Sigma$ be the induced planar
rotation system. Then the local surfaces of the topological embedding are
equal to the local surfaces for $(C,\Sigma)$.∎

There is the following relation between vertices of local surfaces and faces
of link complexes.

######  Lemma .

Let $\Sigma$ be a rotation system of a simplicial complex $C$. There is a
bijection $\iota$ between the set of vertices of local surfaces for
$(C,\Sigma)$ and the set of faces of link complexes for $(C,\Sigma)$, which
maps each vertex $v^{\prime}$ of a local surface cloned from the vertex $v$ of
$C$ to a face $f$ of the link complex at $v$ such that the rotation system at
$v^{\prime}$ is an orientation of $f$.

###### Proof.

The set of faces of the link complex at $v$ is in bijection with the set of
$v$-equivalence classes; here the _$v$ -equivalence relation_ on the set of
orientations of faces of $C$ incident with $v$ is the symmetric transitive
closure of the relation ‘locally related’. Since we work in a subset of the
orientations, every $v$-equivalence class is contained in a local-surface-
equivalence class. On the other hand the set of all clones of a vertex $v$ of
$C$ contained in a local surface $S$ is in bijection with the set of
$v$-equivalence classes contained in the local-surface-equivalence class of
$S$. This defines a bijection $\iota$ between the set of vertices of local
surfaces for $(C,\Sigma)$ and the set of faces of link complexes for
$(C,\Sigma)$.

It is straightforward to check that $\iota$ has all the properties claimed in
the lemma. ∎

######  Corollary .

Given a local surface of a simplicial complex $C$ and one of its vertices
$v^{\prime}$ cloned from a vertex $v$ of $C$, there is a homeomorphism from a
neighbourhood around $v^{\prime}$ in the local surface to the cone with top
$v^{\prime}$ over the face boundary of $\iota(v^{\prime})$ that fixes
$v^{\prime}$ and the edges and faces incident with $v^{\prime}$ in a
neighbourhood around $v^{\prime}$. ∎

The definitions of link graphs and link complexes can be generalised from
simplicial complexes to complexes as follows. The _link graph_ of a complex
$C$ at a vertex $v$ is the graph whose vertices are the edges incident with
$v$. For any traversal of a face of the vertex $v$, we add an edge between the
two vertices that when considered as edges of $C$ are in the face just before
and just after that traversal of $v$. We stress that we allow parallel edges
and loops. Given a complex $C$, any rotation system $\Sigma$ of $C$ defines
rotation systems at each link graph of $C$. Hence the definition of link
complex extends.

###  2.5 Constructing piece-wise linear embeddings

In this section we prove Theorem 2.5.1 below, which is used in the proof of
Theorem 2.2.1.

Figure 2.4: A cylinder with an embedded 2-complex.

######  Example .

Here we give the definition of the Solid Klein Bottle and construct an
embedding of a 2-complex $C$ in the Solid Klein Bottle that does not induce a
planar rotation system.

Given a solid cylinder (see Figure 2.4), there are two ways to identify the
bounding discs: one way the boundary becomes a torus and the other way the
boundary becomes a Klein Bottle. We refer to the topological space obtained
from the solid cylinder by identifying as in the second case as the _Solid
Klein Bottle_. In Figure 2.4 we embedded a 2-complex in the solid cylinder.
Extending the above identification of the cylinder to the embedded 2-complex,
induces an embedding of this new 2-complex in the Solid Klein Bottle. This
embedding does not induce a planar rotation system.

Next we show that the Solid Klein Bottle is the only obstruction that prevents
embeddings of 2-complexes in 3-manifolds to induce planar rotation systems.

######  Lemma .

Let $M$ be a 3-manifold that does not include the Solid Klein Bottle as a
submanifold. Then any embedding of a 2-complex $C$ in $M$ induces a planar
rotation system.

###### Proof.

By treating different connected components separately, we may assume that $C$
is connected. Around each vertex of $C$ we pick a small neighbourhood that is
an open 3-ball, and around each edge of $C$ we pick a small neighbourhood that
is an open cylinder. Next we define orientations on these neighbourhoods. For
that we pick an arbitrary vertex and pick for its neighbourhood one of the two
orientations arbitrarily. Then we pick compatible orientations at the
neighbourhoods of the incident edges. As $C$ is connected, we can continue
recursively along a spanning tree of $C$ until we picked orientations at all
neighbourhoods of vertices and edges. If for a vertex and an incident edge,
their neighbourhoods have incompatible orientations, this edge must be outside
the spanning tree and we can build a Solid Klein Bottle from its fundamental
cycle as follows. Indeed, sticking together the balls at the vertices and the
cylinders at the edges gives a Solid Klein Bottle. By assumption, this does
not occur, so all orientations of neighbourhoods are compatible.

Let $\Sigma$ be the rotation system induced by this embedding of $C$ in $M$
with respect to the orientations chosen above. Clearly, this rotations system
$\Sigma$ is planar. ∎

######  Corollary .

Any embedding of a 2-complex $C$ in an orientable 3-manifold $M$ induces a
planar rotation system.

###### Proof.

It is well-known that a 3-manifold is orientable if and only if it does not
have the Solid Klein Bottle as a submanifold. Hence Section 2.5 follows from
Section 2.5. ∎

Throughout this section we fix a connected and locally connected simplicial
complex $C$ with a rotation system $\Sigma$. An associated topological space
$T(C,\Sigma)$ is defined as follows. For each local surface $S$ of
$(C,\Sigma)$ we take an embedding into $\operatorname{\mathbb{S}}^{3}$ as
follows. Let $g$ be the genus of $S$. We start with the unit ball in
$\operatorname{\mathbb{S}}^{3}$ and then identify $g$ disjoint pairs of discs
through the outside.999We have some flexibility along which paths on the
outside we do these identifications but we do not need to make particular
choices for our construction to work. The constructed surface is isomorphic to
$S$, so this defines an embedding of $S$. Each local surface is oriented and
we denote by $\hat{S}$ the topological space obtained from
$\operatorname{\mathbb{S}}^{3}$ by deleting all points on the outside of $S$.
For each local surface $S$, let $\varphi_{S}$ be the map which maps every cell
of $S$ to the cell of $C$ it is cloned from.

######  Example .

If the map $\varphi_{S}$ is injective, then $S$ is a subcomplex of $C$. By
taking 3-dimensional baricentric subdivisions, one could ensure that the maps
$\varphi_{S}$ are injective. However, our proof below also goes through
smoothly without any injectivity assumptions.

We obtain $T(C,\Sigma)$ from the simplicial complex $C$ by gluing101010Given a
map $f$ from a topological space $X$ to a topological space $Y$, the space
obtained from $Y$ by gluing $X$ via $f$ is the following topological space.
Its point set is obtained from the disjoint union of $X$ and $Y$ by factoring
out the equivalence relation generated from $f$, where $x\in X$ and $y\in Y$
are related if $f(x)=y$. The topology of this space is defined through the
universal property that it is the densest topology such that the injection
from $X$ into this space and the lift of $f$ into this space are continuous.
onto each local surface $S$ the topological space $\hat{S}$ along $S$ via
$\varphi_{S}$.

We remark that associated topological spaces may depend on the chosen
embeddings of the local surfaces $S$ into $\operatorname{\mathbb{S}}^{3}$.
However, if all local surfaces are spheres, then any two associated
topological spaces are isomorphic and in this case we shall talk about ‘the’
associated topological space.

Clearly, associated topological spaces $T(C,\Sigma)$ are compact and connected
as $C$ is connected.

######  Lemma .

The rotation system $\Sigma$ is planar if and only if the associated
topological space $T(C,\Sigma)$ is an oriented 3-dimensional manifold.

###### Proof.

Section 2.5 implies that if the topological space $T(C,\Sigma)$ is a
3-dimensional orientable 3-manifold, then the rotation system $\Sigma$ is
planar. Conversely, now assume that $\Sigma$ is a planar rotation system. We
have to show that the topological space $T(C,\Sigma)$ is an orientable
3-manifold. It suffices to show that $T(C,\Sigma)$ is a 3-manifold since then
orientability follows immediately from the construction of $T(C,\Sigma)$. So
we are to show that there is a neighbourhood around any point $x$ of
$T(C,\Sigma)$ that is isomorphic to the closed 3-dimensional ball $B_{3}$.

If $x$ is a point not in $C$, this is clear. If $x$ is an interior point of a
face $f$, we obtain a neighbourhood of $x$ by gluing together neighbourhoods
of copies of $x$ in the local surfaces that contain an orientation of $f$.
Each orientation of $f$ is contained in local surfaces exactly once. Hence we
glue together the two orientations of $f$ and clearly $x$ has a neighbourhood
isomorphic to $B_{3}$.

Next we assume that $x$ is an interior point of an edge $e$. Some open
neighbourhood of $x$ is isomorphic to the topological space obtained from
gluing together for each copy of $e$ in a local surface, a neighbourhood
around a copy $x^{\prime}$ of $x$ on those edges. A neighbourhood around
$x^{\prime}$ has the shape of a piece of a cake, see Figure 2.5

Figure 2.5: A piece of a cake. This space is obtained by taking the product of
a triangle with the unit interval. The edge $e$ is mapped to the set of points
corresponding to some vertex of the triangle.

First we consider the case that $x$ has several copies. As $\sigma(e)$ is a
cyclic orientation, these pieces of a cake are glued together in a cyclic way
along faces. Since each cyclic orientation of a face appears exactly once in
local surfaces, we identify in each gluing step the two cyclic orientations of
a face. Informally, the overall gluing will be a ‘cake’ with $x$ as an
interior point. Hence a neighbourhood of $x$ is isomorphic to $B_{3}$. If
there is only one copy of $x^{\prime}$, then the copy of $e$ containing
$x^{\prime}$ is incident with the two orientations of a single face. Then we
obtain a neighbourhood of $x$ by identifying these two orientations. Hence
there is a neighbourhood of $x$ isomorphic to $B_{3}$.

It remains to consider the case where $x$ is a vertex of $C$. We obtain a
neighbourhood of $x$ by gluing together neighbourhoods of copies of $x$ in
local surfaces. We shall show that we have one such copy for every face of the
link complex for $(C,\Sigma)$ and a neighbourhood of $x$ in such a copy is
given by the cone over that face with $x$ being the top of the cone, see
Figure 2.6.

Figure 2.6: In this example the link complex of $x$ is a tetrahedron. The
three faces visible in our drawing are highlighted in red, gold and grey. On
the left we see how the four cones over the faces of the link complex are
pasted together to form the cone over the link complex depicted on the right.

We shall show that the glued together neighbourhood is the cone over the link
complex with $x$ at the top. Since $\Sigma$ is planar and $C$ is locally
connected, the link complex is isomorphic to the 2-sphere. Since the cone over
the 2-sphere is a 3-ball, the neighbourhood of $x$ has the desired type.

Now we examine this plan in detail. By Section 2.4 and Section 2.4, the copies
are mapped by the bijection $\iota$ to the faces of the link complex at $x$
and a neighbourhood around such a copy $x^{\prime}$ is isomorphic to the cone
with top $x^{\prime}$ over the face $\iota(x^{\prime})$. We glue these cones
over the faces $\iota(x^{\prime})$ on their faces that are obtained from edges
of $\iota(x^{\prime})$ by adding the top $x^{\prime}$.

The glued together complex is isomorphic to the cone over the complex $S$
obtained by gluing together the faces $\iota(x^{\prime})$ along edges, where
we always glue the edge the way round so that copies of the same vertex of the
local incidence graph are identified. Hence the vertex-edge-incidence relation
and the edge-face-incidence relation of $S$ are the same as for the link
complex at $x$. The same is true for the cyclic orderings of edges on faces.
So $S$ is equal to the link complex at $x$.

Hence a neighbourhood of $x$ is isomorphic to a cone with top $x$ over the
link complex at $x$. Since $\Sigma$ is a planar rotation system, the link
complex is a disjoint union of spheres. As $C$ is locally connected, it is a
sphere. Thus its cone is isomorphic to $B_{3}$. ∎

######  Lemma .

If $C$ is simply connected, then any associated topological space
$T(C,\Sigma)$ is simply connected.

###### Proof.

This is a consequence of Van Kampen’s Theorem [18, Theorem 1.20]. Indeed, we
obtain $T$ from $T(C,\Sigma)$ by deleting all interior points of the sets
$\hat{S}$ for local surfaces $S$ that are not in a small open neighbourhood of
$C$. This can be done in such a way that $T$ has a deformation retract to $C$,
and thus is simply connected. Now we recursively glue the spaces $\hat{S}$
back onto $T$. In each step we glue a single space $\hat{S}$. Call the space
obtained after $n$ gluings $T_{n}$.

The fundamental group of $\hat{S}$ is a quotient of the fundamental group of
the topological space that is the intersection of $T_{n}$ and $\hat{S}$ (this
follows from the construction of the embedding of the surface $S$ into the
space $\hat{S}$). The fundamental group of $T_{n}$ is trivial by induction. So
we can apply Van Kampen’s Theorem to deduce that the gluing space $T_{n+1}$
has trivial fundamental group. Hence the final gluing space $T(C,\Sigma)$ has
trivial fundamental group. So it is simply connected. ∎

The converse of Section 2.5 is true if all local surfaces for $(C,\Sigma)$ are
spheres as follows.

######  Lemma .

If all local surfaces for $(C,\Sigma)$ are spheres and the associated
topological space $T(C,\Sigma)$ is simply connected, then $C$ is simply
connected.

###### Proof.

Let $\varphi$ an image of $\operatorname{\mathbb{S}}^{1}$ in $C$. Since
$T(C,\Sigma)$ is simply connected, there is a homotopy from $\varphi$ to a
point of $C$ in $T(C,\Sigma)$. We can change the homotopy so that it avoids an
interior point of each local surface of the embedding. Since each local
surface is a sphere, for each local surface without the chosen point there is
a continuous projection to its boundary. Since these projections are
continuous, the concatenation of them with the homotopy is continuous. Since
this concatenation is constant on $C$ this defines a homotopy of $\varphi$
inside $C$. Hence $C$ is simply connected. ∎

We conclude this section with the following special case of Theorem 2.2.1.

######  Theorem 2.5.1.

Let $\Sigma$ be a rotation system of a locally connected simplicial complex
$C$. Then $\Sigma$ is planar if and only if $T(C,\Sigma)$ is an oriented
3-manifold. Furthermore, if $\Sigma$ is planar and $C$ is simply connected,
then $T(C,\Sigma)$ must be the 3-sphere.

###### Proof.

By treating different connected components separately, we may assume that $C$
is connected. The first part follows from Section 2.5. The second part follows
from Section 2.5 and Perelman’s theorem [30, 32, 31] that any compact simply
connected 3-manifold is isomorphic to the 3-sphere. ∎

######  Remark .

We used Perelman’s theorem in the proof of Theorem 2.5.1. On the other hand it
together with Moise’s theorem [26], which says that every compact
3-dimensional manifold has a triangulation, implies Perelman’s theorem in the
orientable case as follows. Let $M$ be a simply connected oriented
3-dimensional compact manifold. Let $T$ be a triangulation of $M$, and let $C$
be the simplicial complex obtained from $T$ by deleting the 3-dimensional
cells (recall that 3-dimensional cells of a triangulation are homeomorphic to
closed 3-balls). Since $M$ is orientable, there is a rotation system given by
the embedding of $C$ into $T$; denote it by $\Sigma$. It is clear from that
construction that $T$ is equal to the triangulation given by the embedding of
$C$ into $T(C,\Sigma)$. Hence we can apply Section 2.5 to deduce that $C$ is
simply connected. Hence by Theorem 2.5.1 the topological space $T(C,\Sigma)$,
into which $C$ embeds, is isomorphic to the 3-sphere. Since $T(C,\Sigma)$ is
isomorphic to $M$, we deduce that $M$ is isomorphic to the 3-sphere. We will
not use this remark in our proofs.

###  2.6 Cut vertices

In this section we deduce Theorem 2.2.1 from Theorem 2.5.1 proved in the last
section. Given a prime $p$, a simplicial complex $C$ is _$p$ -nullhomologous_
if every directed cycle of $C$ is generated over ${\mathbb{F}}_{p}$ by the
boundaries of faces of $C$. Note that a simplicial complex $C$ is
$p$-nullhomologous if and only if the first homology group
$H_{1}(C,{\mathbb{F}}_{p})$ is trivial. Clearly, every simply connected
simplicial complex is $p$-nullhomologous.

A vertex $v$ in a connected complex $C$ is a _cut vertex_ if the 1-skeleton of
$C$ without $v$ is a disconnected graph111111We define this in terms of the
1-skeleton instead of directly in terms of $C$ for a technical reason: The
object obtained from a simplicial complex by deleting a vertex may have edges
not incident with faces. So it would not be a 2-dimensional simplicial complex
in the terminology of this paper.. A vertex $v$ in an arbitrary, not
necessarily connected, complex $C$ is _a cut vertex_ if it is a cut vertex in
a connected component of $C$.

######  Lemma .

Every $p$-nullhomologous simplicial complex without a cut vertex is locally
connected.

###### Proof.

We construct for any vertex $v$ of an arbitrary simplicial complex $C$ such
that the link graph $L(v)$ at $v$ is not connected and $v$ is not a cut vertex
a cycle containing $v$ that is not generated by the face boundaries of $C$.

Let $e$ and $g$ be two vertices in different components of $L(v)$. These are
edges of $C$ and let $w$ and $u$ be their endvertices different from $v$.
Since $v$ is not a cut vertex, there is a path in $C$ between $u$ and $w$ that
avoids $v$. This path together with the edges $e$ and $g$ is a cycle $o$ in
$C$ that contains $v$.

Our aim is to show that $o$ is not generated by the boundaries of faces of
$C$. Suppose for a contradiction that $o$ is generated. Let $F$ be a family of
faces whose boundaries sum up to $o$. Let $F_{v}$ be the subfamily of faces of
$F$ that are incident with $v$. Each face in $F_{v}$ is an edge of $L(v)$ and
each vertex of $L(v)$ is incident with an even number (counted with
multiplicities) of these edges except for $e$ and $g$ that are incident with
an odd number of these faces. Let $X$ be the connected component of the graph
$L(v)$ restricted to the edge set $F_{v}$ that contains the vertex $e$. We
obtain $X^{\prime}$ from $X$ by adding $k-1$ parallel edges to each edge that
appears $k$ times in $F_{v}$. Since $X^{\prime}$ has an even number of
vertices of odd degree also $g$ must be in $X$. This is a contradiction to the
assumption that $e$ and $g$ are in different components of $L(v)$. Hence $o$
is not generated by the boundaries of faces of $C$. This completes the proof.
∎

Given a connected complex $C$ with a cut vertex $v$ and a connected component
$K$ of the 1-skeleton of $C$ with $v$ deleted, the _complex attached_ at $v$
centered at $K$ has vertex set $K+v$ and its edges and faces are those of $C$
all of whose incident vertices are in $K+v$.

######  Lemma .

A connected simplicial complex $C$ with a cut vertex $v$ has a piece-wise
linear embedding into $\operatorname{\mathbb{S}}^{3}$ if and only if all
complexes attached at $v$ have a piece-wise linear embedding into
$\operatorname{\mathbb{S}}^{3}$.

###### Proof.

If $C$ has an embedding into $\operatorname{\mathbb{S}}^{3}$, then clearly all
complexes attached at $v$ have an embedding. Conversely suppose that all
complexes attached at $v$ have an embedding into
$\operatorname{\mathbb{S}}^{3}$. Pick one of these complexes arbitrarily, call
it $X$ and fix an embedding of it into $\operatorname{\mathbb{S}}^{3}$. In
that embedding pick for each component of $C$ remove $v$ except that for $X$ a
closed ball contained in $\operatorname{\mathbb{S}}^{3}$ that intersects $X$
precisely in $v$ such that all these closed balls intersect pairwise only at
$v$. Each complex attached at $v$, has a piece-wise linear embedding into the
3-dimensional unit ball as they have embeddings into
$\operatorname{\mathbb{S}}^{3}$ such that some open set is disjoint from the
complex. Now we attach these embeddings into the balls of the embedding of $X$
inside the reserved balls by identifying the copies of $v$. This defines an
embedding of $C$. ∎

Recall that in order to prove Theorem 2.2.1 it suffices to show that any
simply connected simplicial complex $C$ has a piece-wise linear embedding into
$\operatorname{\mathbb{S}}^{3}$ if and only if $C$ has a planar rotation
system.

###### Proof of Theorem 2.2.1..

Clearly if a simplicial complex is embeddable into
$\operatorname{\mathbb{S}}^{3}$, then it has a planar rotation system. For the
other implication, let $C$ be a simply connected simplicial complex and
$\Sigma$ be a planar rotation system. We prove the theorem by induction on the
number of cut vertices of $C$. If $C$ has no cut vertex, it is locally
connected by Section 2.6. Thus it has a piece-wise linear embedding into
$\operatorname{\mathbb{S}}^{3}$ by Theorem 2.5.1.

Hence we may assume that $C$ has a cut vertex $v$. As $C$ is simply connected,
every complex attached at $v$ is simply connected. Hence by the induction
hypothesis each of these complexes has a piece-wise linear embedding into
$\operatorname{\mathbb{S}}^{3}$. Thus $C$ has a piece-wise linear embedding
into $\operatorname{\mathbb{S}}^{3}$ by Section 2.6. ∎

###  2.7 Local surfaces of planar rotation systems

The aim of this section is to prove Theorem 2.2.2. A shorter proof is sketched
in Section 2.7 using algebraic topology. As a first step in that direction, we
first prove the following.

######  Theorem 2.7.1.

Let $C$ be a locally connected $p$-nullhomologous simplicial complex that has
a planar rotation system. Then all local surfaces of the planar rotation
system are spheres.

Before we can prove Theorem 2.7.1 we need some preparation. The complex _dual_
to a simplicial $C$ with a rotation system $\Sigma$ has as its set of vertices
the set of local surfaces of $\Sigma$. Its set of edges is the set of faces of
$C$, and an edge is incident with a vertex if the corresponding face is in the
corresponding local surface. The faces of the dual are the edges of $C$. Their
cyclic ordering is as given by $\Sigma$. In particular, the edge-face-
incidence-relation of the dual is the same as that of $C$ but with the roles
of edges and faces interchanged.

Moreover, an orientation $\vec{f}$ of a face $f$ of $C$ corresponds to the
direction of $f$ when considered as an edge of the dual complex $D$ that
points towards the vertex of $D$ whose local-surface-equivalence class
contains $\vec{f}$. Hence the direction of the dual complex $C$ induces a
direction of the complex $D$. By $\Sigma_{C}=(\sigma_{C}(f)|f\in E(D))$ we
denote the following rotation system for $D$: for $\sigma_{C}(f)$ we take the
orientation $\vec{f}$ of $f$ in the directed complex $C$.

In this paper we follow the convention that for edges of $C$ we use the letter
$e$ (with possibly some subscripts) while for faces of $C$ we use the letter
$f$. In return, we use the letter $f$ for the edges of a dual complex of $C$
and $e$ for its faces.

######  Lemma .

Let $C$ be a connected and locally connected simplicial complex. Then for any
rotation system, the dual complex $D$ is connected.

###### Proof.

Two edges of $C$ are _$C$ -related_ if there is a face of $C$ incident with
both of them. They are _$C$ -equivalent_ if they are in the transitive closure
of the symmetric relation ‘$C$-related’. Clearly, any two $C$-equivalent edges
of $C$ are in the same connected component. If $C$ however is locally
connected, also the converse is true: any two edges in the same connected
component are $C$-equivalent. Indeed, take a path containing these two edges.
Any two edges incident with a common vertex are $C$-equivalent as $C$ is
locally connected. Hence any two edges on the path are $C$-equivalent.

We define _$D$ -equivalent_ like ‘$C$-equivalent’ with ‘$D$’ in place of
‘$C$’. Now let $f$ and $f^{\prime}$ be two edges of $D$. Let $e$ and
$e^{\prime}$ be edges of $C$ incident with $f$ and $f^{\prime}$, respectively.
Since $C$ is connected and locally connected the edges $e$ and $e^{\prime}$
are $C$-equivalent. As $C$ and $D$ have the same edge/face incidence relation,
the edges $f$ and $f^{\prime}$ of $D$ are $D$-equivalent. So any two edges of
$D$ are $D$-equivalent. Hence $D$ is connected. ∎

First, we prove the following, which is reminiscent of euler’s formula.

######  Lemma .

Let $C$ be a locally connected $p$-nullhomologous simplicial complex with a
planar rotation system and $D$ the dual complex. Then

$|V(C)|-|E|+|F|-|V(D)|\geq 0$

Moreover, we have equality if and only if $D$ is $p$-nullhomologous.

###### Proof.

Let $Z_{C}$ be the dimension over ${\mathbb{F}}_{p}$ of the cycle space of
$C$. Similarly we define $Z_{D}$. Let $r$ be the rank of the edge-face-
incidence matrix over ${\mathbb{F}}_{p}$. Note that $r\leq Z_{D}$ and that
$r=Z_{C}$ as $H_{1}(C,{\mathbb{F}}_{p})=0$. So $Z_{D}-Z_{C}\geq 0$. Hence it
suffices to prove the following.

######  Claim .

$|V(C)|-|E|+|F|-|V(D)|=Z_{D}-Z_{C}$

Proof of Claim. Let $k_{C}$ be the number of connected components of $C$ and
$k_{D}$ be the number of connected components of $D$. Recall that the space
orthogonal to the cycle space (over ${\mathbb{F}}_{p}$) in a graph $G$ has
dimension $|V(G)|$ minus the number of connected components of $G$. Hence
$Z_{C}=|E|-|V(C)|+k_{C}$ and $Z_{D}=|F|-|V(D)|+k_{D}$. Subtracting the first
equation from the second yields:

$|V(C)|-|E|+|F|-|V(D)|+(k_{D}-k_{C})=Z_{D}-Z_{C}$

Since the dual complex of the disjoint union of two simplicial complexes (with
planar rotation systems) is the disjoint union of their dual complexes,
$k_{C}\leq k_{D}$. By Section 2.7 $k_{C}=k_{D}$. Plugging this into the
equation before, proves the claim. ! $\diamondsuit$

This completes the proof of the inequality. We have equality if and only if
$r=Z_{D}$. So the ‘Moreover’-part follows. ∎

Our next goal is to prove the following, which is also reminiscent of euler’s
formula but here the inequality goes the other way round.

######  Lemma .

Let $C$ be a locally connected simplicial complex with a planar rotation
system $\Sigma$ and $D$ the dual complex. Then:

$|V(C)|-|E|+|F|-|V(D)|\leq 0$

with equality if and only if all link complexes for $(D,\Sigma_{C})$ are
spheres.

Before we can prove this, we need some preparation. By $a$ we denote the sum
of the faces of link complexes for $(C,\Sigma)$. By $a^{\prime}$ we denote the
sum over the faces of link complexes for $(D,\Sigma_{C})$. Before proving that
$a$ is equal to $a^{\prime}$ we prove that it is useful by showing the
following.

######  Fact .

Section 2.7 is true if $a=a^{\prime}$ and all link complexes for
$(D,\Sigma_{C})$ are connected.

###### Proof.

Given a face $f$ of $C$, we denote the number of edges incident with $f$ by
$deg(f)$. Our first aim is to prove that

$2|V(C)|=2|E|-\sum_{f\in F}\operatorname{deg}(f)+a$ (2.1)

To prove this equation, we apply Euler’s formula [11] in the link complexes
for $(C,\Sigma)$. Then we take the sum of all these equations over all $v\in
V(C)$. Since $\Sigma$ is a planar rotation system, all link complexes are a
disjoint union of spheres. Since $C$ is locally connected, all link complexes
are connected and hence are spheres. So they have euler characteristic two.
Thus we get the term $2|V(C)|$ on the left hand side. By definition, $a$ is
the sum of the faces of link complexes for $(C,\Sigma)$.

The term $2|E|$ is the sum over all vertices of link complexes for
$(C,\Sigma)$. Indeed, each edge of $C$ between the two vertices $v$ and $w$ of
$C$ is a vertex of precisely the two link complexes for $v$ and $w$.

The term $\sum_{f\in F}\operatorname{deg}(f)$ is the sum over all edges of
link complexes for $(C,\Sigma)$. Indeed, each face $f$ of $C$ is in precisely
those link complexes for vertices on the boundary of $f$. This completes the
proof of (2.1).

Secondly, we prove the following inequality using a similar argument. Given an
edge $e$ of $C$, we denote the number of faces incident with $e$ by
$\operatorname{deg}(e)$.

$2|V(D)|\geq 2|F|-\sum_{e\in E}\operatorname{deg}(e)+a^{\prime}$ (2.2)

To prove this, we apply Euler’s formula in link complexes for
$(D,\Sigma_{C})$, and take the sum over all $v\in V(D)$. Here we have ‘$\geq$’
instead of ‘$=$’ as we just know by assumption that the link complexes are
connected but they may not be a sphere. So we have $2|V(D)|$ on the left and
$a^{\prime}$ is the sum over the faces of link complexes for $(D,\Sigma_{C})$.

The term $2|F|$ is the sum over all vertices of link complexes for
$(D,\Sigma_{C})$. Indeed, each edge of $D$ between the two different vertices
$v$ and $w$ of $D$ is a vertex of precisely the two link complexes for $v$ and
$w$. A loop gives rise to two vertices in the link graph at the vertex it is
attached to.

The term $\sum_{e\in E}\operatorname{deg}(e)$ is the sum over all edges of
link complexes for $(D,\Sigma_{C})$. Indeed, each face $e$ of $D$ is in the
link complex at $v$ with multiplicity equal to the number of times it
traverses $v$. This completes the proof of (2.2).

By assumption, $a=a^{\prime}$. The sums $\sum_{f\in F}\operatorname{deg}(f)$
and $\sum_{e\in E}\operatorname{deg}(e)$ both count the number of nonzero
entries of $A$, so they are equal. Subtracting (2.2) from (2.1), rearranging
and dividing by 2 yields:

$|V(C)|-|E|+|F|-|V(D)|\leq 0$

with equality if and only if all link complexes for $(D,\Sigma_{C})$ are
spheres. ∎

Hence our next aim is to prove that $a$ is equal to $a^{\prime}$. First we
need some preparation.

Two cell complexes $C$ and $D$ are _(abstract) surface duals_ if the set of
vertices of $C$ is (in bijection with) the set of faces of $D$, the set of
edges of $C$ is the set of edges of $D$ and the set of faces of $C$ is the set
of vertices of $D$. These three bijections preserve incidences.

######  Lemma .

Let $C$ be a simplicial complex and $\Sigma$ be a rotation system and let $D$
be the dual. The surface dual of a local surface $S$ for $(C,\Sigma)$ is equal
to the link complex for $(D,\Sigma_{C})$ at the vertex $\ell$ of $D$ that
corresponds to $S$.

###### Proof.

It is immediate from the definitions that the vertices of the link complex
$\bar{L}$ at $\ell$ are the faces of $S$. The edges of $S$ are triples
$(e,\vec{f},\vec{g})$, where $e$ is an edge of $C$ and $\vec{f}$ and $\vec{g}$
are orientations of faces of $C$ that are related via $e$ and are in the
local-surface-equivalence class for $S$. Hence in $D$, these are triples
$(e,\vec{f},\vec{g})$ such that $\vec{f}$ and $\vec{g}$ are directions of
edges that point towards $\ell$ and $f$ and $g$ are adjacent in the cyclic
ordering of the face $e$. This are precisely the edges of the link graph
$L(\ell)$. Hence the link graph $L(\ell)$ is the dual graph121212 The _dual
graph_ of a cell complex $C$ is the graph $G$ whose set of vertices is (in
bijection with) the set of faces of $C$ and whose set of edges is the set of
edges of $C$. The incidence relation between the vertices and edges of $G$ is
the same as the incidence relation between the faces and edges of $C$. of the
cell complex $S$.

Now we will use the Edmonds-Hefter-Ringel rotation principle, see [25, Theorem
3.2.4], to deduce that the link complex $\bar{L}$ at $\ell$ is the surface
dual of $S$. We denote the unique cell complex that is a surface dual of $S$
by $S^{*}$. Above we have shown that $\bar{L}$ and $S^{*}$ have the same
1-skeleton. Moreover, the rotation systems at the vertices of the link complex
$\bar{L}$ are given by the cyclic orientations in the local-surface-
equivalence class for $S$. By Section 2.4 these local-surface-equivalence
classes define an orientation of $S$. So $\bar{L}$ and $S^{*}$ have the same
rotation systems. Hence by the Edmonds-Hefter-Ringel rotation principle
$\bar{L}$ and $S^{*}$ have to be isomorphic. So $\bar{L}$ is a surface dual of
$S$. ∎

###### Proof of Section 2.7..

Let $C$ be a locally connected simplicial complex and $\Sigma$ be a rotation
system and let $D$ be the dual. Let $\Sigma_{C}$ be as defined above. By
Section 2.4 and Section 2.7 every link complex for $(D,\Sigma_{C})$ is
connected. By Section 2.7, it suffices to show that the sum over all faces of
link complexes of $C$ with respect to $\Sigma$ is equal to the sum over all
faces of link complexes for $D$ with respect to $\Sigma_{C}$. By Section 2.7,
the second sum is equal to the sum over all vertices of local surfaces for
$(C,\Sigma)$. This completes the proof by Section 2.4. ∎

###### Proof of Theorem 2.7.1..

Let $C$ be a $p$-nullhomologous locally connected simplicial complex that has
a planar rotation system $\Sigma$. Let $D$ be the dual complex. Then by
Section 2.7 and Section 2.7, $C$ and $D$ satisfy Euler’s formula, that is:

$|V(C)|-|E|+|F|-|V(D)|=0$

Hence by Section 2.7 all link complexes for $(D,\Sigma_{C})$ are spheres. By
Section 2.7 these are dual to the local surfaces for $(C,\Sigma)$. Hence all
local surfaces for $(C,\Sigma)$ are spheres. ∎

The following theorem gives three equivalent characterisations of the class of
locally connected simply connected simplicial complexes embeddable in
$\operatorname{\mathbb{S}}^{3}$.

######  Theorem 2.7.2.

Let $C$ be a locally connected simplicial complex embedded into
$\operatorname{\mathbb{S}}^{3}$. The following are equivalent.

  1. 1.

$C$ is simply connected;

  2. 2.

$C$ is $p$-nullhomologous for some prime $p$;

  3. 3.

all local surfaces of the planar rotation system induced by the topological
embedding are spheres.

###### Proof.

Clearly, 1 implies 2. To see that 2 implies 3, we assume that $C$ is
$p$-nullhomologous. Let $\Sigma$ be the planar rotation system induced by the
topological embedding of $C$ into $\operatorname{\mathbb{S}}^{3}$. By Theorem
2.7.1 all local surfaces for $(C,\Sigma)$ are spheres.

It remains to prove that 3 implies 1. So assume that $C$ has an embedding into
$\operatorname{\mathbb{S}}^{3}$ such that all local surfaces of the planar
rotation system induced by the topological embedding are spheres. By treating
different connected components separately, we may assume that $C$ is
connected. By Section 2.4 all local surfaces of the topological embedding are
spheres. Thus 3 implies 1 by Section 2.5.

∎

######  Remark .

Our proof actually proves the strengthening of Theorem 2.7.2 with ‘embedded
into $\operatorname{\mathbb{S}}^{3}$’ replaced by ‘embedded into a simply
connected oriented 3-dimensional compact manifold.’ However this strengthening
is equivalent to Theorem 2.7.2 by Perelman’s theorem.

Recall that in order to prove Theorem 2.2.2, it suffices to show that every
$p$-nullhomologous simplicial complex $C$ has a piece-wise linear embedding
into $\operatorname{\mathbb{S}}^{3}$ if and only if it is simply connected and
$C$ has a planar rotation system.

###### Proof of Theorem 2.2.2..

Using an induction argument on the number of cut vertices as in the proof of
Theorem 2.2.1, we may assume that $C$ is locally connected. If $C$ has a
piece-wise linear embedding into $\operatorname{\mathbb{S}}^{3}$, then it has
a planar rotation system and it is simply connected by Theorem 2.7.2. The
other direction follows from Theorem 2.2.1. ∎

######  Remark .

One step in proving Theorem 2.2.2 was showing that if a simplicial complex
with trivial first homology group embeds in $\operatorname{\mathbb{S}}^{3}$,
then it must be simply connected. In this section we have given a proof that
only uses elementary topology. We will use these methods again in [8].

However there is a shorter proof of this fact, which we shall sketch in the
following. Let $C$ be a simplicial complex embedded in
$\operatorname{\mathbb{S}}^{3}$ such that one local surface of the embedding