Minimum Cut of Directed Planar Graphs in O(n log log n) Time

arXiv:1512.02068v2 [] 12 Nov 2016

Shay Mozes
IDC Herzliya
smozes@idc.ac.il

Cyril Nikolaev
University of Haifa
cyril.nikolaev@gmail.com

Yahav Nussbaum
University of Haifa
yahavnu@gmail.com

Oren Weimann
University of Haifa
oren@cs.haifa.ac.il

Abstract
We give an O(n log log n) time algorithm for computing the minimum cut (or equivalently,
the shortest cycle) of a weighted directed planar graph. This improves the previous fastest
O(n log3 n) solution. Interestingly, while in undirected planar graphs both min cut and min
st-cut have O(n log log n) solutions, in directed planar graphs our result makes min cut faster
than min st-cut, which currently requires O(n log n).

∗

The research was supported in part by Israel Science Foundation grant 794/13.

1

∗

1

Introduction

A cut is a partition of the vertex set of a graph into two non-empty sets X and Y . The capacity of
a cut is the total capacity of the edges from X to Y . The minimum cut problem asks to find a cut
with minimum capacity. The minimum st-cut problem asks, in addition, that vertex s belongs to
X and vertex t to Y . In undirected planar graphs, both problems can be solved in O(n log log n)time [14, 20], where n is the number of vertices of the graph. In directed planar graphs, however,
the fastest algorithms currently known run in O(n log3 n) for min cut [26], and in O(n log n) for min
st-cut [1]. In this work we show how to find a min cut in a directed planar graph in O(n log log n)
time. Therefore, we can currently solve min cut faster than min st-cut in directed planar graphs.
There is a well known duality between cuts in a planar graph and cycles in the dual planar
graph. A minimum cut in a planar graph is a shortest cycle in the dual planar graph. It follows
that any algorithm for finding the minimum cut in a planar graph can also find the shortest cycle
in a planar graph, and vice versa.
Undirected planar graphs. For an undirected planar graph G, Chalermsook, Fakcharoenphol
and Nanongkai [3] gave a simple algorithm that finds the minimum cut by recursively separating
the dual graph G∗ with shortest path separators. At each recursive step, the CFN algorithm applies
a min st-cut algorithm1 in O(n log n) time. This gives an O(n log2 n)-time algorithm for undirected
min cut. Improvements to this running time are based on using faster min st-cut algorithms in the
CFN algorithm. One such algorithm is that of Reif [23], which is a divide and conquer algorithm
over a shortest s-to-t path. We refer to this algorithm as the shortest-path based algorithm. Italiano et al. [14] showed how to use a technique by Fakcharoenphol and Rao [10] to implement the
shortest-path based algorithm in O(n log log n) time. Plugging this into the CFN algorithm yields
an O(n log n log log n) time algorithm for undirected min cut [14].
A second min st-cut algorithm in undirected planar graphs is that of Kaplan and Nussbaum [16].
This algorithm is based on a divide and conquer algorithm on an s-to-t path that is not necessarily
a shortest path, but is small in terms of the number of its vertices. We refer to this algorithm as the
small-path based algorithm. In the paper mentioned above, Italiano et al. [14] used the fact that
the small-path based algorithm runs in sublinear time when the small path has a sublinear number
of vertices, in order to design a min st-cut oracle with sublinear query time and O(n log log n)
preprocessing time. Łącki and Sankowski [20] showed how to efficiently represent and maintain the
shortest path separators and the information required by the small-path based min st-cut oracle of
Italiano et al. along the execution of the CFN algorithm. This allowed them to implement each of
the O(log n) recursive levels of the CFN algorithm in sublinear time. The overall running time is
O(n log log n), which is the current state of the art for min cut in undirected planar graphs. Note
that, in undirected planar graphs, both min cut and min st-cut currently take O(n log log n) time.
Directed planar graphs. The min cut in directed planar graphs, as noted in [25], can be found
in O(n3/2 ) time with a simple use of planar separators. Wulff-Nilsen [26] used the afore-mentioned
technique of Fakcharoenphol and Rao, to bring the running time down to O(n log3 n), which is
the fastest algorithm to this problem prior to the current work. For min st-cut in directed planar
graphs, the fastest known algorithm is the O(n log n)-time max st-flow algorithm of Borradaile and
Klein [1]. Note that in the directed case there is a gap between the O(n log n)-time algorithm for
min st-cut [1] problem, and the min cut problem which, until the present work, required O(n log3 n)
time.
1

Actually, CFN [3] use a max st-flow algorithm. They cite [24], but that algorithm is flawed, as was pointed out
by Borradaile and Klein [1], who also gave a correct algorithm.

1

Our results and techniques. In this paper, we present an O(n log log n) time algorithm for
finding the minimum cut (and hence also the shortest cycle) in a weighted directed planar graph.
We believe this is a significant advance on a fundamental optimization problem.
First, we make a simple observation, that was somehow overlooked, showing that the structural
lemma underlying the O(n log2 n)-time CFN algorithm [3] (for min cut in undirected planar graphs)
can actually be proven for the directed case as well. It is then easy to modify the CFN algorithm
to work for directed planar graphs in the same complexity; In undirected graphs, a minimum cut
separating s and t is a minimum st-cut. In directed graphs it may be a ts-cut. We therefore compute
both a min st-cut and a min ts-cut at each step of the recursion of the CFN algorithm. The running
time of the algorithm remains O(n log2 n).
Recall that improving upon the CFN algorithm in the undirected case required faster min st-cut
algorithms. However, both the shortest-path based algorithm, and the small-path based algorithm,
rely heavily on the graph being undirected. Consequently, it seems that getting faster algorithms for
directed min st-cut is very difficult, and that, therefore, any progress on the minimum cut problem
in directed planar graphs is unlikely. Surprisingly, we show this is not the case. We make another
simple observation which bypasses this difficulty. We show that, while the shortest-path based min
st-cut algorithm does not work in the directed setting, it does work in the directed setting when the
min st-cut happens to be the global minimum cut! Though simple, this surprising observation is a
main conceptual contribution of our work. This observation alone immediately implies that Italiano
et al’s O(n log log n) implementation of the shortest-path based min st-cut algorithm [14] can be
used in the CFN algorithm to find the min cut in directed planar graphs in O(n log n log log n) time.
Getting the running time down to O(n log log n) turns out to be much more difficult. The
small-path based algorithm, on which Łącki and Sankowski’s algorithm is based, heavily relies on
the graph being undirected, and we do not know how to use it in the directed setting, even for
finding the global min cut. Instead, we develop an implementation of the CFN algorithm that
uses the shortest-path based algorithm, rather than the small-path one. In this implementation,
each recursive step takes sublinear amortized time rather than worst case time as in Łącki and
Sankowski’s. We believe this yields a somewhat simpler algorithm, even for undirected min cut,
since the small-path based min st-cut oracle is quite complicated.
The most technically involved part of our contribution is in overcoming the difficulties that arise
when combining the efficient implementation of the shortest-path based algorithm a la Italiano et
al. with the implicit representation of Łącki and Sankowski. The result is the first directed variant
of Reif’s algorithm and the first to handle non-simple directed cycles. An interesting component
in our solution is the use of auxiliary non-planar (but bounded genus) graphs. This allows us to
guarantee that certain subpaths that are represented implicitly posses structural properties that are
required for the correctness of our algorithm. It is often the case that algorithms for planar graphs
are used in algorithms for bounded genus graphs. Here an algorithm for bounded genus graphs is
used for solving a problem on planar graphs. We find this use very interesting. An overview of the
difficulties and their resolution can be found in Section 3.1.
Beyond making significant progress on a fundamental optimization problem using an interesting
and technically challenging solution, our result puts the landscape of planar minimum cut problems
in an interesting situation. Whereas undirected minimum cut, undirected minimum st-cut and
directed minimum cut can all be solved in O(n log log n), we only know how to compute directed
minimum st-cut in O(n log n) time. This may hint that the algorithms for min st-cut and max
st-flow in directed planar graphs can also be improved.
Bounded genus graphs. For bounded genus graphs, some of the algorithms above [5, 7, 25, 26]
work with a minor modification. In particular, it is possible to show that, on a weighted directed

2

graph with genus g, the algorithm of Djidjev [5] finds the shortest cycle in O(g 1/2 n3/2 ) time, and
the algorithm of Wulff-Nilsen [26] in O(gn log2 n + n log3 n) time. We show how to use ideas from
our planar algorithm to find a shortest cycle in a graph of genus g in O(g 2 n log n) time with high
probability or O(gn log2 n) time in the worst case.

2

Preliminaries

In this section we provide necessary background and definitions. Most of the material covered is
not new. However, this section does contain a number of novel insights and observations that are
original contributions of this work. These are clearly indicated where appropriate.
Basic concepts. We assume basic familiarity with planar graphs, such as familiarity with the
definition of the planar dual and the duality of cuts and cycles. Let G be a simple directed planar
graph with n vertices and non-negative arc weights. A directed path P is a sequence of arcs
P = v0 v1 , v1 v2 , . . . , vk−1 vk . It is a directed cycle if, in addition, v0 = vk . An undirected path (cycle)
is a sequence of edges such that reorienting some of the edges yields a directed path (cycle). Unless
otherwise stated, all paths and cycles are directed. We write u <P v to denote that vertex u appears
before vertex v in the path P . We denote by P [u, v] the subpath of P starting at vertex u and
ending at vertex v, and by P (u, v), the subpath P [u, v] without its first and last edges. Also, P [·, a]
(P [a, ·]) denotes the prefix (suffix) of P ending (starting) at a. We denote by rev(uv) the arc vu,
and by rev(P ) the path whose arcs are the reverse of the arcs of P in reverse order. We denote the
number of arcs on path P by |P |. The length of P is the sum of lengths of P ’s arcs.
We say that a path P crosses another path Q if there is a path R that is a common subpath of
P and Q such that (i) the first (last) vertex of R is not the first (last) vertex of P or Q, and (ii)
the edge of P that precedes the subpath R enters Q from one side and the edge of P that follows
R leaves Q from the other side. See Figure 1. The absolute value of the number of times P crosses
Q from right to left minus the number of times P crosses Q from left to right is called the crossing
number of P and Q. Its parity is called the the crossing parity. The crossing number (parity) of a
primal path P and a dual path Q is defined as the (parity of the) number of arcs of P whose duals
belong to Q minus the number of reverses of arcs of P whose duals belong to Q.

Q

P

P

Q

Q

P

Figure 1: On the left, the path P (solid) crosses the path Q (dashed). On the middle, P does not
cross Q. On the right, P crosses Q three times (all from right to left) so their crossing parity is odd.
We say that a (possibly non-simple) cycle C encloses a face f if a path starting at a virtual
vertex embedded in the infinite face and ending at a virtual vertex embedded in f crosses C an odd
number of times. A vertex or an edge x incident to a face f are enclosed by C if f is enclosed by C.
If x is enclosed by C but x 6∈ C then x is said to be strictly enclosed by C. The subgraph enclosed
3

by a cycle C is called the interior of C and the subgraph not enclosed by C is called the exterior of
C (C itself belongs to both the interior and the exterior).
Unique shortest paths. We assume throughout the paper that shortest paths in the graph are
unique. This assumption simplifies the presentations, but is also used in proving the correctness
of our algorithm. In general graphs, this assumption can be achieved with high probability by
applying the Isolation Lemma [21, 22]. Indeed, prior algorithms for ebedded graphs that require
this assumption usually use the isolation lemma, which results in a randomized algorithm with high
probability of success. However, recently, Erickson and Fox [11] have shown a simple way to enforce
this assumption deterministically in graphs embedded on a genus g surface with O(g) overhead (i.e.,
with no overhead for planar graphs).
Multiple-source shortest paths (MSSP). Klein [17] described an algorithm that, given a
directed planar graph G with arc lengths, a face f∞ of G, and a shortest path tree T rooted at
some vertex of f∞ computes, in O(n log n) time, a data structure representing all shortest path trees
rooted at each vertex of f∞ . The data structure can be queried in O(log n) time for the distance
between any vertex u ∈ f∞ and any other vertex v ∈ V (G). The data structure can also be queried
for the arcs of the shortest u-to-v path (instead of just the distance), in O(log log ∆) amortized
time per reported arc. Here ∆ is the maximum degree of a vertex in G. We refer to this algorithm
and data structure as MSSP (multiple-source shortest paths). Cabello, Chambers and Erickson [2]
described an MSSP algorithm for genus-g graphs. The algorithm assumes unique shortest paths
and runs in O(gn log n) time with high probability (using the isolation lemma), or in deterministic
O(g 2 n log n) time (using the new technique of Erickson and Fox [11]).
r–divisions, Dense distance graphs, and FR-Dijkstra. An r-division [12] of G, for some
r < n, is a decomposition of G into O(n/r) pieces, where each piece has at most r vertices and
√
O( r) boundary vertices (vertices shared with other pieces). There is an O(n) time algorithm that
computes an r-division of a planar graph with the additional property that the boundary vertices in
each piece lie on a constant number of faces of the piece (called holes) [10, 18]. The dense distance
graph (DDG) of a piece R is the complete graph over the boundary vertices of R. The length
of edge uv in the DDG of R equals to the u-to-v distance inside R. Note that the DDG of R is
non-planar. The DDG of an r-division is the union of DDGs of all pieces of the r-division. Thus,
√
the total number of vertices in the DDG is sublinear O( nr · r) = O( √nr ), and the total number of
edges is linear O( nr · r) = O(n). The DDG can be computed in O(n log r) time using the MSSP
algorithm [17]. Fakcharoenphol and Rao [10] described an implementation of Dijkstra’s algorithm,
nicknamed FR-Dijkstra on the DDG of an r–division. Computing shortest paths in the DDG using
FR-Dijkstra takes O( √nr log2 ( √nr )) time which is proportional (up to polylog factors) to the number
of vertices of the DDG, and sublinear in n, the number of vertices of G.
A directed version of the CFN algorithm. The algorithm of Chalermsook et al. [3] computes
a minimum cut in an undirected planar graph. We describe their algorithm for the directed case.2
For this we need the following lemma, which implies that we may assume that the shortest cycle in
the graph crosses any shortest path at most once.3
Lemma 1. Let P be a shortest u-to-v path for a pair of vertices u, v. There is a globally shortest
cycle C such that either C and P are completely disjoint or they share a single subpath.
Let o be an arbitrary vertex in G. A shortest path separator [19] is an undirected cycle S
consisting of an edge uv, a shortest (directed) o-to-u path P , and a shortest (directed) o-to-v path
2
3

The observation that the CFN algorithm can be made to work in the directed case is novel.
A similar lemma appeared without proof in [3], but that paper did not consider directed graphs.

4

P 0 , such that both the interior and exterior of the cycle consist of at most 2/3 of the total number
of the faces of G. Such a separator can be found in O(n) time [3, 19].
Given a shortest path separator S, the shortest cycle in G is either in the interior of S, in the
exterior of S, or crosses S. The former two options are handled recursively. We describe how to
find the shortest cycle C that crosses S. Since C crosses S, it does so at least twice. By Lemma 1,
we may assume that C crosses P exactly once, and so the vertex o and the edge uv are in two
different sides of C. Let s∗ be the face adjacent to the first edge of P external to S, and let t∗ be
the face adjacent to uv internal to S. The cycle C is the shortest cycle that separates s∗ and t∗ .
See Figure 2. In the dual planar graph, C is either a minimum st-cut or a minimum ts-cut, where
s and t are the vertices dual to the faces s∗ and t∗ , respectively. Therefore, C can be found by two
executions of a min st-cut algorithm, which takes O(n log n) time [1].
o
s∗

C

t∗
u

v

Figure 2: If the shortest cycle C crosses the separator S, then it crosses the shortest o − u path
once and the shortest o − v path once. In this case, the vertex o (together with the face s∗ ) and the
edge uv (together with the face t∗ ) are in two different sides of C.
Overall, the recursive decomposition of the graph using shortest path separators has O(log n)
levels of recursion. Before each recursive level we can remove every vertex of degree two, and merge
its two adjacent edges into a single edge (combining the lengths of the two). This guarantees that
the total size of all subgraphs in the same level of the recursion is O(n), and so all executions of the
min st-cut algorithm in this level take total O(n log n). The overall running time is thus O(n log2 n).
Reif ’s algorithm. Reif’s algorithm [23] (referred to in the introduction as the shortest-path based
algorithm) is used to find a minimum st-cut in an undirected planar graph. We describe it as an
algorithm for a directed graph G.4 Given a shortest s∗ -to-t∗ path P in G, Reif’s algorithm finds the
shortest cycle C that crosses P exactly once.5 In undirected graphs C corresponds to a min st-cut
in the dual graph, but in directed graphs it does not. The crucial observation, however, is that this
is exactly the property required by the CFN algorithm for finding the global min cut.
4

We note that the literature is infested with inaccuracies on the use of Reif’s algorithm in the directed case. Janiga
and Koubek [15] attempted to generalize Reif’s algorithm to compute a min st-cut in directed planar graphs. They
find the shortest cycle that separates s∗ and t∗ and crosses some s-to-t path at a particular vertex. This cycle is
used to divide the problem into two separate subproblems. However, this algorithm is flawed [16]. The cycle found
by Janiga and Koubek is not necessarily simple, nor do they make sure it corresponds to an st-cut rather than to
a ts-cut. Erickson and Nayyeri [8] remarked that the algorithm of Janiga and Koubek appears to find the smaller
between the minimum st-cut and minimum ts-cut. However, this claim is also false. The cycle dual to the min st-cut
may cross the cycle used by Janiga and Koubek to divide the problem. In this case the cycle corresponding to the
min st-cut will never be found because it does not belong to any of the two subproblems.
5
This view of Reif’s algorithm does not require deep insights but is novel nonetheless. It does require a slightly
careful proof of Lemma 2, which is trivial in the undirected case.

5

We assume that the cycle C crosses the path P from right-to-left (the other case is symmetric,
and the algorithm tries both). Reif’s algorithm makes an incision along P and replaces every
vertex pi of P with two vertices p0i and p1i . Every edge pi pi+1 of P is replaced with two edges p0i p0i+1
and p1i p1i+1 . Every edge pi v is replaced with an edge p0i v (p1i v) if it emanates left (right) from P .
Similarly, every edge vpi is replaced with an edge vp0i (vp1i ) if it enters P from its left (right) side.
See Figure 3.
p0

p11

p01
p12

p13
p14

p02

p03
p04
p0ℓ−1
p1ℓ−1

pℓ

Figure 3: An incision along P . The newly created face is shaded.
Let Pi be a shortest p0i -to-p1i path. In the original graph (i.e., before the incision) Pi is a
shortest simple cycle Ci which crosses P exactly once, at pi . Finding the desired cycle C therefore
amounts to finding the shortest among all Pi s. Reif’s algorithm does this in O(n log n) time using
divide-and-conquer based on the following lemma.
Lemma 2. Let Pi be a shortest p0i -to-p1i path. For j 6= i, there is a shortest p0j -to-p1j path Pj that
does not cross Pi .
Reif’s divide-and-conquer algorithm proceeds as follows. It first finds a shortest p0i -to-p1i path Pi
for i = |P |/2. This takes O(n) time using [13]. The path Pi divides the graph into two subgraphs.
By Lemma 2, each subgraph can be handled separately. The algorithm therefore recurses on both
subgraphs. To get a total running time of O(n log n), in each recursive level we remove vertices of
degree two and merge their two adjacent edges as explained in the CFN algorithm above.
Italiano et al’s implementation of Reif ’s algorithm. Italiano et al. [14] developed a faster
O(n log log n) implementation of Reif’s algorithm to find a minimum st-cut in undirected planar
graphs. As above, we observe that, when applied to a directed planar graph, the algorithm computes
the shortest simple cycle crossing P exactly once. Plugging this into each of the log n levels of the
CFN algorithm yields an O(n log n log log n) algorithm for the directed global min cut problem.
The algorithm of Italiano et al. computes an r-division with r = log6 n. As in Reif’s algorithm,
an incision is made in G along P . Note that the incision may cut pieces. Every such piece R, is
replaced with a set of pieces, one for each connected component of R following the incision. For
every vertex pi of P that was a boundary vertex prior to the incision, both p0i and p1i are defined
to be boundary vertices after the incision. The DDG of all resulting pieces can be computed in
O(n log r) = O(n log log n) time using the MSSP algorithm [17], and we can run FR-Dijkstra on
√
this DDG in sublinear O((n/ r) log2 n) = O(n/ log n) time.
The first stage of the algorithm (called coarse Reif) finds the shortest cycles Ci that cross P once
at a boundary vertex. The running time of this step is dominated by the O(n log log n) time required
to compute the DDG. It implements Reif’s algorithm by only considering boundary vertices, and
uses FR-Dijkstra to quickly compute the shortest paths Pi . The next step, called refined Reif,
6

computes the shortest cycles that cross P at non-boundary vertices. It implements Reif’s algorithm
within the subgraphs enclosed by the cycles found in the coarse Reif step. The running time of this
step is also O(n log log n).
Italiano et al. used the main ideas from their fast implementation of Reif’s algorithm to design
a min st-cut oracle for undirected planar graphs that, after O(n log log n) preprocessing can answer
min st-cut queries, and support edge insertions and deletions, in O(n/ log n) time per query or
operation. This oracle is based on a min st-cut due to Kaplan and Nussbaum [16], rather than on
Reif’s. The oracle was then used by Łącki and Sankowski [20] to solve undirected global min cut as
we explain next.
The algorithm of Łącki and Sankowski for undirected global min cut. The currently
fastest algorithm for undirected global min cut is that of Łącki and Sankowski [20]. Its running
time is O(n log log n). Their algorithm emulates the CFN algorithm on the DDG. The bottleneck
in the O(n log n log log n) global min cut algorithm of Italiano et al. [14] is the recomputation, in
O(n log log n) time, of the DDG at each of the O(log n) levels of the CFN recursion. Łącki and
Sankowski [20] showed how to build the DDG just once (in O(n log log n) time) and maintain it (in
sublinear time) throughout all the recursive calls of the CFN algorithm. They further show how to
find a shortest path separator in O(n/ log n) time, and maintain the information required by the
min cut oracle of Italiano et al. to compute min st-cuts in O(n/ log n) time. Thus, the running
time of the whole algorithm is actually dominated by the O(n log log n)-time preprocessing step of
building the DDG.
Łącki and Sankowski described how to efficiently keep track of the partition of the graph into
subgraphs when cutting along a cycle Ci that is only represented in the DDG (this is called implicitly
cutting the graph). The vertices of the DDG (i.e., the boundary vertices of G) are partitioned into
the interior and exterior of Ci according to the embedding of Ci in G. The time required is
proportional to the number of boundary vertices, not to the size of G. We use this technique in our
algorithm without change. A brief description of the so called recursion graph and division edges
used in their technique appears in Section 5 for completeness.

3

Our Algorithm

Our observations from the previous section allow us to design a version of the CFN algorithm that
is based on an efficient directed variant of Reif’s algorithm. Our algorithm begins by computing
an r-division of the graph G, and a corresponding DDG for r = log8 n. This takes O(n log r) =
O(n log log n) time. Then, as in [20], a shortest path tree of G, rooted at some boundary vertex,
is computed and maintained as a shortest path tree in the DDG. The dividing step identifies a
balanced shortest path separator composed of two shortest paths P and P 0 plus a single edge e.
Let B = {b1 , . . . bp } be the boundary vertices along the shortest path P . Since P ends at a vertex
of e, which is not necessarily a boundary vertex, the suffix P [bp , ·] is fully contained in the piece
of the r-division containing e. The algorithm represents P by the sequence of boundary vertices B
plus all the vertices in the suffix P [bp , ·]. Note that P may have O(n) vertices but its representation
√
uses only O(n/ r) boundary vertices, and the O(r) vertices of P [bp , ·]. The algorithm cuts the
graph along the separator, as done in [20], and recurses on the interior and exterior subproblems.6
Problems with fewer than r boundary vertices are not handled recursively, but by any existing
6

Note that, since the graph is directed, edges of the DDG in a subproblem may represent paths that cross the
separator an even number of times. This does not affect the correctness of the algorithm because we are interested
in the globally minimum cycle. On the one hand, such paths are at least as short as the shortest path restricted to
the subproblem. On the other hand, such paths correspond to valid paths in the original graph.

7

directed global min cut algorithm (see analysis). In addition, we invoke a global min cut algorithm
on every piece R individually.
In the conquering step, we wish to find the shortest cycle that crosses P exactly once. This is
where our algorithm significantly differs from [20]. Instead of using the min st-cut oracle of [14], we
present a directed variant of Reif’s algorithm (which we refer to as the inner recursion). In what
follows we assume, without loss of generality, that the shortest cycle C we are looking for crosses P
from right to left. The other case is symmetric, and the algorithm implements both.
Performing an incision along P . We now describe the procedure for performing an incision
along P (the preliminary step of Reif’s algorithm). Consider a piece R. If any subpath of P
connects two different holes of R or if t is a vertex of R then we perform the incision of R explicitly.
Otherwise, the incision is performed implicitly. In an explicit incision, a piece R is explicitly cut into
subpieces, and a DDG is computed from scratch for each of the resulting subpieces by rebuilding
their MSSP data structure [17]. In an implicit incision, the edges of the DDG of R are partitioned
among the DDGs of the subpieces of R, without actually cutting R and recomputing the DDG.
This is done as follows. The subpaths of P going through R break R into connected components.
See Figure 10(left). Each of these connected components is considered from now on as an individual
subpiece of R. The division of the boundary vertices of R (on all holes of R) into the resulting
subpieces is inferred as in [20], using the skeleton graph and the division edges technique. For each
subpiece Q we would like the length of each DDG edge uv to correspond to the shortest u-to-v
path in Q (rather than in R). However, this would require recomputing the DDG of Q which we
cannot afford. Instead, we use the original DDG edge uv in R. This edge corresponds to a shortest
u-to-v path ρ that is allowed to venture in R outside Q. It turns out that this is problematic only
when the region R contains holes. For ease of presentation we ignore this point for now and proceed
with describing the algorithm. We will later discuss the difficulties manifested by holes and their
resolution.
Applying Reif ’s algorithm to P . Having made the incision along P in the DDG, we now wish
to perform Reif’s divide-and-conquer on the path P . However, since an edge of the graph might
appear on the path P in many different levels of the CFN recursion, we cannot afford to handle all
edges of P at every recursive level. We next show that it suffices to handle each edge e at most
once, at the earliest level of the CFN recursion at which e ∈ P .
We classify the edges of P into two types, active and inactive. An edge pi pi+1 is inactive if it
was already part of the separator in some earlier level of the CFN recursion. Observe that (1) the
active edges form a suffix of P , (2) we only need to find the shortest p0i -to-p1i path Pi if pi pi+1 is
active (if pi pi+1 is inactive then every cycle that goes through pi must also go through pi+1 ), and
(3) we can discover the active suffix by revealing the edges of P one by one (each in O(log r) time
using the MSSP data structure until we reach an inactive edge.
The first step of our Reif variant therefore discovers the active suffix of P in time O(x log r)
where x is the number of active edges in P . Next, we wish to find the shortest p0i -to-p1i path Pi
where pi is the middle vertex of the active suffix of P . Let R denote the piece containing pi . We
(temporarily) add p0i and p1i as boundary vertices and add appropriate DDG edges as follows. If
there exists a subpath of P whose endpoints lie on different holes of R, it means that we have
already explicitly built the new DDG of R’s subpieces (after the incision) by computing new MSSP
data structures (see above). In this case p0i and p1i both belong to the same subpiece Q, we add
to the DDG an edge from p0i to every boundary vertex of Q, and from every boundary vertex of
Q to p1i . The lengths of these edges are obtained by querying the new MSSP data structure of Q.
Otherwise, the endpoints of all subpaths of P in R lie on the same hole so p0i and p1i belong to
different subpieces Q0 and Q1 of R. We add to the DDG edges from p0i to all vertices of Q0 and
8

from all vertices of Q1 to p1i . These distances are computed by querying the existing MSSP data
structures of R.
After connecting pi to the boundary vertices of R, we find the DDG representation of the path
Pi by running FR-Dijkstra from p0i to p1i on the DDG. Notice that while Pi is a simple path in the
DDG, it might correspond to a non-simple path in the underlying graph. This is because the implicit
DDG incision means DDG edges may correspond to subpaths in the graph before the incision. We
later show how to ensure that this does not violate the correctness of the algorithm.
Reif’s algorithm proceeds by cutting the graph along the cycle Ci that corresponds to Pi and
recursing on the interior and exterior. We implement this by cutting the DDG implicitly along Pi
using the division edge technique, obtaining two DDGs denoted DDG s (containing s) and DDG t
(containing t). We assign the prefix P [s, pi ) to DDG s and the suffix P (pi , t] to DDG t , and then
recurse on both subgraphs.
We note that, for undirected graphs, the algorithm above is complete and correct. We believe
that, for the undirected case, it is simpler than the algorithm of Łącki and Sankowski [20] because
it does not rely on the rather complicated min st-cut oracle of Italiano et al. [14].

3.1

A flaw in the algorithm and its resolution

Since our algorithm implements the CFN algorithm, in order to prove the correctness of our algorithm it suffices to prove that, at each level of the CFN recursion, if the global min cycle C crosses
the shortest path separator then our algorithm will find C. Since at each level of the CFN recursion
our algorithm implements Reif’s algorithm, it suffices to show that any p0i -to-p1i path Pi found by
our algorithm is either C, or C is represented in one of the resulting DDGs or DDGt obtained by
implicitly cutting the DDG along Pi . However, in directed graphs this might actually be false! We
first explain at a high level how the problem arises, and then explain how to resolve it.
Recall that the DDG of a subpiece Q used at some point in the execution of our algorithm is
not obtained by explicitly computing shortest paths between the boundary nodes in that subgraph,
but by using edges from the DDG of the original piece R. This implies that the shortest paths that
correspond to DDG edges of Q may actually venture outside Q. In particular, while the p0i -to-p1i
path Pi found by our algorithm is a simple cycle in the DDG that crosses P exactly once (at pi ), it
may actually correspond to a non-simple cycle Ci that crosses P more than once. See Figure 4(b,c).
It turns out that in such cases C may actually cross Ci . This is problematic because the algorithm
implicitly cuts the DDG along Pi and recurses on DDGs and DDGt . If C crosses Pi then it seems
that C will be represented in neither DDGs nor DDGt .
To overcome this problem we characterize the structure of the subpaths of Pi that cross P . We
call such subpaths fingers. We show that each finger is restricted to a single piece R of the r–division.
We further show that the problem mentioned above does not occur in fingers that enclose no holes
of R (see Figure 4(c)). The reason is that, in the absence of holes, all boundary vertices on the
global min cut do lie on the same side of Ci . Therefore, if a finger encloses no holes, even though C
might cross Ci , it is still represented in either DDGs or DDGt . Since the number of holes in each
piece is constant, we can precompute a constant number of versions of the DDG of each piece R.
In each version, the paths corresponding to DDG edges interact with the holes of R in a prescribed
way. We can then carefully choose which version of the DDG of R to use when computing Pi so
as to ensure that each finger of Ci is locally homologous to P in roughly the following sense: the
subgraph sandwiched between the finger and P contains no holes of R.
We now explain the changes in the algorithm in detail. Recall the description of the implicit
incision along P . Let R be a piece of the r–division. The path P breaks R into subpieces. For
each subpiece Q we would like the length of each DDG edge uv to correspond to the shortest u-to-v
9

v

u
s

pi

t

s

py

pi
b

(a)

u
px

t

s

v
py

pi

a

b

px

t

a

(c)

(b)

Figure 4: In all diagrams, the shortest s-to-t path P is shown in red, the global shortest cycle C in green,
and a the shortest cycle Ci that crosses P at the middle vertex pi in blue. (a) When Ci is simple it is not
crossed by C, so breaking the problem along Ci is valid. (b) Even though Pi is a simple path in the DDG,
the cycle Ci it corresponds to in the underlying graph (blue) is not simple. A piece R of the r-division is
shown (shaded). The underlying path of the DDG edge ab crosses P even after an implicit incision along
P . The px -to-py subpath of Pi is called a finger. In this case, the globally shortest cycle C might cross Ci
at the finger. Dividing the problem along Ci is problematic because C has boundary vertices in both the
exterior (e.g., u) and the interior (e.g., v) of Pi . (c) When no holes are “sandwiched” between the finger and
P , all boundary vertices of the globally shortest cycle C are in the exterior of Ci even though C crosses Ci .
Therefore, C is still represented in DDGs after breaking the problem implicitly along Ci .

path in Q (rather than in R). However, this would require recomputing the DDG of Q which we
cannot afford. Instead, we use the original DDG edge uv in R. This edge corresponds to a shortest
u-to-v path ρ that is allowed to venture in R outside Q. The path ρ can be decomposed so that
the maximal subpaths of ρ in R \ Q start and end on P . We call these subpaths simple fingers of
ρ. The base of a simple finger is the subpath of P between the endpoints of the finger. For the
correctness of our algorithm we require that:
Property 1. For every simple finger S, the cycle formed by S and its base encloses no holes of R.
To achieve Property 1, instead of precomputing a single DDG for each piece R of the r-division,
we compute many DDGs (exponential in the number of holes in R, which is O(1)). When information
about a DDG edge uv of Q is required (e.g., by FR-Dijkstra or when implicitly cutting the graph
open), it is reported using the precomputed version of the DDG of R that corresponds to the subset
of holes that belong to Q. We next explain this preprocessing step.
The Z2 -homology cover. We use a special case of the Z2 -homology cover developed by Erickson
and Nayyeri [8] for bounded genus graphs. To the best of our knowledge this is the first time that
homology covers are used for planar graphs. Our description is less general than the one in [8], and
differs in some of the details to make the presentation shorter and suitable for our application. We
perform the following preprocessing for each of the O(1) possible subsets H of holes of R. For each
hole h` ∈ H we choose an arbitrary path A` in the dual of R connecting the external hole of R with
h` . We construct a graph, called the Z2 -homology cover of R by making, for each ` = 1, . . . , |H|,
an incision along A` . See section 2, and Figure 3 for a detailed definition of an incision. Note, that
here the incision is performed in the dual of R. In the primal, this can be thought of as splitting
each (primal) edge of A` into two complementary half-edges that are not connected to each other.
See Figure 10. Let R0 denote the resulting (primal) graph. The Z2 -homology cover is constructed
by glueing together 2|H| copies of R0 . Each copy is labeled with a distinct |H|-bit string. For labels
b and b0 differing in a single bit j, the corresponding copies of R0 are glued along the complementary
half edges of Aj . See Figure 10. The resulting graph is not planar, but can be embedded on a surface
with constant (albeit exponential in |H|) genus.7 We can therefore use the MSSP data structure
The dual of this graph is essentially a hypercube (which has genus 2|H| ). That is, after deleting from each copy
of R0 all edges that do not belong to the infinite face, the interior of each copy becomes a single face and the dual of
7

10

for bounded genus graphs [2] on the Z2 -homology cover of R in O(r log r) time. Let BQ be the set
of boundary vertices of Q that do not belong to holes in the subset H. The MSSP data structure
can report in O(log r) time the distance between any vertex u0...0 of BQ (i.e., the boundary vertex
u in the copy with the all-zero label) and any vertex v b of BQ (i.e., the boundary vertex v in the
copy with label b). A shortest u0...0 -to-v b path in the Z2 -homology cover corresponds to a shortest
u-to-v path in R under the restriction that for every A` it’s crossing parity is even (odd) iff the `th
bit of b is zero (one). See Figure 10. When information about a DDG edge uv of Q is required
during the execution of the algorithm, it is fetched by querying the MSSP data structure for the
Z2 -homology cover created for the appropriate subset H of the holes of R. For the query we need
to figure out the label b of v to be used when querying the MSSP data structure. This choice is
described in Section 4.5.

3.2

Correctness

The correctness of our algorithm follows from the following lemma, which states that in the way we
cut the DDG we do not lose the globally shortest cycle C.
Lemma 3. If the globally minimum cycle C is the p0k -to-p1k path in the DDG for some pk ∈ P , then
either pk = pi and C = Ci , or pk ∈ P [s, pi ) and C is the p0k -to-p1k path in DDG s , or pk ∈ P (pi , t]
and C is the p0k -to-p1k path in DDG t .
In the rest of this section we lay out the structural properties that facilitate the proof of Lemma 3.
The proof itself is a rather complicated case analysis and is deffered to Section 4.4. In a nutshell,
our analysis shows that, in every possible case, either C crossing Ci leads to a contradiction or the
crossing is such that all the boundary vertices of C (and hence all the DDG edges of C) belong to
either DDG s or DDG t .
Observe that in the DDG both C and Ci cross P exactly once (from right to left). In the underlying graph however, Ci may cross P some odd number of times. The cycle Ci can be partitioned
into internally disjoint subpaths that do not cross P at all. See Fig. 6 for an illustration. Starting
from pi , Ci is first composed of zero or more alternating px -to-py subpaths where y < x < i (otherwise, if x < y then by the unique shortest paths assumption Ci [px , py ] should be equal to P [px , py ]).
These subpaths either begin by emanating left of P and end by entering left of P or they begin by
emanating right of P and end by entering right of P . We call the former subpaths a finger of Ci
above P and the latter a finger of Ci below P . After such zero or more fingers, there is exactly one
p` -to-pj subpath that begins by emanating left of P at p` and ends by entering right of P at pj . We
call this p` -to-pj subpath the separation finger. Observe that by definition ` ≤ i. If j < i, then it
must be (by the unique shortest paths assumption) that Ci [pj , pi ] = P [pj , pi ]. Otherwise, if j ≥ i,
then Ci [pj , pi ] consists of zero or more alternating px -to-py subpaths where i < y < x < j. These
subpaths can be fingers of Ci above P or below P .
Note that, because the DDG was implicitly cut along P , for every DDG edge uv of Ci that
belongs to a piece R such that P separates R into multiple parts, both u and v belong to the same
part Q. If the path corresponding to the DDG edge uv crosses P , it must do so an even number of
times, and create at least one finger that belongs to R \ Q. recall that any such finger is called a
simple finger. Hence:
Observation 1. Every px -to-py finger S of Ci [pi , p` ] below P is a simple finger. Thus S is contained
in a single piece of the r-division and (by Property 1) S encloses no holes.
this Z2 -homology cover is a hypercube. Adding back the deleted (planar) portions does not increase the genus.

11

Observation 2. Every px -to-py finger S of Ci [pj , pi ] above P is a simple finger. Thus S is contained
in a single piece of the r-division and (by Property 1) S encloses no holes.
Note that by our incision procedure we have that fingers of Ci that are confined to a single
piece R do not enclose any holes of R. Also note that two fingers of Ci can cross each other (thus
making Ci non-simple). However, by the following claim, this can only happen if one finger is the
separation finger and the other is a finger of Ci [pj , pi ] above P (Figure 6) or a finger of Ci [pi , p` ]
below P (Figure 7), or one finger is of Ci [pi , p` ] and the other is of Ci [pj , pi ] (Figure 8).
Claim 1. Ci can cross itself only if the crossing is (I) between the separation finger and a finger of
Ci [pj , pi ] above P , or (II) between the separation finger and a finger of Ci [pi , p` ] below P , or (III)
between a finger of Ci [pi , p` ] above (below) P and a finger of Ci [pj , pi ] above (below) P .
The remainder of the proof of Lemma 3 which consists of numerous cases appears in Section 4.4.

3.3

Analysis

All pre-computations are dominated by the O(n log r) = O(n log log n) time for computing the DDG
in all pieces of the r–division.
We first bound the time for performing incisions. The time to perform the implicit incisions
√
of P is proportional to the number of boundary vertices in the graph, which is O(n/ r) over all
subgraphs in a single level of the CFN recursion tree. Hence, over the entire run of the algorithm,
√
the cost of all implicit incisions is O((n/ r)·log n) = O(n). The time to perform an explicit incision
of a single piece R is dominated by the O(r log r) time of MSSP. Every time such an incision is
made because a DDG edge e of P connects two different holes of R, the number of holes in R
decreases (the two holes connected by e become a single hole). Since the number of holes in each
piece is constant, such explicit incisions occur a constant number of times per piece over the entire
execution of the algorithm. Hence, the total time spent on all such explicit incisions over all pieces
during the entire course of the algorithm is O((n/r) · r log r) = O(n log log n).
In each subproblem of the CFN recursion, the algorithm performs an explicit incision in the
piece R to which t (the last vertex of P ) belongs. Such incisions do not decrease the number of
holes, so we cannot charge for them globally as above. In subproblems containing Ω(r) boundary
vertices, the O(r log r) time of the implicit incision is dominated by the O(r log2 n) time for FRDijkstra computation. Subproblems with O(r) boundary vertices are called small subproblems and
are handled by running any existing algorithm for directed min cut (i.e., bootstrapping). Denote
the running time of this directed min cut algorithm by O(nf (n)). Then, as shown in [20], handling
all small subproblems takes O(nf (r)) time.
We now bound the time spent on FR-Dijkstra computations. Consider a non-small subproblem
at some level of the CFN recursion with b = Ω(r) boundary vertices and x active edges. The
√
algorithm finds Ci using FR-Dijkstra in O( r log r + b log2 n) time (the first term is the cost of
connecting the middle vertex pi to the DDG, and the second term is the cost of FR-Dijkstra).
The algorithm then recurses on the interior and exterior of Ci each containing at most x/2 active
edges. Contracting degree-2 edges in the DDG of every subproblem guarantees that, at each level
of the inner recursion, every boundary vertex appears in at most two subproblems with more than
two boundary vertices [14, 20]. Call a subproblem with at most two boundary vertices a tiny
subproblem. Thus, the total time for all non-tiny subproblems along all levels of the inner recursion
is O(b log2 n log x), which is O(b log3 n) since x = O(n). Since the sum over the boundary vertices of
√
all non-small subproblems at a single level of the CFN recursion is O(n/ r), and since the depth of
the CFN recursion is O(log n), the total time required for all FR-Dijkstra computations on non-tiny
√
subproblems throughout the algorithm is O(n log4 n/ r) = O(n).
12

We now bound the cost of tiny subproblems. This cost is dominated by the O(log r) time
required to connect pi to the (at most two) boundary vertices. The Dijkstra computation then
takes constant time. Since each tiny subproblem is associated with some active edge (an edge
whose endpoint is pi ), and since at this time this edge becomes inactive, the total number of tiny
problems along the entire execution of the algorithm is O(n), and the time to handle them all is
O(n log r) = O(n log log n).
Subproblems with no boundary vertices are handled by bootstrapping. I.e., by calling any
directed min cut algorithm in each piece of the r–division separately. This takes total O((n/r) ·
rf (r) = O(nf (r)) time.
Summing the different terms above we get that the total running time of the algorithm is
O(n log log n)+O(nf (r))+O(n)+O(n log log n)+O(nf (r))). Using the f (n) = log2 n (i.e., using [3]
for bootstrapping) results in a total running time of O(n log log n + n log2 (log n)) = O(n log2 log n)
for directed global minimum cut. Using the resulting algorithm in the bootstrapping (i.e., f (n) =
log2 log n) yields the claimed O(n log log n) running time for directed global minimum cut.

4

Missing Proofs and Additional Details

4.1

Proof of Lemma 1

Let C be a shortest cycle in G that shares two distinct vertices c1 and c2 with the path P , labeled
so that c1 <P c2 . If the subpath of C[c1 , c2 ] is different than P [c1 , c2 ], then we replace C[c1 , c2 ] with
P [c1 , c2 ]. Since P is a shortest path, the cycle C remains a shortest cycle. We repeat this process
until the vertices and the edges of C that are also in P form a subpath of C, as required.

4.2

Proof of Lemma 2

The path Pi separates the graph into two subgraphs. The two vertices p0j and p1j are in the same
side of Pi . Let Pj be a simple shortest p0j -to-p1j path. If Pj crosses Pi then Pj must touch Pi after
the first such crossing since the two endpoints of Pj are in the same side of Pi . Let q1 be the first
vertex of Pj that also belongs to Pi , and let q2 be the last vertex of Pj that also belongs to Pi . It
must be that q1 <Pi q2 since otherwise Pj must cross itself (see Figure 5). The subpath of Pi [q1 , q2 ]
is a shortest q1 -to-q2 path. Replacing Pj [q1 , q2 ] with Pi [q1 , q2 ] results in a shortest p0j -to-p1j path Pj
that does not cross Pi , as required.

4.3

Proof of Claim 1

We prove that all other crossings are impossible since they imply that we can remove a subcycle
C 0 from Ci (thus making Ci shorter) while Ci still passes through pi and its crossing parity with P
remains the same:
• A finger cannot cross itself. This is because apart from its endpoints a finger does not include
any vertices of P and so if it crosses itself at vertex a it means that there is a cycle C 0
containing a but not containing any vertices of P .
• Two fingers cannot cross if they are both above P or both below P and are both in either
Ci [pj , pi ] or Ci [pi , p` ]. If they cross at vertex a then there is a cycle C 0 that (1) contains a,
(2) does not contain pi , and (3) crosses P an even number of times (since C 0 does not contain
Ci [p` , pj ]).

13

p1i

p1j

q1
p0

pℓ

q2

p0i

p0j

Figure 5: The path Pi (dashed ) separates the graph into two subgraphs. Both p0j and p1j are in the
same side of Pi . If the path Pj (solid ) crosses Pi such that the first vertex of Pj that is common
with Pi follows in Pi the last vertex of Pj that is also a vertex of Pi , then Pj must cross itself.
Note that, for clarity, we re-embedded the graph so that the new face created by the incision is the
infinite face.
• The separation finger cannot cross a finger of Ci [pi , p` ] above P or a finger of Ci [pj , pi ] below
P for the same reason as the previous case.
• A px -to-py finger f1 below P and a pw -to-pz finger f2 above P cannot cross. Assume for
contradiction that f1 first crosses f2 at vertex a. Consider the cycle C 00 composed of (1) the
subpath of f1 between px and a, (2) the subpath of f2 between a and pz , and (3) the subpath
of P between px and pz . Notice that at vertex a, Ci [px , ·] enters C 00 and must exit C 00 before
reaching py . It cannot exit at (1) because we proved that a finger f1 cannot cross itself, and
it cannot exit at (3) because a finger does not cross P , so it must exit C 00 at some vertex b of
f2 that belongs to Ci [a, pz ]. However, this means that both f1 and f2 contain a-to-b subpaths
in contradiction to unique shortest paths.

4.4

Proof of Lemma 3

To prove the lemma, we next show that at least one of DDG s or DDG t contains all the boundary
vertices of C. Suppose for the sake of contradiction that there are two boundary vertices on C that
do not belong to the same side of Ci . Let pk be the vertex where C crosses P . Let b1 , b2 be the first
pair of consecutive boundary vertices on C after pk that belong to different sides of Ci .
Assume w.l.o.g. that pk and b1 are on the same side of Ci . Let a be the first vertex of C after
b1 where C crosses Ci . First we consider the case where pk is strictly external to Ci . The finger S
containing a is one of three types:
1. S is the separation finger. In this case, since pk is external to Ci , there can be three options: (1)
j ≤ k < `, (2) k < j and k < `, (3) k ≥ `.
1.1 If j ≤ k < `, then Ci [pj , pi ] = P [pj , pi ] and pk is a vertex of Ci , so it is not strictly external
to Ci .
1.2 If k < j and k ≤ `, then let C 0 be the cycle C[pk , a] ◦ Ci [a, pj ] ◦ rev(P [pk , pj ]). Since pk is
external to Ci , then C[pk , a] is external to Ci . At vertex a, C enters C 0 . Observe that C[a, pk ]
does not cross P and needs to enter P from the right before reaching pk . This means that
either C[a, pk ] exits C 0 or it passes through pj . However, C[a, pk ] cannot exit C 0 at C[pk , a]
14

a
pi

s

pk

py

p

px

pj

t

Figure 6: The shortest s-to-t path P (in red), some pieces of the r-division (in black), the shortest
cycle Ci (in blue), and the globally shortest cycle C (in green). Apart from the p` -to-pj separation
finger, Ci has four fingers below P and three above. Observe that C does not cross Ci except inside
the shaded piece where C enters and exits a px -to-py finger of Ci above P . Such crossings are
allowed.
because C is a simple cycle, it cannot exit C 0 at P [pk , pj ] because C crosses P only once (at
pk ), so if C[a, pk ] exits C 0 it must do so at some vertex b of Ci [a, pj ]. Since Ci [a, pj ] does
not cross P at all, we can replace C[a, b] with Ci [a, b] to get a globally minimum cycle that
does not cross Ci at a. The same argument shows that C[a, pk ] cannot pass through pj .
Before moving on, observe that we have just proven a stronger claim since we did not use
the fact that a is the first crossing vertex nor the fact that pk is strictly external to Ci (i.e.,
the claim holds even if pk is on Ci ). Namely, we proved that (∗) If k < j and k ≤ ` then C
does not cross the separation finger.
1.3 If k ≥ `, then it must be that pk is enclosed by some px -to-py finger S 0 that is above P
(i.e., S and S 0 cross as in case I in Claim 1). Observe that S 0 encloses only vertices of some
single piece R. Since C[pk , ·] first intersects S it must be that S enters the finger S 0 (at some
vertex c) and exits the finger S 0 (at some vertex d) such that a ∈ S[c, d] (notice that it is
possible that a = c = d). Furthermore, C[pk , ·] first crosses S[c, d] at a and must eventually
exit the finger S 0 (at some vertex b ∈ Ci [px , py ]). We first claim that b 6∈ Ci [px , d]. This
is because that would imply that for some u ∈ S[a, d] the subpaths C[a, u] and Ci [a, u]
are two a-to-u shortest paths that do not cross P . We can therefore replace C[a, u] with
Ci [a, u]. Finally, we claim that b 6∈ Ci [d, py ]. This is because if b ∈ Ci [d, py ] then in Ci we
could replace Ci [a, d] ◦ Ci [d, d] ◦ Ci [d, b] with C[a, a] ◦ C[a, b]: (1) We are allowed to do such
replacing because C[pk , b] is enclosed by S 0 and so is completely contained in R, and (2)
This can only make Ci shorter because Ci [d, d] is not longer than C[a, a] (since C[a, a] is the
globally minimum cycle) and because Ci [a, d] ◦ Ci [d, b] is not longer than C[a, b] (since they
are both contained in R and do not cross P , and since C[a, b] is a globally shortest a-to-b
path).
2. S is a px -to-py finger of Ci below P . Since pk is external to Ci and since C[pk , ·] crosses Ci first in
a finger below P we can conclude that k < `. Let C 0 be the cycle C[pk , a]◦Ci [a, py ]◦rev(P [pk , py ]).
At vertex a, C enters C 0 and must exit C 0 before reaching pk . C cannot exit at C[pk , a] because
15

C is simple, and it cannot exit at P [pk , py ] because C crosses P only once, so C must exit C 0 at
some vertex b of Ci [a, py ]. However, since Ci [a, py ] does not cross P at all, we can replace C[a, b]
with Ci [a, b].

s

p

pk pi

pj

t
v

a
u

Figure 7: A finger of C[pi , p` ] below P that crosses the separation finger.
3. S is a px -to-py finger of Ci above P .
3.1 If k < `, then after crossing at a the cycle C enters the finger S (otherwise C crosses P
more than once). In order for this to happen, the finger S must cross the separation finger
(as in case I in Claim 1 and as illustrated in Figure 6). To see why, consider the cycle
C 0 = Ci [p` , pj ] ◦ rev(P [p` , pj ]) (C 0 = Ci [p` , pj ] ◦ P [pj , p` ]) if ` ≤ j (if j < `). Since pk is
strictly external to C 0 , C cannot enter C 0 before crossing the finger S. Hence the finger S
must cross the separation finger. This means that i < y < x ≤ j because if ` < y < x < i
and S crosses the separation finger at node u then we can throw Ci [u, u] from Ci and obtain
a shorter cycle Ci that passes through pi and separates s and t. Since i < y < x ≤ j
then, by Observation 2, the finger S is entirely contained in a single piece R and encloses
no holes. Recall that b1 and b2 are the boundary vertices preceding and following a on C,
and by definition belong to different sides of Ci . Thus b1 , b2 are boundary vertices of R.
We claim that the DDG edge b1 b2 belong to the same side of Ci , which is a contradiction.
This is because for b1 and b2 to belong to different sides of Ci , C[b1 , b2 ] must either cross P
from left to right (but C cannot do this by definition) or cross the separation finger (but C
cannot do this by (∗)).
3.2 If k ≥ ` then pk is enclosed by some finger S 0 of Ci above P . Note that S 0 can be either
the px -to-py finger S (and then y < k < x), or some other pw -to-pz finger (i.e., S and S 0
cross as in case III of Claim 1 as illustrated in Figure 8). Since pk is enclosed by the S 0
finger, C[pk , ·] must exit S 0 at some vertex a0 (note that if S 0 = S then a0 = a). Then, before
reaching a0 again, C[a0 , ·] must cross the separation finger (at some vertex b).
If Ci [a0 , b] does not include pi , then since C[a0 , b] does not cross P we should replace in Ci the
subpath Ci [a0 , b] with C[a0 , b]. If Ci [a0 , b] does include pi , then C[pk , a0 ] is entirely contained
in a single piece R and so in Ci we should replace the subpath Ci [b, a0 ] with C[b, a0 ].
Next we consider the case where pk is internal to Ci or lies on Ci . Again, the finger S is one of three
types:
4. S is the separation finger. In this case, if k ≤ ` then since pk is internal to Ci it means that
j < `, Ci [pj , pi ] = P [pj , pi ], and pk lies on Ci . Furthermore, Ci [p` , pk ] (and hence also Ci [a, pk ])
does not cross P at all. This means that in C we can replace C[a, pk ] with Ci [a, pk ] to get a
16

pi

s

p

pz

pk pw

py

px

pj

t

Figure 8: Crossing px -to-py and pw -to-pz fingers of Ci (in blue) above P . Notice that C (in green,
shown partially) first crosses the px -to-py finger even though z < k < w. We prove that such
crossings cannot occur.
globally minimum cycle that does not cross Ci at a. If on the other hand k ≥ `, then C exits Ci
in a and C(a, pk ] must intersect Ci (because pk is either in or on Ci ). Let b be the last vertex
where C(a, pk ] intersects Ci . If b ∈ Ci [a, pi ) then in Ci we could replace Ci [a, b] with C[a, b] since
C[a, b] does not cross P . If on the other hand b ∈ Ci [pi , a) then Ci [a, b] (as opposed to C[a, b]) is
required to pass through pi . In this case we therefore consider Ci [b, a] and C[b, a]: even though
C[b, a] crosses P (at pk ) the subpath C[b, pk ] is entirely contained in a single piece R (because
it is enclosed by a finger of Ci [pi , p` ] below P , which by Observation 1 is contained in a single
piece). Therefore, in Ci we could replace Ci [b, a] with C[b, a].
5. S is a px -to-py finger of Ci below P .
5.1 If k = ` then if a is on Ci [pj , pi ] then we can replace C[pk , a] with Ci [pk , a]. If a is on
Ci [pi , p` ] then we can replace C[a, pk ] with Ci [a, pk ]. We conclude that k 6= `.
5.2 If j < i then Ci [pj , pi ] = P [pj , pi ] so Observation 1 applies to S.
i. If k ≤ y or k ≥ x, then after entering the finger S at a and before reaching pk again,
C[pk , ·] must exit S at some vertex b. However then, by Observation 1, there is a DDG
edge whose corresponding path contains C[a, b] as a subpath and has both endpoints
on the same side of Ci .
ii. If y < k < x and j ≤ k, then k is at the base of the finger S. Since j < i we have
that the bases of all fingers are in P [p` , pi ]. This implies that k ≤ i. Let b be the last
vertex of C strictly before pk that belongs to S (see Figure 9 which falls under case II of
Claim 1). (i) pk is a vertex of Ci , (ii) C[b, pk ] is enclosed by S, (iii) C[b, pk ] is contained
in a single piece R, (iv) C[pk , b] does not cross P . This implies that Ci is a non-simple
cycle in which we could replace Ci [b, pk ] with the non-simple cycle C ◦ C[b, pk ]. To see
that this can only make Ci shorter define u to be the last vertex of Ci [p` , pj ) that
belongs to S if j > y and py otherwise. Observe that Ci [b, pk ] can be decomposed as
Ci [b, u] ◦ Ci [u, p` ] ◦ Ci [p` , u] ◦ Ci [u, pk ]. The cycle Ci [u, p` ] ◦ Ci [p` , u] is not longer than C
(since C is globally minimum), and Ci [b, u] ◦ Ci [u, pk ] is not longer than C[b, pk ] (since
they are both contained in R, and since C[b, pk ] is a globally shortest b-to-pk path).
iii. If y < k < x and k < j, then again, define u to be the last vertex of Ci [p` , pj ) that
belongs to S. C enters at a the simple cycle C[pk , a] ◦ Ci [a, u] ◦ Ci [u, pj ] ◦ rev(P [pk , pj ])
(where Ci [u, pj ] is the simple path in Ci between u and pj ). It must exit this cycle in
17

s

p

py pj pk

px
u

pi

t

b

Figure 9: C (in green) crosses the px -to-py finger of Ci (in blue) at b. Such crossings cannot occur
because the (non-simple) subpath Ci [b, pk ] can be made shorter by replacing it with C ◦ C[b, pk ].
order to get to pk from below. It cannot cross at P by definition of pk . It cannot leave
the cycle through C because of simplicity. It cannot leave the cycle through Ci [a, u]
because Ci [a, u] and C[a, u] are two different shortest paths. If it leaves the cycle at a
vertex v of Ci [u, pj ] then, similarly to case 5(2)ii, we can make Ci shorter by replacing
Ci [a, v] with C ◦ C[a, v].
5.3 If j ≥ i then k > `. This means that S is a finger of Ci [pi , p` ] below P that crosses the
separation finger (see Figure 7 which falls under case II of Claim 1). In other words, a is
enclosed by the cycle Ci [p` , pj ] ◦ rev(P [p` , pj ]) since otherwise C[pk , ·] must first exit this
cycle which would mean that S is the separation finger (and not a finger below).
i. If k < y then C[pk , ·] enters the cycle C[pk , a] ◦ Ci [a, py ] at vertex a and must exit this
cycle before reaching pk again. It cannot exit at C[pk , a] because C is simple and it
cannot exit Ci [a, py ] at any vertex b because that would imply that Ci [a, b] and C[a, b]
are two a-to-b shortest paths.
ii. If x < k < j then pk is on the base of some bottom finger S 0 6= S. To reach pk again,
C[pk , ·] must cross the separation finger and then cross S 0 . We have already proved in
case 4 that this is impossible.
iii. If y ≤ k ≤ x then let u and v be the vertices that belong to both S and the separation
finger and are the endpoints of their intersecting subpaths (see Figure 8). At vertex
a, C[pk , ·] enters the cycle C[pk , a] ◦ Ci [a, py ] and we have already seen in case 5(3)i
that C[a, pk ] must remain inside this cycle. This implies that C[a, ·] must cross Ci [u, pj ]
before reaching pk . Let b denote the last such crossing vertex. In Ci , we can therefore
replace Ci [a, u] ◦ Ci [u, u] ◦ Ci [u, b] with C[a, a] ◦ C[a, b] to obtain a shorter cycle. This is
because C is the globally shortest cycle and so C[a, a] is shorter than Ci [u, u] and C[a, b]
is shorter than Ci [a, u] ◦ Ci [u, b].
iv. If k ≥ j then C[pk , ·] cannot cross the separation finger: If it crosses at vertex b then
it exists the cycle C[pk , b] ◦ Ci [b, pj ] and it must enter this cycle again before reaching
pk . However, it cannot enter at C[pk , b] because C is simple and it cannot enter at a
vertex c of Ci [b, pj ] because then C[b, c] and Ci [b, c] are two b-to-c shortest paths. This
means that C(a, ·] can only cross S (an odd number of times). However, since S is a
simple finger it is contained in a single piece R (by Observation 1). Such crossings are
available in the DDG even after cutting along Ci .
6. S is a px -to-py finger of Ci above P .
18

6.1 If k = ` < j then, if the first edge of C that leaves Ci after pk is enclosed by the separation
finger, then C first crosses the separation finger, so we are in case 1.2. If the first edge of C
that leaves Ci after pk is not enclosed by the separation finger, then S must also cross the
separation finger, so we are in case 3.1.
6.2 If k < j, then C[pk , ·] must exit the cycle Ci [p` , pj ] ◦ rev(P [p` , pj ]) (at some vertex a0 on the
separation finger Ci [p` , pj ]) and then (since pk is enclosed by Ci ) intersect Ci again (in this
case pk is on the base of a bottom finger, so the last vertex b of Ci intersected by C before
reaching pk belongs to this bottom finger). As in case 4 above, if b ∈ Ci [a0 , pi ) we could
replace Ci [a0 , b] with C[a0 , b] and if b ∈ Ci [pi , a0 ) we could replace Ci [b, a0 ] with C[b, a0 ].
6.3 If i ≤ j ≤ k, then the finger S must be such that x ≤ k. If S is a finger of Ci [pj , pi ] (i.e.,
i < y < x ≤ j), then C[pk , ·] enters the finger at a and must exit the finger (at some vertex
b ∈ Ci [px , py ]) before reaching pk . Observation 2, the finger S is entirely contained in a
single piece R and encloses no holes. Therefore, the boundary vertices b1 and b2 preceding
and following a on C belong to the same side of Ci , contradicting their definition. If on the
other hand S is a finger of Ci [pi , p` ] (i.e., ` < y < x < i), then first edge of C[a, ·] is enclosed
by the cycle C[pk , a] ◦ Ci [a, py ] ◦ P [py , pk ]. Thus C[a, pk ] must exit this cycle before reaching
pk . It can only exit at some vertex b ∈ Ci [a, py ]. However, this implies that Ci [a, b] and
C[a, b] are two shortest a-to-b paths that do not cross P .
6.4 If j ≤ i ≤ k, then as in case 6.3, this means that C[pk , ·] at vertex a enters the cycle
C[pk , a] ◦ Ci [a, py ] ◦ P [py , pk ] and must exit this cycle at some vertex b ∈ Ci [a, py ]. Implying
that Ci [a, b] and C[a, b] are two shortest a-to-b paths that do not cross P .
6.5 If j ≤ k ≤ i, then pk lies on Ci [pj , pi ] = P [pj , pi ], and S is a finger of Ci [pi , p` ]. This means
that in Ci we could replace Ci [a, pk ] with C[a, pk ] because Ci [a, pk ] does not visit i, and
C[a, pk ] does not cross P .
Since pk might not be a boundary vertex of the r-division, we must also argue that pk is assigned
to the subgraph of the DDG in which we have shown C exists (i.e., either DDG s or DDG t ). Let
pf irst and plast denote the first and last vertices of P that are also vertices of Ci . We have already
seen that, in the cases where C crosses Ci , pk either appears before pf irst or after plast on P . If, on
the other hand C does not cross Ci at all then, since C crosses P once, pk cannot be inside a finger.
Therefore, either pk appears on P before pf irst (and hence also before pi ), or pk appears on P after
plast (and hence also after pi ).

4.5

Additional details about the use of the Z2 -homology cover

When information about a DDG edge uv of Q is required during the execution of the algorithm,
we want it to correspond to a shortest u-to-v path in R that satisfies Property 1. The appropriate
shortest path is represented in the MSSP data structure for the Z2 -homology cover of R with H
being the subset of holes of R that are not holes of Q. This subset H can be associated with Q at
the time the implicit incision along P is made. We need to be able to infer the appropriate label
of the vertex v. Among the (DDG) edges of P that form the boundary of Q there is a constant
number of edges that split the holes in H (this is because each such edge defines a distinct subpiece
of R \ Q that contains at least one hole). When R is implicitly cut along P , we mark the endpoints
of such edges and store them using a data structure that supports fast predecessor search ((i) given
a boundary vertex of P find its marked predecessor on P , and (ii) given a boundary vertex of Q
find its marked predecessor on the external boundary of Q). For each pair of marked vertices x, y
we store the crossing parity of an x-to-y path in Q with every A` . These crossing parities can
19

P
u

u00

00

h1
h1

v

h2
h2

A1

01

v01
A2
A1

A1

h2
A2

10
A2

h1
A2

h2

A1

h2

A1

A2

Q

11

h1
h1

w
Figure 10: On the left, a piece R (in black) with two holes h` (` = 1, 2, green and blue), each with
a dual path A` from the external hole to h` . The path P (in red) separates R into subpieces, one of
which (shaded) is Q. On the right, the Z2 -homology cover of R with H = {h1 , h2 }. A valid (i.e., one
whose fingers do not enclose any holes of H) shortest u-to-v path ρ in R must have an even (odd)
crossing parity with A1 (A2 ) and therefore corresponds to a u00 -to-v 01 path in the Z2 -homology
cover. One such valid u-to-v path ρ is illustrated as the dashed (purple) line. Similarly, a valid
u-to-w path must have an odd (even) crossing parity with A1 (A2 ) and therefore corresponds to a
u00 -to-w10 path in the Z2 -homology cover.
be computed using the information stored in the MSSP data structure for the (DDG) edges of P .
Whenever the appropriate label for v for a DDG edge uv is required, it is obtained by querying the
label stored for the pair of predecessors of u and v.

5

The Division-Edge technique

A technique of Łącki and Sankowski that we use without change in our algorithm is the use of
a recursion graph and division edges to efficiently keep track of the partition of the graph into
subgraphs along the execution of the algorithm. Since most of the algorithm is run on the DDG
rather than on the underlying planar graph G, it is necessary to be able to quickly determine
how to partition the boundary vertices when separating a graph into the subgraphs enclosed and
not enclosed by some cycle of edges in the DDG. Note that this is particularly challenging since,
in general, boundary vertices of a piece belong to multiple holes. The recursion graph stores the
information required to perform this task.
For each piece R of the r-division with external hole h and a constant number of internal holes
{hi }, we fix an arbitrary set of mutually noncrossing h-to-hi paths Khi . We store for every edge e
of the DDG of R the crossing parity number of the path corresponding to e and each Khi . This
information can be computed and stored within the same bounds required to compute and store
the DDG.
20

The recursion graph is a planar embedded graph whose vertices are the boundary vertices of
the r-division of the input planar graph. Initially, the only edges in the recursion graph are edges
between consecutive boundary vertices of the r-division that lie on the same hole of their piece.
The embedding of this initial graph is inherited from the embedding of the input planar graph.
Edges between consecutive vertices that do not exist in the original graph are embedded along the
corresponding subpath of the hole. Edges are added to the recursion graph when the algorithm
separates the graph into internal and external parts with respect to some cycle C of edges in the
DDG. For each DDG edge e of C, we add an edge e0 to the recursion graph. The edge e0 has the
same endpoints as e, and is embedded in the recursion graph so that the crossing parity of each
Khi and the curve on the plain that corresponds to e0 matches the parity stored for the DDG edge
e. This guarantees that the partition of boundary vertices into the internal and external subgraphs
with respect to the DDG cycle C is the same as the partition of the vertices with respect to the
corresponding cycle in the recursion graph. Since the number of vertices and edges of the recursion
graph is linear in the number of boundary vertices, computing the partition of a subgraph G0 takes
linear time in the number of boundary vertices in G0 .

6

Graphs Embedded on a Surface

In this section we briefly describe a generalization of our algorithm for finding the shortest cycle in a
graph embedded on a surface with a bounded genus g. We present two algorithms for the problem,
one runs in O(g 2 n log n) time with high probability, and the other runs in O(gn log2 n) in the worst
case. Notice that the duality between cuts and cycles does not hold for g > 0, so these algorithms
do not find the minimum cut in such graphs.
The first algorithm uses a greedy system of loops [9] based at an arbitrary vertex o. This is a set
L of 2g undirected cycles in G, each of them containing the basepoint o, such that every undirected
cycle S in L consists of an edge uv, a shortest o-to-v path and, a shortest o-to-u path. This is
similar to a shortest path separator. If we make incisions in G along the paths that define the cycles
of L, we remain with a planar graph GL .
We begin by finding a greedy system of loops L in O(n) time using the algorithm of Erickson
and Whittlesey [9]. The shortest cycle in G is either a cycle in GL , or crosses one of the undirected
cycles of L. We find the shortest cycle in GL in O(n log log n) time using the algorithm for planar
√
graphs (to get this time bound we assume that g = o( n), since otherwise the second algorithm
which we present next is faster). We find the shortest cycle if it crosses a member of L using an
MSSP algorithm, similarly to the implementation of Reif’s algorithm [23] which we described in
Section 2. We use here the fact that a cycle of L is composed of two shortest paths and that
Lemma 1 does not depend on the planarity of the input graph. We apply O(g) times the MSSP
algorithm of Cabello et al. [2]. This takes O(g 2 n log n) time with high probability. The shortest
cycle in the graph is the shortest among the O(g) cycles that we find for each member of L and the
shortest cycle in GL .
Our second algorithm for embedded graphs uses a planarizing set, which is a set of edges or
vertices whose removal from the graphs leaves a planar graph. We begin by finding a planarizing
√
set R of O( gn) edges in time linear in the number of the edges of the graph [6]. We remove the edges
of R and get a planar graph GR . We find the shortest cycle in GR using our algorithm for planar
graphs. For each edge uv of R we find the shortest cycle containing uv by computing the shortest
√
v-to-u path. This takes O( gn log2 n) time per edge of R after O(n log2 n) time preprocessing using
a variant of FR-Dijkstra [10], as noted by Smith. This gives a total running time of O(gn log2 n)
(we assume here that g = o(n), otherwise it is simple to get this time bound). The shortest cycle

21

in G is the shortest among the shortest cycle containing edges of R and the shortest cycle in GR .

22

References
[1] G. Borradaile and P. Klein. An O(n log n) algorithm for maximum st-flow in a directed planar
graph. J. ACM, 56(2):9, 2009.
[2] S. Cabello, E. W. Chambers, and J. Erickson. Multiple-source shortest paths in embedded
graphs. SIAM J. Comput., 42(4):1542–1571, 2013.
[3] P. Chalermsook, J. Fakcharoenphol, and D. Nanongkai. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In SODA, pages 828–829, 2004.
[4] H.C. Chang and H.I Lu. Computing the girth of a planar graph in linear time. SIAM J.
Comput., 42(3):1077–1094, 2013.
[5] H. N. Djidjev. A faster algorithm for computing the girth of planar and bounded genus graphs.
ACM Trans. Algorithms, 7(1):3, 2010.
[6] H. N. Djidjev and S. M. Venkatesan. Planarization of graphs embedded on surfaces. In WG,
pages 62–72, 1995.
[7] D. Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl., 3(3):1–27, 1999.
[8] J. Erickson and A. Nayyeri. Minimum cuts and shortest non-separating cycles via homology
covers. In SODA, pages 1166–1176, 2011.
[9] J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. In SODA,
pages 1038–1046, 2005.
[10] J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and near
linear time. J. Comput. Syst. Sci., 72(5):868–889, 2006.
[11] K. Fox and J. Erickson. private communication. 2016.
[12] G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications.
SIAM J. Comput., 16(6):1004–1022, 1987.
[13] M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms for
planar graphs. J. Comput. Syst. Sci., 55(1):3–23, 1997.
[14] G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Improved algorithms for min
cut and max flow in undirected planar graphs. In STOC, pages 313–322, 2011.
[15] L. Janiga and V. Koubek. Minimum cut in directed planar networks. Kybernetika, 28(1):37–49,
1992.
[16] H. Kaplan and Y. Nussbaum. Minimum s-t cut in undirected planar graphs when the source
and the sink are close. In STACS, pages 117–128, 2011.
[17] P. N. Klein. Multiple-source shortest paths in planar graphs. In SODA, pages 146–155, 2005.
[18] P. N. Klein, S. Mozes, and C. Sommer. Structured recursive separator decompositions for
planar graphs in linear time. In STOC, pages 505–514, 2013.

23

[19] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math,
36(2):177–189, 1979.
[20] J. Łącki and P. Sankowski. Min-cuts and shortest cycles in planar graphs in O(n log log n)
time. In ESA, pages 155–166, 2011.
[21] R. Motwani and P. Raghavan. Randomized algorithms. Press Syndicate of the University of
Cambridge, 1995.
[22] K. Mulmuley, U. Vazirani, and V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105–113, 1987.
[23] J. H. Reif. Minimum s-t cut of a planar undirected network in O(n log2 n) time. SIAM J.
Comput., 12(1):71–81, 1983.
[24] K. Weihe. Maximum (s,t)-flows in planar networks in O(|V | log |V |)-time. J. of Comp and Sys.
Scie., 55(3):454–476, 1997.
[25] O. Weimann and R. Yuster. Computing the girth of a planar graph in O(n log n) time. SIAM
J. Discrete Math, 24(2):609–616, 2010.
[26] C. Wulff-Nilsen. Girth of a planar digraph with real edge weights in O(n log3 n) time.
arXiv:0908.0697, 2010.

24

