Lower Bounds for Planar Electrical Reduction∗
Hsien-Chih Chang

Jeff Erickson

University of Illinois at Urbana-Champaign
{hchang17, jeffe}@illinois.edu

arXiv:1707.04683v1 [cs.CG] 15 Jul 2017

Submitted to SODA 2018 — July 12, 2017

Abstract
We improve our earlier lower bounds on the number of electrical transformations required to
reduce an n-vertex plane graph in the worst case [SOCG 2016] in two different directions. Our
previous Ω(n3/2 ) lower bound applies only to facial electrical transformations on plane graphs with no
terminals. First we provide a stronger Ω(n2 ) lower bound when the graph has two or more terminals,
which follows from a quadratic lower bound on the number of homotopy moves in the annulus,
described in a companion paper. Our second result extends our earlier Ω(n3/2 ) lower bound to
the wider class of planar electrical transformations, which preserve the planarity of the graph but
may delete cycles that are not faces of the given embedding. This new lower bound follows from
the observation that the defect of the medial graph of a planar graph is the same for all its planar
embeddings.

∗

This work was partially supported by NSF grant CCF-1408763.

Lower Bounds for Planar Electrical Reduction

1

1

Introduction

Consider the following set of local operations performed on any graph:
• Leaf contraction: Contract the edge incident to a vertex of degree 1.
• Loop deletion: Delete the edge of a loop.
• Series reduction: Contract either edge incident to a vertex of degree 2.
• Parallel reduction: Delete one of a pair of parallel edges.
• Y ∆ transformation: Delete a vertex of degree 3 and connect its neighbors with three new edges.
• ∆Y transformation: Delete the edges of a 3-cycle and join the vertices of the cycle to a new
vertex.

These operations and their inverses, which we call electrical transformations following Colin de Verdière
et al. [11], have been used for over a century to analyze electrical networks [25]. Steinitz [31,32] proved
that any planar network can be reduced to a single vertex using these operations. Several decades later,
Epifanov [15] proved that any planar graph with two special vertices called terminals can be similarly
reduced to a single edge between the terminals; simpler algorithmic proofs of Epifanov’s theorem were
later given by Feo [17], Truemper [33, 34], and Feo and Provan [18]. These results have since been
extended to planar graphs with more than two terminals [3,12,19,20] and to some families of non-planar
graphs [19, 35].
Despite decades of prior work, the complexity of the reduction process is still poorly understood.
Steinitz’s proof implies that O(n2 ) electrical transformations suffice to reduce any n-vertex planar graph
to a single vertex; Feo and Provan’s algorithm reduces any 2-terminal planar graph to a single edge in
O(n2 ) steps. While these are the best upper bounds known, several authors have conjectured that they
can be improved. Without any restrictions on which transformations are permitted, the only known
lower bound is the trivial Ω(n). However, we recently proved that if all electrical transformations are
required to be facial, meaning any deleted cycle must be a face of the given embedding, then reducing a
plane graph without terminals to a single vertex requires Ω(n3/2 ) steps in the worst case [8].
In this paper, we extend our earlier lower bound in two directions. First, in Section 3, we consider plane graphs with two terminals. In this setting, leaf deletions, series reductions, and Y ∆
transformations that delete terminals are forbidden. We prove in Section 3 that Ω(n2 ) facial electrical
transformations are required in the worst case to reduce a 2-terminal plane graph as much as possible.
Not every 2-terminal plane graph can be reduced to a single edge between the terminals using only facial
electrical transformations. However, we show that any 2-terminal plane graph can be reduced to a unique
minimal graph called a bullseye using a finite number of facial electrical transformations. Our lower
bound ultimately reduces to a recent Ω(n2 ) lower bound on the number of homotopy moves required to
simplify a contractible closed curve in the annulus, which we describe in a companion paper [10].
In Section 4, we consider a wider class of electrical transformations that preserve the planarity
of the graph, but are not necessarily facial. Our second main result is that Ω(n3/2 ) planar electrical
transformations are required to reduce a planar graph (without terminals) to a single vertex in the worst
case. Like our earlier lower bound for facial electrical transformations, our proof ultimately reduces to a
study of a certain curve invariant, called the defect, of the medial graph (viewed as a closed curve) of the
given plane graph G. A key step in our new proof is the following surprising observation: Although the
definition of the medial graph of G depends on the embedding of G, the defect of the medial graph is
the same for all planar embeddings of G.

2

2
2.1

Hsien-Chih Chang and Jeff Erickson

Background
Types of Electrical Transformations

We distinguish between three increasingly general types of electrical transformations in plane graphs:
facial, planar, and arbitrary. (For ease of presentation, we assume throughout the paper that plane
graphs are actually embedded on the sphere instead of the plane.)
An electrical transformation in a plane graph G is facial if any deleted cycle is a face of G. All
leaf contractions, series reductions, and Y ∆ transformations are facial, but loop deletions, parallel
reductions, and ∆Y transformations may not be facial. Facial electrical transformations form three
dual pairs, as shown in Figure 2.1; for example, any series reduction in G is equivalent to a parallel
reduction in the dual graph G ∗ .

Figure 2.1. Facial electrical transformations in a plane graph G and its dual G ∗ .

An electrical transformation in G is planar if it preserves the planarity of the underlying graph.
Equivalently, an electrical transformation is planar if the vertices of the cycle deleted by the transformation
are all incident to a common face (in the given embedding) of G. All facial electrical transformations
are trivially planar, as are all loop deletions and parallel reductions. The only non-planar electrical
transformation is a ∆Y transformation whose three vertices are not incident to a common face; any
such transformation introduces a K3,3 minor into the graph, connecting the three vertices of the ∆ to an
interior vertex, an exterior vertex, and the new Y vertex.

Figure 2.2. A non-planar ∆Y transformation.

2.2

Multicurves and Medial Graphs

Formally, a closed curve in a surface M is a continuous map γ: S 1 → M . A closed curve is simple if it is
injective. A multicurve is an collection of one or more disjoint closed curves. We consider only generic
closed curves and multicurves, which are injective except at a finite number of (self-)intersections, each of
which is a transverse double point. A multicurve is connected if its image in the surface is connected; we
consider only connected multicurves in this paper. The image of any (non-simple, connected) multicurve
has a natural structure as a 4-regular map, whose vertices are the self-intersection points of the curve,
edges are maximal subpaths between vertices, and faces are components of the complement of the curve
in the surface. We do not distinguish between multicurves whose images are combinatorially equivalent
maps.
The medial graph G × of a plane graph G is another plane graph whose vertices correspond to
the edges of G, and two vertices of G × are connected by an edge if the corresponding edges in G are
consecutive in cyclic order around some vertex, or equivalently, around some face in G. Every vertex in
every medial graph has degree 4; thus, every medial graph is the image of a multicurve. Conversely, the

Lower Bounds for Planar Electrical Reduction

3

image of every non-simple multicurve on the sphere is the medial graph of some plane graph. We call a
plane graph G unicursal if its medial graph G × is the image of a single closed curve.
Smoothing a multicurve γ at a vertex x replaces the intersection of γ with a small neighborhood
of x with two disjoint simple paths, so that the result is another 4-regular plane graph. There are two
possible smoothings at each vertex. More generally, a smoothing of γ is any multicurve obtained by
smoothing a subset of its vertices. For any plane graph G, the smoothings of the medial graph G × are
precisely the medial graphs of minors of G.

Figure 2.3. Smoothing a vertex.

2.3

Local Moves

A homotopy between two curves γ and γ0 on the same surface is a continuous deformation from one
curve to the other, formally defined as a continuous function H : S 1 × [0, 1] → M such that H(·, 0) = γ
and H(·, 1) = γ0 . The definition of homotopy extends naturally to multicurves. Classical topological
arguments imply that two multicurves are homotopic if and only if one can be transformed into the other
by a finite sequence of homotopy moves, shown in Figure 2.4. A multicurve is homotopically reduced
if no sequence of homotopy moves leads to a multicurve with fewer vertices.

Figure 2.4. Homotopy moves 10, 20, and 33.

Figure 2.5. Medial electrical moves 10, 21, and 33.

Facial electrical transformations in any plane graph G induce local transformations in the medial
graph G × that closely resemble homotopy moves. We call these 10, 21, and 33 moves, where the
numbers before and after each arrow indicate the number of local vertices before and after the move;
see Figure 2.5. We collectively refer to these transformations and their inverses as medial electrical
moves. A multicurve is electrically reduced if no sequence of medial electrical moves leads to another
multicurve with fewer vertices.
For multicurves on surfaces with boundary, both homotopy moves and medial electrical moves on
boundary faces are forbidden.

3

Two-Terminal Plane Graphs

Most applications of electrical reductions, starting with Kennelly’s classical computation of effective
resistance [25], designate two vertices of the input graph as terminals and require a reduction to a
single edge between those terminals. In this context, electrical transformations that delete either of the
terminals are forbidden; specifically: leaf contractions when the leaf is a terminal, series reductions when
the degree-2 vertex is a terminal, and Y ∆ transformations when the degree-3 vertex is a terminal.

4

Hsien-Chih Chang and Jeff Erickson

Epifanov [15] was the first to prove that any 2-terminal planar graph can be reduced to a single
edge between the terminals using a finite number of electrical transformations, roughly 50 years after
Steinitz proved the corresponding result for planar graphs without terminals [31, 32]. Epifanov’s proof
is non-constructive; algorithms for reducing 2-terminal planar graphs were later described by Feo [17],
Truemper [33], and Feo and Provan [18]. (An algorithm in the spirit of Steinitz’s reduction proof can
also be derived from results of de Graaf and Schrijver [21].)
An important subtlety that complicates both Epifanov’s proof and its algorithmic descendants is
that not every 2-terminal planar graph can be reduced to a single edge using only facial electrical
transformations. The simplest bad example is the three-vertex graph shown in Figure 3.1; the solid
vertices are the terminals. Although this graph has more than one edge, it has no reducible leaves, empty
loops, cycles of length 2 or 3, or vertices with degree 2 or 3. (Later in this section, we prove that this
graph cannot be reduced to an edge even if we allow “backward” facial electrical transformations that
make the graph more complicated.)

Figure 3.1. A facially irreducible 2-terminal plane graph.

In this section, we show that in the worst case, Ω(n2 ) facial electrical transformations are required
to reduce an 2-terminal plane graph with n vertices as much as possible. First, we prove in Section 3.1
that any 2-terminal planar graph can be reduced to a unique minimal graph called a bullseye by facial
electrical transformations. We prove our quadratic lower bound in Section 3.2.
Existing algorithms for reducing an arbitrary 2-terminal plane graphs to a single edge rely on an additional operation which we call a terminal-leaf contraction, in addition to facial electrical transformations.
We discuss this subtlety in more detail in Section 3.3.
3.1

Winding Number, Medial Depth, and Bullseyes

The medial graph G × of any 2-terminal plane graph G is properly considered as a multicurve embedded
in the annulus; the faces of G × that correspond to the terminals are removed from the surface.
The winding number of a directed closed curve γ in the annulus is the number of times any generic
path α from one boundary component to the other crosses γ from left to right, minus the number of
times α crosses γ from right to left. Two directed closed curves in the annulus are homotopic if and only
if their winding numbers are equal.
The depth of any multicurve γ in the annulus is the minimum number of times a path from one
boundary to the other crosses γ; thus, depth is essentially an unsigned version of winding number. Just as
the winding number around the boundaries is a complete homotopy invariant for curves in the annulus,
the depth of the medial graph turns out to be a complete invariant for facial electrical transformation of
2-terminal plane graphs.
Lemma 3.1. Medial electrical transformations do not change the depth of any connected multicurve in
the annulus. Thus, facial electrical transformations in any 2-terminal plane graph G do not change the
depth of the medial graph G × .
Proof: Let γ be a connected multicurve in the annulus. For any face of γ that could be deleted by a
medial electrical move, exhaustive case analysis implies that there is a shortest path between the two
boundary faces of γ that avoids that face.


Lower Bounds for Planar Electrical Reduction

5

For any integer d > 0, let αd denote the unique closed curve in the annulus with d − 1 vertices and
winding number d. Up to isotopy, this curve can be parametrized in the plane as
αd (θ ) := ((cos(θ ) + 2) cos(dθ ), (cos(θ ) + 2) sin(dθ )).
In the notation of our other papers [8, 9], αd is the flat torus knot T (d, 1).
Similarly, for any k > 0, let Bk denote the 2-terminal plane graph that consists of a path of length k
between the terminals, with a loop attached to each of the k − 1 interior vertices, embedded so that
collectively they form concentric circles that separate the terminals. We call each graph Bk a bullseye.
For example, B1 is just a single edge; B2 is shown in Figure 3.1; and B4 is shown on the left in Figure 3.2.
The medial graph Bk× of the kth bullseye is the curve α2k . Because different bullseyes have different
medial depths, Lemma 3.1 implies that no bullseye can be transformed into any other bullseye by facial
electrical transformations.

Figure 3.2. The bullseye graph B4 and its medial graph α8 .

Lemma 3.2. For any integer d > 0, the curve αd is both homotopically reduced and electrically reduced.
Proof: Every connected multicurve in the annulus with either winding number d or depth d has at least
d + 1 faces (including the faces containing the boundaries of the annulus) and therefore, by Euler’s
formula, has at least d − 1 vertices.

Lemma 3.3. If γ is a homotopically reduced connected multicurve in the annulus, then γ = αd for some
integer d.
Proof: A multicurve in the annulus is homotopically reduced if and only if its constituent curves are
homotopically reduced and disjoint. Thus, any connected homotopically reduced multicurve is actually a
single closed curve. Any two curves in the annulus with the same winding number are homotopic [24].
Finally, up to isotopy, αd is the only closed curve in the annulus with winding number d and d − 1
vertices [22, Lemma 1.12].

Lemma 3.4. Let γ be a connected multicurve on any surface, possibly with boundary. If γ is electrically
reduced, then γ is also homotopically reduced.
Proof: Let γ be a connected multicurve in some arbitrary surface, and suppose γ is not homotopically
reduced. A seminal result of de Graaf and Schrijver [21] implies that γ can be simplified by a finite
sequence of homotopy moves1 that never increases the number of vertices. In particular, applying some
finite sequence of 33 moves to γ creates either an empty loop, which can be removed by a 10 move, or
an empty bigon, which can be removed by either a 20 move or a 21 move. Thus, γ is not electrically
reduced.

1

De Graaf and Schrijver’s result requires a fourth type of homotopy move, which moves an isolated simple contractible
constituent curve from one face of the rest of the multicurve to another. However, since this move can only be applied to
disconnected multicurves, it does not affect our argument.

6

Hsien-Chih Chang and Jeff Erickson
The following corollaries are now immediate.

Corollary 3.5. A connected multicurve γ in the annulus is electrically reduced if and only if γ = αdepth(γ) .
Corollary 3.6. Let γ and γ0 be two connected multicurves in the annulus. Then γ can be transformed
into γ0 by medial electrical moves if and only if depth(γ) = depth(γ0 ).
Corollary 3.7. Let G be an arbitrary 2-terminal plane graph. G can be reduced to the bullseye Bk using
a finite sequence of facial electrical transformations if and only if depth(G × ) = 2k.
Corollary 3.8. Let G and H be arbitrary 2-terminal plane graphs. G can be transformed to H using a
finite sequence of facial electrical transformations if and only if depth(G × ) = depth(H × ).
3.2

Quadratic Lower Bound

For any connected multicurve γ, let X (γ) denote the minimum number of medial electrical moves
required to reduce γ as much as possible, and let H(γ) denote the minimum number of homotopy moves
required to reduce γ as much as possible. Our quadratic lower bound proof generally follows our earlier
proof that X (γ) ≥ H(γ) for any closed curve γ in the plane or the sphere [8, Lemma 3.3], which is based
in turn on arguments of Truemper [33] and Noble and Welsh [27].
Lemma 3.9. For any connected proper smoothing γ of any connected multicurve γ in the annulus, we
have X (γ) + 12 depth(γ) ≤ X (γ) + 12 depth(γ).
Proof: Let γ be an arbitrary connected multicurve in the annulus, and let γ be an arbitrary connected
proper smoothing of γ. Without loss of generality, we can assume that γ is non-simple, since otherwise
the lemma is vacuous.
First, suppose γ is a connected smoothing of γ obtained by smoothing a single vertex x. There are
only two cases to consider: Either γ is electrically reduced or not.
If γ is electrically reduced, then γ = αd for some integer d ≥ 2 by Corollary 3.5. (The curves α0
and α1 are simple.) The smoothed curve γ contains a single loop if x is the innermost or outermost
vertex of γ, or a single bigon otherwise. Applying one 10 or 20 move transforms γ into the curve
αd−2 , which is electrically reduced by Lemma 3.2. Thus we have X (γ) = 1 and depth(γ) = d − 2, which
implies X (γ) + 12 depth(γ) = X (γ) + 12 depth(γ).
On the other hand, suppose γ is not reduced. We argue by induction on X (γ), with the set of reduced
curves as a base case, closely following our earlier proof [8, Lemma 3.1]. Let γ0 be the result of the
first medial electrical move in the minimum-length sequence that reduces γ. We immediately have
X (γ0 ) = X (γ)−1 and depth(γ0 ) = depth(γ). There are several subcases to consider, depending on whether
the move from γ to γ0 involves the smoothed vertex x, and if so, on the type of move and how x is
smoothed. In all cases, there is a connected multicurve γ0 that can be obtained both by applying at most
one medial electrical move to γ and by smoothing at most two vertices of γ0 .
Specifically, if the move from γ to γ0 does not involve x, we can define γ0 = γ; the remaining eight
subcases are illustrated in Figure 3.3. One subcase for the 01 move is impossible, because we have
assumed that γ is connected. In the remaining 01 subcase and one 21 subcase, we can define
γ0 = γ = γ0 , and in all remaining subcases, γ0 is a proper smoothing of γ0 .
In every case, we have depth(γ) = depth(γ0 ) and depth(γ) = depth(γ0 ), and therefore
X (γ) + 12 depth(γ) ≤ X (γ0 ) + 1 + 12 depth(γ0 )
≤ X (γ0 ) + 1 + 12 depth(γ0 )
1
2

≤ X (γ) + depth(γ),

(∗)

Lower Bounds for Planar Electrical Reduction

7

1→0

=

2→1

=

1→0

1→2

=

=

3→3

2→1

=

Figure 3.3. Cases for the proofs of Lemma 3.9 and 4.6; the circled vertex is x .

where the second inequality (∗) is either trivial (because γ0 = γ0 ) or follows from the induction hypothesis
(because γ0 is a proper smoothing of γ0 ).
Finally, if γ is obtained from γ by smoothing more than one vertex, the lemma follows from the
previous cases by induction on the number of vertices.

Lemma 3.10. For every connected multicurve γ in the annulus, there is a minimum-length sequence of
medial electrical moves that reduces γ to αdepth(γ) without 01 or 12 moves.
Proof: Consider a minimum-length sequence of medial electrical moves that reduces an arbitrary
connected multicurve γ in the annulus. For any integer i ≥ 0, let γi denote the result of the first i moves
in this sequence. Suppose γi has one more vertex than γi−1 for some index i. Then γi−1 is a connected
proper smoothing of γi , and depth(γi ) = depth(γi−1 ); so Lemma 3.9 implies that X (γi−1 ) ≤ X (γi ),
contradicting our assumption that the reduction sequence has minimum length.

Lemma 3.11. X (γ) + 12 depth(γ) ≥ H(γ) for every closed curve γ in the annulus.
Proof: Let γ be a closed curve in the annulus. If γ is already electrically reduced, then X (γ) = H(γ) = 0
by Lemma 3.4, so the lemma is trivial. Otherwise, let Σ be a minimum-length sequence of medial
electrical moves that reduces γ as much as possible. By Lemma 3.10, we can assume that the first move
in Σ is neither 01 nor 12. If the first move is 10 or 33, the theorem immediately follows by
induction on X (γ), since by Lemma 3.1 neither of these moves changes the depth of the curve.
The only interesting first move is 21. Let γ0 be the result of this 21 move, and let γ◦ be the
result if we perform the 20 homotopy move on the same vertex instead. The minimality of Σ implies
X (γ) = X (γ0 ) + 1, and we trivially have H(γ) ≤ H(γ◦ ) + 1. Because γ is a single curve, γ◦ is also a single
curve and therefore a connected proper smoothing of γ0 . Thus, Lemmas 3.1 and 3.9 and the inductive
hypothesis imply
X (γ) + 12 depth(γ) = X (γ0 ) + 21 depth(γ0 ) + 1
≥ X (γ◦ ) + 12 depth(γ◦ ) + 1
≥ H(γ◦ ) + 1
≥ H(γ),
which completes the proof.



8

Hsien-Chih Chang and Jeff Erickson

Theorem 3.12. Let G be an arbitrary 2-terminal plane graph, and let γ be any unicursal smoothing
of G × . Reducing G to a bullseye requires at least H(γ) − 12 depth(γ) facial electrical transformations.
In a companion paper [10], we describe an infinite family of contractible curves in the annulus that
require Ω(n2 ) homotopy moves to simplify. Because these curves are contractible, they have even depth,
and thus are the medial graphs of 2-terminal plane graphs. Euler’s formula implies that every n-vertex
curve in the annulus has exactly n + 2 faces (including the boundary faces) and therefore has depth at
most n + 1.
Corollary 3.13. Reducing a 2-terminal plane graph to a bullseye requires Ω(n2 ) facial electrical transformations in the worst case.
3.3

Terminal-Leaf Contractions

The electrical reduction algorithms of Feo [17], Truemper [33], and Feo and Provan [18] rely exclusively
on facial electrical transformations, plus one additional operation.
• Terminal-leaf contraction: Contract the edge incident to a terminal vertex with degree 1. The
neighbor of the deleted terminal becomes a new terminal.
Terminal-leaf contractions are also called FP-assignments, after Feo and Provan [12, 19, 20]. Later
algorithms for reducing plane graphs with three or four terminals [3,12,20] also use only facial electrical
transformations and terminal-leaf contractions.
Formally, terminal-leaf contractions are not electrical transformations, as they can change the value
one wants to compute. For example, if the edges in the graph shown in Figure 3.1 represent 1Ω
resistors, a terminal-leaf contraction changes the effective resistance between the terminals from 2Ω
to 1Ω. However, both Gilter [19] and Feo and Provan [18] observed that any sequence of facial electrical
transformations and terminal-leaf contractions can be simulated on the fly by a sequence of planar
electrical transformations. Specifically, we simulate the first leaf contraction at either terminal by
simply marking that terminal and proceeding as if its unique neighbor were a terminal. Later electrical
transformations involving the neighbor of a marked terminal may no longer be facial, but they will
still be planar; terminal-leaf contractions at the unique neighbor of a marked terminal become series
reductions. At the end of the sequence of transformations, we perform a final series reduction at the
unique neighbor of each marked terminal.
Unfortunately, terminal-leaf contractions change both the depth of the medial graph and the curve
invariants that imply the quadratic homotopy lower bound. As a result, our quadratic lower bound
proof breaks down if we allow terminal-leaf contractions. Indeed, we conjecture that any 2-terminal
plane graph can be reduced to a single edge using only O(n3/2 ) facial electrical transformations and
terminal-leaf contractions, matching the lower bound proved in Section 4.

4

Planar Electrical Transformations

Finally, we extend our earlier Ω(n3/2 ) lower bound for reducing plane graphs without terminals using
only facial electrical transformations to the larger class of planar electrical transformations. As in our
earlier work [8], we analyze electrical transformations in an unicursal plane graph G in terms of a
certain invariant of the medial graph of G called defect, first introduced by Aicardi [2] and Arnold [4, 5].
Our extension to non-facial electrical transformations is based on the following surprising observation:
Although the medial graph of G depends on its embedding, the defect of the medial graph of G does not.

Lower Bounds for Planar Electrical Reduction
4.1

9

Defect

Let γ be an arbitrary closed curve on the sphere. Choose an arbitrary basepoint γ(0) and an arbitrary
orientation for γ. For any vertex x of γ, we define sgn(x) = +1 if the first traversal through x crosses the
second traversal from right to left, and sgn(x) = −1 otherwise. Two vertices x and y are interleaved,
denoted x Ç y, if they alternate in cyclic order—x, y, x, y—along γ. Finally, following Polyak [28], we
can define
X
defect(γ) := − 2
sgn(x) · sgn( y),
xÇ y

where the sum is taken over all interleaved pairs of vertices of γ.
Trivially, every simple closed curve has defect zero. Straightforward case analysis [28] implies that
the defect of a curve does not depend on the choice of basepoint or orientation. Moreover, any homotopy
move changes the defect of a curve by at most 2; see our previous paper [8, Section 2.1] for an explicit
case breakdown. Defect is also preserved by any homeomorphism from the sphere to itself, including
reflection.
4.2

Tangle Flips

Now let σ be a simple closed curve that intersects γ only transversely and away from its vertices. By
the Jordan curve theorem, we can assume without loss of generality that σ is a circle, and that the
intersection points γ ∩ σ are evenly spaced around σ. A tangle of γ is the intersection of γ with either
disk bounded by σ; each tangle consists of one or more subpaths of γ called strands. We arbitrarily
refer to the two tangles defined by σ as the interior and exterior tangles of σ.
A tangle is tight if each strand is simple and each pair of strands crosses at most once. Any tangle can
be tightened—that is, transformed into a tight tangle—by continuously deforming the strands without
crossing σ or moving their endpoints, and therefore by a finite sequence of homotopy moves. Let γ å σ
and γ ä σ denote the closed curves that result from tightening the interior and exterior tangles of σ,
respectively.2

Figure 4.1. Flipping tangles with one and two strands.

Finally, we can flip any tangle by reflecting the disk containing it, so that each strand endpoint maps
to a different strand endpoint; see Figure 4.1. Straightforward case analysis implies that flipping any
tangle of γ with at most two strands transforms γ into another closed curve. The main result of this
section is that the resulting curve has the same defect as γ.
Lemma 4.1. Let γ be an arbitrary closed curve on the sphere. Flipping any tangle of γ with one strand
yields another closed curve γ0 with defect(γ0 ) = defect(γ).
Proof: Let σ be a simple closed curve that crosses γ at exactly two points. These points decompose σ
into two subpaths α · β, where α is the unique strand of the interior tangle and β is the unique strand of
the exterior tangle. Let Σ denote the interior disk of σ, and let φ : Σ → Σ denote the homeomorphism
that flips the interior tangle. Flipping the interior tangle yields the closed curve γ0 := rev(φ(α)) · β,
where rev denotes path reversal.
2

We recommend pronouncing å as “tightened inside” and ä as “tightened outside”; note that the symbols å and ä resemble
the second letters of “inside” and “outside”.

10

Hsien-Chih Chang and Jeff Erickson

No vertex of α is interleaved with a vertex of β; thus, two vertices in γ0 are interleaved if and only
if the corresponding vertices in γ are interleaved. Every vertex of rev(φ(α)) has the same sign as the
corresponding vertex of α, since both the orientation of the vertex and the order of traversals through
the vertex changed. Thus, every vertex of γ0 has the same sign as the corresponding vertex of γ. We
conclude that defect(γ0 ) = defect(γ).

Lemma 4.2. Let γ be an arbitrary closed curve on the sphere. Flipping any tangle of γ with two strands
yields another closed curve γ0 with defect(γ0 ) = defect(γ).
Proof: Let σ be a simple closed curve that crosses γ at exactly four points. These four points naturally
decompose γ into four subpaths α · δ · β · ", where α and β are the strands of the interior tangle of σ,
and δ and " are the strands of the exterior tangle. Flipping the interior tangle either exchanges α and β,
reverses α and β, or both; see Figure 4.2. In every case, the result is a single closed curve γ0 .
"
↵
"

↵

↵

↵

↵

"

"

"
↵
"

"

↵

↵

↵

"

"
↵

↵

"

↵

"

"

Figure 4.2. Flipping all six types of 2-strand tangle.

The identity defect(γ0 ) = defect(γ) follows from our inclusion-exclusion formula for defect [7,
Lemma 5.4]; we give a simpler complete proof here to keep the paper self-contained.
We classify each vertex of γ as interior if it lies on α and/or β, and exterior otherwise. Similarly, we
classify pairs of interleaved vertices are either interior, exterior, or mixed.
An interior vertex x and an exterior vertex y are interleaved if and only if x is an intersection point
of α and β and y is an intersectionPpoint of δ and ". Thus, the total contribution of mixed vertex pairs
to Polyak’s formula defect(γ) = −2 xÇ y sgn(x) · sgn( y) is
!
!
X X
X
X
−2
sgn(x) · sgn( y) = − 2
sgn(x)
sgn( y) .
x∈α∩β y∈δ∩"

x∈α∩β

y∈δ∩"

Consider any sequence of homotopy moves that tightens the interior tangle with strands α and β. Any
20 move involving both α and β removes one positive and one negative vertex; no other homotopy
move changes the
P number of vertices in α ∩ β or the signs of those vertices. Thus, tightening α and β
leaves the sum x∈α∩β sgn(x) unchanged. Similarly, tightening the exterior tangle δ ∪ " leaves the sum
P
or δ and "
y∈δ∩" sgn( y) unchanged. But after tightening both tangles, either α and β are disjoint,
P
are disjoint, or both, as γ is a single closed curve. Thus, at least one of the sums x∈α∩β sgn(x) and
P
y∈δ∩" sgn( y) is equal to zero. We conclude that mixed vertex pairs do not contribute to the defect.
The curve γ å σ obtained by tightening α and β has at most one interior vertex (and therefore no
interior vertex pairs); the exterior vertices of γ å σ are precisely the exterior vertices of γ. Similarly, the
curve γ ä σ obtained by tightening both δ and " has at most one exterior vertex; the interior vertices of
γ ä σ are precisely the interior vertices of γ. It follows that defect(γ) = defect(γ ä σ) + defect(γ å σ).
Finally, let γ0 be the result of flipping the interior tangle. The curve γ0 ä σ is just a reflection of γ ä σ,
which implies that defect(γ0 ä σ) = defect(γ ä σ), and straightforward case analysis implies γ0 å σ = γ å σ.
We conclude that defect(γ0 ) = defect(γ0 åσ)+defect(γ0 äσ) = defect(γåσ)+defect(γäσ) = defect(γ). 

Lower Bounds for Planar Electrical Reduction
4.3

11

Navigating Between Planar Embeddings

A classical result of Adkisson [1] and Whitney [36] is that every 3-connected planar graph has an
essentially unique planar embedding. Mac Lane [26] described how to count the planar embeddings of
any biconnected planar graph, by decomposing it into its triconnected components. Stallmann [29, 30]
and Cai [6] extended Mac Lane’s algorithm to arbitrary planar graphs, by decomposing them into
biconnected components. Mac Lane’s decomposition is also the basis of the SPQR-tree data structure of
Di Battista and Tamassia [13, 14], which encodes all planar embeddings of an arbitrary planar graph.
Mac Lane’s structural results imply that any planar embedding of a 2-connected planar graph G can
be transformed into any other embedding by a finite sequence of split reflections, defined as follows.
A split curve is a simple closed curve σ whose intersection with the embedding of G consists of two
vertices x and y; without loss of generality, σ is a circle with x and y at opposite points. A split reflection
modifies the embedding of G by reflecting the subgraph inside σ across the line through x and y.
Lemma 4.3. Let G be an arbitrary 2-connected planar graph. Any planar embedding of G can be
transformed into any other planar embedding of G by a finite sequence of split reflections.
To navigate among the planar embeddings of arbitrary connected planar graphs, we need two
additional operations. First, we allow split curves that intersect G at only a single cut vertex; a cut
reflection modifies the embedding of G by reflects the subgraph inside such a curve. More interestingly,
we also allow degenerate split curves that pass through a cut vertex x of G twice, but are otherwise
simple and disjoint from G. The interior of a degenerate split curve σ is an open topological disk. A
cut eversion is a degenerate split reflection that everts the embedding of the subgraph of G inside such
a curve, intuitively by mapping the interior of σ to an open circular disk (with two copies of x on its
boundary), reflecting the interior subgraph, and then mapping the resulting embedding back to the
interior of σ. Structural results of Stallman [29, 30] and Di Battista and Tamassia [14, Section 7] imply
the following.

Figure 4.3. Top row: A regular split reflection and a cut reflection. Bottom row: a cut eversion.

Lemma 4.4. Let G be an arbitrary connected planar graph. Any planar embedding of G can be transformed into any other planar embedding of G by a finite sequence of split reflections, cut reflections,
and cut eversions.
Now consider the effect of these operations on the medial graph G × . For simplicity, assume G × is a
single closed curve. Let σ be any (possibly degenerate) split curve for G. Embed G × so that every medial
vertex lies on the corresponding edge in G, and every medial edge intersects σ at most once. Then σ
intersects at most four edges of G × , so the tangle of G × inside σ has at most two strands. Moreover,
reflecting (or everting) the subgraph of G inside σ induces a flip of this tangle of G × .
Lemmas 4.1, 4.2, and 4.4 now immediately imply the following result.

12

Hsien-Chih Chang and Jeff Erickson

Theorem 4.5. Let G and H be planar embeddings of the same abstract planar graph. If G is unicursal,
then H is unicursal and defect(G × ) = defect(H × ).
4.4

Back to Planar Electrical Moves

Each planar electrical transformation in a planar graph G induces the same change in the medial graph G ×
as a finite sequence of 1- and 2-strand tangle flips (hereafter simply called “tangle flips”) followed by a
single medial electrical move. For an arbitrary connected multicurve γ on the sphere, let X̄ (γ) denote
the minimum number of medial electrical moves in a mixed sequence of medial electrical moves and
tangle flips that simplifies γ. Similarly, let H̄(γ) denote the minimum number of homotopy moves in a
mixed sequence of homotopy moves and tangle flips that simplifies γ. We emphasize that tangle flips are
“free” and do not contribute to either X̄ (γ) or H̄(γ).
Our lower bound on planar electrical moves follows our earlier lower bound proof for facial electrical
moves [8] almost verbatim; the only subtlety is that the embedding of the graph can effectively change
at every step of the reduction. We repeat the arguments here to keep the paper self-contained.
Lemma 4.6. X̄ (γ) < X̄ (γ) for every connected proper smoothing γ of every connected multicurve γ on
the sphere.
Proof: Let γ be a connected multicurve, and let γ be a connected proper smoothing of γ. The proof
proceeds by induction on X̄ (γ). If X̄ (γ) = 0, then γ is already simple, so the lemma is vacuously true.
First, suppose γ is obtained from γ by smoothing a single vertex x. Let Σ be an optimal mixed
sequence of tangle flips and medial electrical moves that simplifies γ. This sequence starts with zero
or more tangle flips, followed by a medial electrical move. Let γ0 be the multicurve that results from
the initial sequence of tangle flips; by definition, we have X̄ (γ) = X̄ (γ0 ). Moreover, applying the same
sequence of tangle flips to γ yields a connected multicurve γ0 such that X̄ (γ) = X̄ (γ0 ). Thus, we can
assume without loss of generality that the first operation in Σ is a medial electrical move.
Now let γ0 be the result of this move; by definition, we have X̄ (γ) = X̄ (γ0 ) + 1. As in the proof of
Lemma 3.9, there are several subcases to consider, depending on whether the move from γ to γ0 involves
the smoothed vertex x, and if so, the specific type of move; see Figure 3.3. In every subcase, we can
apply at most one medial electrical move to γ to obtain a (possibly trivial) smoothing γ0 of γ0 , and then
apply the inductive hypothesis on γ0 and γ0 to prove the statement. We omit the straightforward details.
Finally, if γ is obtained from γ by smoothing more than one vertex, the lemma follows immediately
by induction from the previous analysis.

Lemma 4.7. For every connected multicurve γ, there is an intermixed sequence of medial electrical
moves and tangle flips that reduces γ to a simple closed curve, contains exactly X̄ (γ) medial electrical
moves, and does not contain 01 or 12 moves.
Proof: Consider an optimal sequence of medial electrical moves and tangle flips that reduces γ, and let γi
denote the result of the first i moves in this sequence. If any γi has more vertices than its predecessor
γi−1 , then γi−1 is a connected proper smoothing of γi , and Lemma 4.6 implies a contradiction.

Lemma 4.8. X̄ (γ) ≥ H̄(γ) for every closed curve γ on the sphere.
Proof: Let γ be a planar closed curve. The proof proceeds by induction on X̄ (γ). If X̄ (γ) = 0, then γ is
simple and thus H̄(γ) = 0, so assume otherwise.
Let Σ be an optimal sequence of medial electrical moves and tangle flips that reduces γ, and let γi be
the curve obtained by applying a prefix of Σ up to and including the first medial electrical move. The
minimality of Σ implies that X̄ (γ) = X̄ (γ0 ) + 1. By Lemma 4.7, we can assume without loss of generality

Lower Bounds for Planar Electrical Reduction

13

that the first medial electrical move in Σ is neither 01 nor 12, and if this first medial electrical move
is 10 or 33, the theorem immediately follows by induction.
The only remaining move to consider is 21. Let γ denote the result of applying the same sequence
of tangle flips to γ, but replacing the final 21 move with a 20 move, or equivalently, smoothing the
vertex of γ0 left by the final 21 move. We immediately have H̄(γ) ≤ H̄(γ) + 1. Because γ is a connected
proper smoothing of γ0 , Lemma 4.6 implies X̄ (γ) < X̄ (γ0 ) = X̄ (γ) − 1. Finally, the inductive hypothesis
implies that X̄ (γ) ≥ H̄(γ), which completes the proof.

Lemma 4.9. H̄(γ) ≥ |defect(γ)|/2 for every closed curve γ on the sphere.
Proof: Each homotopy move decreases |defect(γ)| by at most 2, and Lemmas 4.1 and 4.2 imply that
tangle flips do not change |defect(γ)| at all. Every simple curve has defect 0.

Theorem 4.10. Let G be an arbitrary planar graph, and let γ be any unicursal smoothing of G × (defined
with respect to any planar embedding of G). Reducing G to a single vertex requires at least |defect(γ)|/2
planar electrical transformations.
Proof: The minimum number of planar electrical transformations required to reduce G is at least X̄ (G × ).
Because γ is a single curve, it must be connected, so Lemma 4.6 implies that X̄ (G × ) ≥ X̄ (γ). The theorem
now follows immediately from Lemmas 4.8 and 4.9.

Finally, Hayashi et al. [23] and Even-Zohar et al. [16] describe infinite families of planar closed
curves with defect Ω(n3/2 ); see also [8, Section 2.2]. The following corollary is now immediate.
Corollary 4.11. Reducing any n-vertex planar graph to a single vertex requires Ω(n3/2 ) planar electrical
transformations in the worst case.

5

Open Problems

Our results suggest several open problems. Perhaps the most compelling, and the primary motivation for
our work, is to find either a subquadratic upper bound or a quadratic lower bound on the number of
(unrestricted) electrical transformations required to reduce any planar graph without terminals to a single
vertex. Like Gitler [19], Feo and Provan [18], and Archdeacon et al. [3], we conjecture that O(n3/2 ) facial
electrical transformations suffice. More ambitiously, we conjecture that any 2-terminal plane graph can
be reduced to a single edge using O(n3/2 ) facial electrical transformations and terminal-leaf contractions,
as mentioned in Section 3.3. However, proving these conjectures appears to be challenging.
Finally, none of our lower bound techniques imply anything about non-planar electrical transformations or about electrical reduction of non-planar graphs. Indeed, the only lower bound known in the
most general setting, for any family of electrically reducible graphs, is the trivial Ω(n). It seems unlikely
that planar graphs can be reduced more quickly by using non-planar electrical transformations, but we
can’t prove anything. Any non-trivial lower bound for this problem would be interesting.

References
[1] Virgil W. Adkisson. Cyclicly connected continuous curves whose complementary domain boundaries
are homeomorphic, preserving branch points. C. R. Séances Soc. Sci. Lett. Varsovie III 23:164–193,
1930.
[2] Francesca Aicardi. Tree-like curves. Singularities and Bifurcations, 1–31, 1994. Advances in Soviet
Mathematics 21, Amer. Math. Soc.

14

Hsien-Chih Chang and Jeff Erickson

[3] Dan Archdeacon, Charles J. Colbourn, Isidoro Gitler, and J. Scott Provan. Four-terminal reducibility
and projective-planar wye-delta-wye-reducible graphs. J. Graph Theory 33(2):83–93, 2000.
[4] Vladimir I. Arnold. Plane curves, their invariants, perestroikas and classifications. Singularities and
Bifurcations, 33–91, 1994. Adv. Soviet Math. 21, Amer. Math. Soc.
[5] Vladimir I. Arnold. Topological Invariants of Plane Curves and Caustics. University Lecture Series 5.
Amer. Math. Soc., 1994.
[6] Jaizhen Cai. Counting embeddings of planar graphs using DFS trees. SIAM J. Discrete Math.
6(3):335–352, 1993.
[7] Hsien-Chih Chang and Jeff Erickson. Electrical reduction, homotopy moves, and defect. Preprint,
October 2015. arXiv:1510.00571.
[8] Hsien-Chih Chang and Jeff Erickson. Untangling planar curves. Proc. 32nd Int. Symp. Comput.
Geom., 29:1–29:15, 2016. Leibniz International Proceedings in Informatics 51. 〈http://drops.
dagstuhl.de/opus/volltexte/2016/5921〉.
[9] Hsien-Chih Chang and Jeff Erickson. Unwinding annular curves and electrically reducing planar
networks. Accepted to Computational Geometry: Young Researchers Forum, Proc. 33rd Int. Symp.
Comput. Geom., 2017.
[10] Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick,
Dylan Thurston, and Stephan Tillmann. Tightening curves on surfaces via local moves. Submitted,
2017.
[11] Yves Colin de Verdière, Isidoro Gitler, and Dirk Vertigan. Réseaux électriques planaires II. Comment.
Math. Helvetici 71:144–167, 1996.
[12] Lino Demasi and Bojan Mohar. Four terminal planar Delta-Wye reducibility via rooted K2,4 minors.
Proc. 26th Ann. ACM-SIAM Symp. Discrete Algorithms, 1728–1742, 2015.
[13] Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing. Proc. 30th Ann. IEEE
Symp. Foundations Comput. Sci., 436–441, 1989.
[14] Giuseppe Di Battista and Roberto Tamassia. On-line planarity testing. SIAM J. Comput. 25(5):956–
997, 1996.
[15] G. V. Epifanov. Reduction of a plane graph to an edge by a star-triangle transformation. Dokl. Akad.
Nauk SSSR 166:19–22, 1966. In Russian. English translation in Soviet Math. Dokl. 7:13–17, 1966.
[16] Chaim Even-Zohar, Joel Hass, Nati Linial, and Tahl Nowik. Invariants of random knots and links.
Discrete & Computational Geometry 56(2):274–314, 2016. arXiv:1411.3308.
[17] Thomas A. Feo. I. A Lagrangian Relaxation Method for Testing The Infeasibility of Certain VLSI Routing
Problems. II. Efficient Reduction of Planar Networks For Solving Certain Combinatorial Problems.
Ph.D. thesis, Univ. California Berkeley, 1985. 〈http://search.proquest.com/docview/303364161〉.
[18] Thomas A. Feo and J. Scott Provan. Delta-wye transformations and the efficient reduction of
two-terminal planar graphs. Oper. Res. 41(3):572–582, 1993.
[19] Isidoro Gitler. Delta-wye-delta Transformations: Algorithms and Applications. Ph.D. thesis, Department of Combinatorics and Optimization, University of Waterloo, 1991.

Lower Bounds for Planar Electrical Reduction

15

[20] Isidoro Gitler and Feliú Sagols. On terminal delta-wye reducibility of planar graphs. Networks
57(2):174–186, 2011.
[21] Maurits de Graaf and Alexander Schrijver. Making curves minimally crossing by Reidemeister
moves. J. Comb. Theory Ser. B 70(1):134–156, 1997.
[22] Joel Hass and Peter Scott. Intersections of curves on surfaces. Israel J. Math. 51:90–120, 1985.
[23] Chuichiro Hayashi, Miwa Hayashi, Minori Sawada, and Sayaka Yamada. Minimal unknotting sequences of Reidemeister moves containing unmatched RII moves. J. Knot Theory Ramif.
21(10):1250099 (13 pages), 2012. arXiv:1011.3963.
[24] Heinz Hopf. Über die Drehung der Tangenten und Sehnen ebener Kurven. Compositio Math.
2:50–62, 1935.
[25] Arthur Edwin Kennelly. Equivalence of triangles and three-pointed stars in conducting networks.
Electrical World and Engineer 34(12):413–414, 1899.
[26] Saunders Mac Lane. A structural characterization of planar combinatorial graphs. Duke Math. J.
3(3):460–472, 1937.
[27] Steven D. Noble and Dominic J. A. Welsh. Knot graphs. J. Graph Theory 34(1):100–111, 2000.
[28] Michael Polyak. Invariants of curves and fronts via Gauss diagrams. Topology 37(5):989–1009,
1998.
[29] Matthias F. M. Stallmann. Using PQ-trees for planar embedding problems. Tech. Rep. NCSU-CSC
TR-85-24, Dept. Comput. Sci., NC State Univ., December 1985. 〈https://people.engr.ncsu.edu/
mfms/Publications/1985-TR_NCSU_CSC-PQ_Trees.pdf〉.
[30] Matthias F. M. Stallmann. On counting planar embeddings. Discrete Math. 122:385–392, 1993.
[31] Ernst Steinitz. Polyeder und Raumeinteilungen. Enzyklopädie der mathematischen Wissenschaften
mit Einschluss ihrer Anwendungen III.AB(12):1–139, 1916.
[32] Ernst Steinitz and Hans Rademacher. Vorlesungen über die Theorie der Polyeder: unter Einschluß
der Elemente der Topologie. Grundlehren der mathematischen Wissenschaften 41. Springer-Verlag,
1934. Reprinted 1976.
[33] Klaus Truemper. On the delta-wye reduction for planar graphs. J. Graph Theory 13(2):141–148,
1989.
[34] Klaus Truemper. Matroid Decomposition. Academic Press, 1992.
[35] Donald Wagner. Delta-wye reduction of almost-planar graphs. Discrete Appl. Math. 180:158–167,
2015.
[36] Hassler Whitney. Congruent graphs and the connectivity of graphs. Amer. J. Math. 54(1):150–168,
1932.

