Finding All Useless Arcs in Directed Planar Graphs
Jittat Fakcharoenphol∗

Bundit Laekhanukit†

Pattara Sukprasert‡

arXiv:1702.04786v3 [cs.DS] 2 Mar 2017

March 3, 2017

Abstract
Maximum flow is a fundamental problem in Combinatorial Optimization that has numerous
applications in both theory and practice. In this paper, we study the flow network simplification
problem, which asks to remove all the useless arcs from the graph. To be precise, an arc is useless
if it does not participate in any simple s, t-path. Weihe [FOCS’94, JCSS’97] showed that if there
exists an O(n log n)-time algorithm for simplifying a flow network, then a maximum s, t-flow
in directed planar graphs can be computed in O(n log n)-time. However, there was no known
algorithm that could determine all the useless arcs in O(n log n)-time. Although an O(n log n)time algorithm for computing maximum flow on planar directed graphs without simplifying
a flow network has been later discovered by Borradaile and Klein [SODA’06, J.ACM’09], it
remains open whether a directed planar flow network can be simplified in O(n log n)-time.
Here we present an algorithm that determines all the useless arcs in O(n log n)-time, thus
completing the framework of Weihe. Our algorithm improves upon the previous best running
time of Õ(n2 ) for removing all the useless arcs by Misiolek and Chen [COCOON’05, IPL’06]
and by Biedl, Brejová and Vinar [MFCS’00]. Our main algorithm requires the planar embedding to contain no clockwise cycle, and every vertex except source and sink has degree three.
The bottleneck of our algorithm is the O(n log n) time algorithm for preprocessing the planar
embedding while all the other parts runs in linear time.

1

Introduction

The maximum s, t-flow problem is a fundamental problem in Combinatorial Optimization that
has numerous applications in both theory and practice. A basic instance of maximum flow where
the underlying graph is planar has been considered as an important special case and has been
studied since 50’s in the early work of Ford and Fulkerson [FF56]. Since then, there have been
steady developments of maximum flow algorithms on undirected planar graphs. Itai and Shiloach
[IS79] proposed an algorithm for the maximum s, t-flow problem on undirected planar graphs that
runs in O(n2 log n) time, and in subsequent works [Has81, Rei83, HJ85, Fre87, KRHS94, HKRS97,
INSW11], the running time have been improved to the current best O(n log log n)-time algorithm
by Italiano et al. [INSW11].
Another line of research is the study of the maximum s, t-flow problem in directed planar graphs.
The fastest algorithm with the running time of O(n log n) is due to Borradaile and Klein [BK09].
∗

Kasetsart University, Thailand
Weizmann Institute of Science, Israel. Partially supported by the ISF grant 621/12 and I-CORE grant No. 4/11.
‡
Kasetsart University, Thailand and The Optimum Solutions, Singapore
†

1

Historically, in 1994, Weihe [Wei97] presented a novel approach that would solve the maximum s, tflow problem on directed planar graphs in O(n log n) time. However, Weihe’s algorithm requires a
preprocessing step that transforms an input graph into a particular form: (1) each vertex (except
source and sink) has degree three, (2) the planar embedding has no clockwise cycle, and (3) every
arc must participate in some simple s, t-path.
The first condition can be guaranteed by a simple (and thus linear-time) reduction, and the
second condition can be obtained by an algorithm of Khuller, Naor and Klein in [KNK93] which
runs in O(n log n)-time. Unfortunately, for the third condition, there was no known algorithm
that could remove all such “useless” arcs in O(n log n)-time. As this problem seems to be simple,
this issue had not been noticed until it was pointed out much later by Biedl, Brejová and Vinar
[BBV00]. Although an O(n log n)-time algorithm for the maximum s, t-flow problem in directed
planar graphs has been devised by Borradaile and Klein [BK09], the question of removing all the
useless arcs in O(n log n)-time remains unsolved.
In this paper, we study the flow network simplification problem, where we are given a directed
planar graph G = (V, E) on n vertices, a source vertex s and a sink vertex t, and the goal is to
remove all the arcs e that are not contained in any simple s, t-path. One may observe that the
problem of determining the usefulness of a single arc involves finding two arc-disjoint paths, which
is NP-complete in general directed graphs [FHW80]. Thus, detecting all the useless arcs at once
is non-trivial. Here we present an O(n log n)-time algorithm that determines all the useless arcs,
thus solving the problem left open in the work of Weihe [Wei97] and settling the complexity of
simplifying a flow network in directed planar graphs.
The main ingredient of our algorithm is a decomposition algorithm that slices the plane graph
into small strips with simple structures. This allows us to design an appropriate data structure to
handle each strip separately. Our data structure is simple but requires a rigorous analysis of the
properties of a planar embedding. We use information provided by the data structure to determine
whether each arc e is contained in a simple s, t-path P in O(1) time, thus yielding a linear-time
algorithm. The main difficulty is that we cannot afford to explicitly compute such s, t-path P (if
one exists) as it would lead to O(n2 ) running time. The existence of any path P can only be
determined implicitly by our structural lemmas.
Our main algorithm runs in linear time. However, it requires the planar embedding (which is
assumed to be given together with the input graph) to contain no clockwise cycle. This can be
assumed wlog because ones may apply the algorithm of Khuller, Naor and Klein [KNK93] to modify
the planar embedding, which costs an extra O(n log n) time in the complexity of the algorithm.
Moreover, we assume that every vertex that is not source and sink has degree three, which can be
done by a standard reduction in linear-time. The above two reductions may affect the usefulness
of arcs in the graph, but this is sufficient for the application of the flow-network simplification
algorithm in computing maximum s, t-flow. By standard reductions, we may further assume that
the source s has outdegree one (otherwise, we replace s by an arc ss0 ), and the sink t is in the
boundary face of the plane graph.
As a final remark, our algorithm runs in linear-time given that the graph has been preprocessed
by the algorithms in [KNK93], which runs in O(n log n). This is the bottle-neck of our algorithm.

1.1

Related Work

Planar duality plays crucial roles in planar flow algorithm developments. Many maximum flow algorithms in planar graphs exploit a shortest path algorithm as a subroutine. However, the O(n log n)2

time algorithm for the maximum s, t-flow problem in directed planar graphs by Borradaile and Klein
[BK09], which is essentially a left-most augmenting-path algorithm, is not based on shortest path
algorithms. Erickson [Eri10] reformulated the maximum flow problem as a parametric shortest path
problem and devised a similar O(n log n) algorithm. Borradaile and Harutyunyan [BH13] explored
this path-flow duality further and showed a correspondence between maximum flows and shortest
paths in directed planar graphs with no restriction on the locations of the source and the sink.
For directed planar graphs with unit capacities, Eisenstat and Klein [EK13] presented a linear
time algorithm for finding the max s, t-flow.
A seminal work of Miller and Naor [MN95] studied flow problems in planar graphs with multiple
sources and multiple sinks. The problem is special in planar graphs as one cannot use standard
reduction to the single-source single-sink problem without destroying the planarity. Using a wide
range of planar graph techniques, Borradaile, Klein, Mozes, Nussbaum, Wulff-Nilsen [BKM+ 11]
presented an O(n log3 n) algorithm for this problem.

2

Preliminaries

We use the standard terminologies in graph theory. By degree of a vertex in a directed graph, we
mean the sum of indegree and outdegree. Let G be an input planar directed graph with n vertices
and m = O(n) arcs. We assume that a planar embedding of G is given as input. Let s and t be
source and sink vertices, respectively. A strongly connected component of G is a maximal subgraph
of G that is strongly connected. For any strongly connected component C such that s, t 6∈ V (C),
a vertex v ∈ V (C) is an entrance of C if there exists an s, v-path P ⊆ G such that P contains no
vertices of C except v, i.e., V (P ) ∩ V (C) = {v}. Similarly, a vertex v ∈ V (C) is an exit of C if there
exists an v, t-path P ⊆ G such that P contains no vertices of C except v, i.e., V (P ) ∩ V (C) = {v}.
A path P ⊆ G is a simple path if each vertex appears in P at most once. We say that an arc uv
is a useful arc (w.r.t. s and t) if there is a “simple” s, t-path P containing uv. Thus, the s, u and
v, t subpaths of P have no common vertices. Otherwise, if there is no simple s, t-path containing
uv, then we say that uv is a useless arc (w.r.t. s and t). Similarly, a path P is useful (w.r.t. s and
t) if there is a simple s, t-path Q that contains P . Note that if a path P is useful, then all the arcs
of P are useful. However, the converse is not true, i.e., all the arcs of P are useful does not imply
that P is a useful path.
Throughout this paper, we assume two properties of the input graph G:
1. There is no clockwise cycle in the planar embedding.
2. Every vertex except s and t has degree three.
3. The source s is adjacent to only one outgoing arc.
4. The sink t is on the boundary face.

2.1

Planar Embedding and Basic Subroutines

We assume that the planar embedding is given in the form of an adjacency list sorted in counterclockwise order. To be precise, our input is a table T of adjacency list of arcs incident to each
vertex v ∈ V (G) (i.e., V (G) is the index of T ) sorted in counterclockwise order. Each adjacency
list T (v) is a doubly linked-list of arcs having v as either heads or tails. (i.e., arcs of the forms
3

uv or vw). We can construct from the table T , two tables of adjacency list, say T in and T out ,
whose entry T in (v) (respectively, T out (v)) for v ∈ V (G) is a pointer to a doubly linked-list of arcs
entering (respectively, leaving) v. Thus, given an arc vw, we can query in O(1) time an arc vw0 next
to vw in the counterclockwise (or clockwise) order. Moreover, by preprocessing, we can query in
O(1) time the right-most arc (resp., left-most arc) of uv, which is an arc vw in the reverse direction
that is nearest to uv in the counterclockwise (resp., clockwise) order. It is easy to see that this
preprocessing can be implemented to run in linear time.
Belows are the list of basic subroutines used in our paper.
• Next(vw). Given an arc vw ∈ E(G), return an arc vw0 (an arc adjacent to v) next to vw in
the counterclockwise order.
• Prev(vw). Given an arc vw ∈ E(G), return an arc vw0 (an arc adjacent to v) before vw in
the counterclockwise order.
• Right(uv). Given an arc uv ∈ E(G), return an arc vw (an arc adjacent to v) which is an
arc in the reverse direction nearest to uv in the counterclockwise order.
• Left(uv). Given an arc uv ∈ E(G), return an arc vw (an arc adjacent to v) which is an arc
in the reverse direction nearest to uv in the clockwise order.
Left and Right Direction. Since we are given a planar embedding, we may compare two
paths/arcs using the notion of left to and right to. Given a path P , we say that an arc e = vw
(resp., e = wv) is right to P if v ∈ P and there exist arcs av, vb in P such that vw appears after
av and before vb in counterclockwise order. The notion left to can be defined analogously. Given
two paths P and Q that have an intersection, we say that P is right to Q if any arc of P entering
or leaving Q is right to Q. (Note that if P and Q have no intersection, then we cannot say which
path is on the left or on the right.)
The subroutines mentioned previously allow us to query in O(1) time the right-most arc vw of
a given arc uv, which is the arc in the reverse direction nearest to uv in the counterclockwise order.
Consequently, we may define the right-first-search algorithm as a variant of the depth-first-search
algorithm that chooses to traverse to the right-most (unvisited) arc in each step of the traversal.
Since we assume that the source s has a single arc e leaving it, the right-first-search (resp.,
left-first-search) started from s is unique and thus well-defined (because every path must start from
the arc e).

3

Overview and Structural Lemmas

In this section, we give an overview of the algorithm. We start by decomposing G into a set of
strongly connected components. Observe that any arc uv that connects two strongly connected
components is useful if and only if u is reachable from s and t is reachable from v. We are left to work
on arcs inside strongly connected components. We work on each strongly connected component
independently.
We state the following useful facts.
Lemma 1. Let e0 be any useless arc in G. Then any useful arc e ∈ E(G) is also useful in G − {e0 }.

4

Proof. By the definition of useful arc e, there exists a simple s, t-path P in G containing e, and such
path P cannot contain e0 ; otherwise, it would certify that e0 is useful. Therefore, P ⊆ G − {e0 },
implying that e is useful in G − {e0 }.
Lemma 2. An arc e is useful if and only if it is contained in some useful path.
Proof. The lemma follows from the definition of useful arcs, i.e., if an arc e is contained in a useful
path P , then we know that there must exist a simple s, t-path Q that contains P (and thus e),
meaning that e is useful. If e is useful, then we know that it must be contained in a simple s, t-path
Q, and every subpath of P is useful by definition.
Lemma 3. Let C be a strongly connected component, and let B be a set of boundary arcs of C,
then B forms a counter clockwise cycle.
Proof. Since we assume that the embedding has no clockwise cycle, it suffices to show that B is
a cycle. We prove by a contradiction. Assume that B is not a cycle. Then we would have two
consecutive arcs in B that go in opposite directions. (Note that the underlying undirected graph
of B is always a cycle.) That is, there must exist a vertex u with two leaving arcs, say uv and
uw. Since u, v, w are in the same strongly connected component, the component C must have a
v, u-path P and and a w, u-path P 0 . We may assume minimality of P and P 0 and thus assume that
they are simple paths. Now P ∪ {uv} and P 0 ∪ {uw} forms a cycle, and only one of them can be
counterclockwise (since uv and uw are in opposite direction), a contradiction.
Lemma 4. Let u and v be an entrance and an exit of C, and let Pu and Pv be an s, u-path Pu
and a v, t-path Pv that contains no vertices of C except u and v, respectively. Then Pu and Pv are
vertex disjoint.
Proof. Suppose Pu and Pv are not vertex-disjoint. Then the intersection of Pu and Pv induces a
strongly connected component strictly containing C. This is a contradiction since C is a maximal
strongly connected subgraph of G.
Observe that C forms a region on a surface. Our algorithm deals with two cases. The first case
is the outside case where the source s lies outside the boundary of C in the planar embedding.
Since t is assumed to be in the boundary face of the planar embedding, both s and t lie outside
the boundary of C. The second is the inside case where the s lies inside the boundary of C. See
Figure 1 for the example of outside and inside cases. It is possible to have many inside cases (see
Figure 2).

4

Strip Decomposition

The crucial part of our algorithm is the decomposition algorithm that decompose the component
C into strips, which is a region of C in the planar embedding encloses by two arc-disjoint paths U
and F that share start and end vertices.
We will present a strip-decomposition algorithm that decomposes a given strip CU,F into a
collection S of minimal strips in the sense that any strip in S has no proper subgraph that is a
strip. Moreover, any two strips obtained by the decomposition are either disjoint or share only
their boundary vertices. We claim that the above decomposition can be done in linear time. After

5

s

Component C

t

floor

Component C

s

t

floor
Figure 1: The top figure illustrates the outside case, while the bottom figure illustrates the inside
case.

t

s

Figure 2: An example showing 6 components. Note the nested inside cases.

6

ceiling

-cr
up

backward

oss
-cr

forward

wn
do

oss

hanging

floor

Figure 3: The classification of links in a strip.
the decomposition, all the inner arcs of each strip are useless whereas the boundary arcs are useful
provided that the initial floor F is useful.
Now we formally define strips. A strip of C, denoted by CU,F , is a subgraph of C enclosed (in
the planar embedding) by two arc-disjoint paths U and F that share the first and the last vertices.
We assume that F is to the right of U in the right-first-search order from s. If we place the first
vertex of F and U on the left and the last vertex on the right, then F lies beneath U in the planar
drawing. Thus, we call F the floor and U the ceiling of the strip CU,F . Note that U and F form
the boundary of the strip CU,F .
Consider any strip CU,F . We call arcs in U and F boundary arcs and call other arcs (i.e.,
arcs in E(CU,F ) − (E(U ) ∪ E(F ))) inner arcs. Similarly, vertices in U and F are called boundary
vertices and other vertices (i.e., vertices in V (CU,F ) − (V (U ) ∪ V (F ))) are called inner vertices.
We call a path P ⊆ CU,F a link in the strip CU,F if the end-vertices of P are in the boundary
and no other vertices are in the boundary, i.e., V (P ) ∩ (V (U ) ∪ V (F )) = {u, v} where u, v is the
first and last vertices of P , respectively. Observe that a link has no arcs of the boundary, i.e.,
E(P ) ∩ (E(U ) ∪ E(F )) = ∅. Let us order vertices on the floor according to the order that they
appear in the floor F , and denote the order of a vertex v ∈ V (F ) by φ(v). If both end-vertices of
the link P are in F and φ(u) > φ(v), then we say that P is a backward path w.r.t to the floor F .
Otherwise, if φ(u) < φ(v), then we say that P is a forward path w.r.t to the floor F and ceiling C.
A link that goes from the floor F to an inner vertex of the ceiling U , then we call it an up-cross
path, and if it goes from an inner vertex of the ceiling U to the floor F , then we call it a down-cross
path. A link whose start and end at inner vertices of the ceiling C is called hanging path. Sometime
we abuse this classification of paths in CU,F also for paths that start and end on the floor F . The
classification of these links are shown in Figure 4.
An extended forward path Q is a u, v-path such that u, v ∈ V (F ) and Q contains no backward
path. It is easy to see that Q can be partitioned into a collection of paths Q1 , . . . , Qq such that
each Qi is either a forward path or a subpath of F . By this definition, the floor F itself is also
an extended forward path. We will sometimes abuse the term extended forward path to mean a
forward path. In this sense, the ceiling is also an extended forward path. Observe that any forward
path is useful and so are extended forward paths if the floor F is useful.
Lemma 5. Consider a strip CU,F such that the source vertex s and the sink vertex t are not in
CU,F . If F is useful, then so is any forward path w.r.t. CU,F .
7

Proof. Let u and v be the start and end vertices of F and P be a forward path connecting q, w ∈
V (F ). Since F is useful, there exists a simple s, t-path R that contains F . We may choose R to be
the shortest such path. Since s, t are not in CU,F , vertices in V (R) − V (F ) are not in CU,F . Let
Rs,u and Rv,t be the s, u and v, t subpaths of R. Let Fu,q and Fw,v be the u, q and w, v subpaths of
F . Then we construct a new path by concatenating these paths. Let R0 = Rs,u · Fu,q · P · Fw,v · Rv,t
be such a path. It can be seen that R0 is a simple path. This proves that P is useful.
The following corollary follows immediately from Lemma 5.
Corollary 6. Consider a strip CU,F such that the source vertex s and the sink vertex t are not in
CU,F . If F is useful, then so is any extended forward path w.r.t. CU,F .
Proof. We proceed the proof in the same way as in Lemma 5. First, since F is useful, there exists
a simple s, t-path R that contains F . Now consider any extended forward path P . Observe that
P can be partitioned into subpaths so that so that each subpath is either contained in R or is
a forward path w.r.t CU,F . For each u, v-subpath Q of P that is a forward path, we replace the
u, v-subpath of R by Q. Since Q is arc-disjoint from R, the above process results in a new simple
s, t-path containing P . This implies that P is useful.

4.1

The Decomposition Algorithm

Now we describe our strip decomposition algorithm. We start our discussion by presenting an
abstraction of our algorithm. We denote the initial (input) strip by CU ∗ ,F ∗ . We call U ∗ the topmost ceiling and call F ∗ the lowest floor. The top-most ceiling U ∗ can be a dummy ceiling that
does not exist in the graph.
The decomposition algorithm taking as input a strip CU,F . Then it finds the “right-most” path
P w.r.t. the floor F that is either a forward path or an up-cross path. This path P slices the strips
into two parts, the up-strip and the down-strip. See Figure 4. Intuitively, we wish to slice the input
strip so that the final collection consists of strips that have no forward, up-cross or down-cross
paths. The right-most path guarantees that the down-strip have no down-cross path. Moreover,
provided that the initial strip has no down cross path or hanging path, each final strip has no
forward, up-cross, down-cross, nor hanging path.
The naive implementation yields an O(n2 )-time algorithm. We devote the rest of this section
to present a linear-time algorithm for the strip-decomposition.
Lemma 7. There is a linear-time algorithm that, given as input a strip CU ∗ ,F ∗ , outputs a collection
S of strips such that each strip CU,F ∈ S has neither forward, up-cross, down-cross nor hanging
path. Moreover, if F ∗ is useful, then all the arcs in the boundary of any strip CU,F ∈ S are useful.

4.2

Linear Time Implementation

Now we present a linear-time implementation of our strip decomposition algorithm and thus prove
Lemma 7.
The input of our algorithm is an initial strip CU ∗ ,F ∗ . We insist that the input strip CU ∗ ,F ∗ has
no hanging path, but it might contain forward, up-cross or down-cross paths. In this sense, we
say that a strip is minimal if it has neither hanging, forward, up-cross nor down-cross paths (but,
the backward paths are allowed). The output of our algorithm is a collection S of strips that are

8

ceiling

Up Strip
Path P
Down Strip
floor

s’

t’

ceiling

Up Strip

Down Strip

Path P
s’

floor

t’

Figure 4: The path P slices the strip into up-strip and down-strips.

9

minimal. Let s0 and t0 be the first and the last vertex of F , respectively. Our Algorithm requires
the following initial color settings for vertices.
• All the inner vertices of CU,F are white.
• All the inner vertices of the ceiling U are green.
• All the vertices of the floor F are red.
• All the inner arcs of CU,F are white.
• All the border arcs of CU,F are black.
This initialization is done in Main-Decomposition (Algorithm 1). Then the algorithm calls a subroutine Decompose (Algorithm 3) to decompose the strip CU,F .
The recursive algorithm Decompose(CU,F , v) processes the strip in recursive manner. Given a
strip CU,F , the algorithm calls Find-Forward (Algorithm 2) to find a link P that is either a forward
path or an up-cross path, which slices the strip CU,F into two smaller strips CUdown ,Fdown and
CUup ,Fup and recursively partitions these two strips until we have a strip that has neither forward,
up-cross nor down-cross paths. Thus, the only links remaining in the strips are backward paths.
Our algorithm requires a careful implementation as these strips share boundary arcs. We guarantee
that our algorithm visits each arc on the boundary at most O(1) times and thus the algorithm runs
in linear time.
Note that the subroutine decompose will have a glitch if v is the first vertex s0 of the floor F
and there is no arc between the first arc of the ceiling U and the first arc of the floor F . The main
algorithm (Algorithm 1) prevents this issue by adding a dummy arc (s0 , z ∗ ) between (s0 , a) and
(s0 , b).
Algorithm 1 Main-Decomposition(CU ∗ ,F ∗ )
1: Let s0 , t0 be the first and the last vertices of F ∗ , respectively.
2: Mark all the inner vertices of CU ∗ ,F ∗ as white.
3: Mark all the inner vertices of the ceiling U ∗ as green.
4: Mark all the vertices of the floor F ∗ as red.
5: Mark s0 as black.
6: Mark all border arcs of CU ∗ ,F ∗ as black.
7: Mark all inner arcs of CU ∗ ,F ∗ as white.
8: {Glitch Prevention}
9: if there is no arc between the first arc of the ceiling U ∗ and the first arc of the floor F ∗ then
10:
Mark s0 as black.
11:
Let v be the second vertex of F (i.e., (s0 , v) ∈ E(F )).
12: else
13:
Let v := s0 .
14: end if
15: Call S := Decompose(CU,F , v).
16: return The collection of minimal strips S.

10

Algorithm 2 Find-Forward(CU,F , uv)
1: Mark v as grey.
2: Let vw := Right(uv) be the right most arc of uv.
3: while vw is white do
4:
Mark vw as black.
5:
if w is white then
6:
Call P := Find-Forward(CU,F , vw). .
7:
if P is not an empty path then
8:
return the path v · P .
9:
end if
10:
if w is red or green then
11:
return the path (v, w).
12:
end if
13:
end if
14:
Update vw := Next(vw).
15: end while
16: return An empty path ().

4.3

Implementation Details

Observe that we might create O(n) strips (and thus have O(n) floors and ceilings) during the run
of the decomposition algorithm. However, we cannot afford to store floors and ceilings of all the
strips separately as they are not arc disjoint. Otherwise, just storing them would require a running
time of O(n2 ). To avoid this issue, we keep paths (either floor or ceiling) as doubly linked lists. As
we will show in Lemma 12, our decomposition algorithm maintains an invariant that, at any point
in time, each arc is contained in at most one floor and at most one ceiling. Consequently, we can
store CU,F by referencing to the first and last arcs of the floor (respectively, ceiling). Moreover,
since we store paths as doubly linked list, each cut-and-join operations can be done in O(1) time.
Since we do not have the complete representation of CU,F , it is not clear if we can check the
memberships of arcs in the strip. As such, we use the coloring scheme to mark which vertices are
in the ceiling or in the floor. It is more difficult to check if vertices (resp., arcs) are in a particular
strip. Thus, we need to describe how to implement Step 9 of Algorithm 1 and Step 5 of Algorithm 3.
Consider a strip CU,F , and let s0 and t0 be the first and last vertices of the floor F , respectively.
We check if there is an arc between the first arc of the floor F , say s0 a and the first arc of the
ceiling U , say s0 b, by querying if s0 b is the arc next to s0 a in the counterclockwise order (i.e.,
Next(s0 a) = s0 b)). If so, then we know that there can be no arcs between s0 a and s0 b. This gives
an implementation of Step 9 of Algorithm 1 that runs in O(1) time.
Next let v be a vertex in the floor F . If v = s0 , then we can check if v is incident to an inner
arc of CU,F by checking if there is an arc between s0 a and s0 b (as previously discussed). Otherwise,
if v is an inner vertex of the path F , then we take a subpath (u, v, w) of F (which exists because v
is an inner vertex). Then check if the left-most arc of uv is vw (i.e., Left(uv) = vw)). If so, then
there can be no arc between uv and vw, meaning that v is incident to no inner arcs.

11

Algorithm 3 Decompose(CU,F , v)
1: Let s0 and t0 be the first and last vertices of F , respectively.
2: Initial P := () as an empty path.
3: while P = () and v 6= t0 do
4:
Mark v as black. .
5:
if v ∈ V (F ) is incident to an inner arc of CU,F then
6:
Let w be the vertex next to v in the floor F .
7:
Let vz := Next(vw) be the arc next to vw in the counterclockwise order.
8:
Call P := Find-Forward(CU,F , vz). .
9:
end if
10:
Update v := w (i.e., iterate to the next vertex).
11: end while
12: If P is an empty path, then return {CU,F }.
13: Mark all the inner vertices of P as green. .
14: Let v and w the first and last vertices of P , respectively.
15: if w is red (i.e., w ∈ V (F )) then
16:
Let Fs0 ,v , Fv,w and Fw,t0 be s0 , v, v, w and w, t0 subpaths of F , respectively.
17:
Let Uup := U and Fup := Fs0 ,v · P · Fw,t0 .
18:
Let Udown := P and Fdown := Fv,w .
19: else
20:
Let Fs0 ,v , Fv,t0 be s0 , v, v, t0 subpaths of F , respectively.
21:
Let Us0 ,w , Uw,t0 be s0 , w, w, t0 subpaths of U , respectively.
22:
Let Uup := Us0 ,w and Fup := Fs0 ,v · P .
23:
Let Udown := P · Uw,t0 and Fdown := Fv,t0 .
24: end if
25: {We decompose the down-strip before the up-strip.}
26: Let w be the vertex next to v in Fdown .
27: Sdown := Decompose(CUdown ,Fdown , w). .
28: Mark all the vertices of P except v as red. .
29: Sup := Decompose(CUup ,Fup , v). .
30: return S := Sup ∪ Sdown .

12

4.4

Properties of the Decomposition

Belows are the properties of our algorithms.
Lemma 8 (Boundary Bounded Search). Consider a call to Find-Forward(CU,F , uv). Suppose v
is an inner vertex of CU,F , and each vertex in the boundary of CU,F is either red, green or black.
Then, in any recursive call, Find-Forward never visits vertices outside of CU,F , and never changes
colors of border vertices of CU,F .
Proof. We prove the statement by induction.
Suppose the conditions hold, and consider a call to Find-Forward(CU,F , uv). The only step
where the algorithm changes the color of any vertex is in Step 1, where it changes the color of v
to grey. Since v is an inner vertex of CU,F , it is clear that the algorithm does not change colors of
border vertices in this call. Moreover, all the neighbors of v must be in CU,F . This means that the
arc vw that the algorithm processes in the while-loop (Step 3) must be such that w is in CU,F , and
w must be white because of the coloring assumption.
Next, consider the recursive-call in Step 6. By the condition in Step 5, the algorithm proceeds
to call Find-Forward(CU,F , vw) only if w is white and must be an inner vertex. Thus, the conditions remain hold for the next recursive call, and we deduce inductively that the assertion is true
throughout all the remaining recursive calls. Therefore, we conclude that the algorithm never visits
vertices outside of the strip CU,F , and it never changes colors of vertices in the border of CU,F .
Lemma 9 (Coloring Invariants). Consider the call to Algorithm 3, say Decompose(CU,F , v). Let
CU,F be the input strip, and let s0 and t0 be the first and the last vertices of the floor F . Then the
following invariants hold at the beginning of the decomposition.
• All the vertices in U except s0 and t0 are green.
• All the vertices in the s0 , v-subpath of F except v are black.
• All the vertices in the v, t0 -subpath of F except v are red.
• All the inner vertices (those in V (CU,F ) − (V (U ) ∪ V (F ))) are white or grey.
Proof. We prove the invariants by induction. The assertion is trivially true in the initial call to
Algorithm 3 (which is in turn called by Algorithm 1).
Suppose the invariants hold until some recursive call to Decompose(CU,F , v). If none of the calls
to Find-Forward(CU,F , vw) returns a non-empty path P , then we are done because there would be
no more recursive calls. Moreover, no vertices in CU,F are changed colors except those inner vertices
of CU,F because Find-Forward(CU,F , vw) never changes colors of vertices in the floor and the ceiling
by Lemma 8.
Now suppose that Find-Forward(CU,F , vw) returns a non-empty path P . By construction, all
the vertices in the s0 , v-subpath of F are colored black by Step 4 while other vertices in F remain
red. In Step 13, the Algorithm 3 changes colors of all the inner vertices of P to green. The last
vertex of P is either red or green, but in both cases, the path P becomes part of the ceiling Udown ,
and the coloring invariants remain hold for the pair of ceiling and floor Udown , Fdown by construction.
Thus, we inductively deduce that the invariant holds throughout the recursive call in Step 27. The
recursive call may change colors of vertices in the strip CUdown ,Fdown , but it never changes the color
of the inner vertices of the ceiling Udown . Thus, in either case, after changing the colors of vertices
13

in P except v to red in Step 28, we must have that the invariants hold for the pair of ceiling and
floor Uup , Fup . Therefore, inductively, we conclude that the invariants hold throughout the run of
the decomposition algorithm.
Lemma 10. Prior to the call to Find-Forward(CU,F , vz) in Step 8 of Algorithm 3, no out-neighbor
of a grey vertex is black or grey. Similarly, if Find-Forward(CU,F , vz) returns an empty path, then
no out-neighbor of a grey vertex is black or grey.
Proof. We prove the lemma by induction. The assertion is true prior to the first call to FindForward because, at the initial call to Algorithm 3 by the main algorithm (Algorithm 1), there is
no grey vertex.
Suppose the assertion is true prior to the call to Find-Forward(CU,F , vz) in Step 8. We will
show that the invariant still hold before to the next call to Find-Forward.
If Find-Forward returns an empty-path, then we know by the stopping condition of the subroutine that it could not find an arc vw such that w is a red or green vertex. Thus, all the vertices
marked grey by this call to Find-Forward have no red or green out-neighbors. We conclude that
the invariant remains hold in the next call to Find-Forward in the while-loop (Step 3).
If Find-Forward returns a non-empty path P , then let Z be a vertex that has been scanned
by Find-Forward, i.e., vertices that are colored grey in this call. Observe that vertices in Z −
V (P ) are those that have been scanned prior to vertices in V (P ). Thus, any vertex in Z − V (P )
has no white, red nor green out-neighbors; otherwise, Find-Forward would have terminated with
a non-empty path. As the algorithm marks all the inner vertices of P as green (Step 13) the
invariant remain holds for the next call to Find-Forward (if one exists) in the recursive call to
Decompose(CUdown ,Fdown , w) (Step 27) regardless of the color of the last vertex of P . We apply our
arguments inductively and conclude that the invariant holds throughout the recursive-call and all
its children processes. Then at the time the algorithm returned from Decompose(CUdown ,Fdown , w)
(after backtracking) all the grey vertices have neither white, red nor green out-neighbors. Now,
as the algorithm changes only the colors of the vertices in V (P ) − {v} (from green to red), the
invariant still holds before calling Decompose(CUup ,Fup , v) and thus the next call to Find-Forward
(if such call occurs). Therefore, we apply the induction hypothesis and conclude that the invariant
holds prior to every call to Find-Forward.
Lemma 11. Consider the run of Find-Forward(CU,F , vz) in Step 8 of Algorithm 3. Then the
algorithm returns a path P starting from v that is either a forward path or an up-cross path if one
exists. Thus, P is arc-disjoint from U and F .
Proof. We recall to the coloring invariants of Algorithm 3 in Lemma 9. It can be seen by the
construction that, at the time Algorithm 3 calls Find-Forward(CU,F , vz), all the vertices in the
s0 , v-subpaths of F are black.
Suppose the algorithm finds a path P , and let x and y be the first and last vertex of P ,
respectively. Then all the inner vertices of P must be grey because all the vertices that FindForward adds to P except x and y is grey by construction. (Note that y is red or green by the
stopping condition.) Thus, P must be a link that goes from a black vertex to a red vertex or to
a green vertex. We now apply the coloring invariants (Lemma 9). If it is the former case, then P
must go from the s0 , x-subpath Fs0 ,x of F to V (F ) − V (Fs0 ,x ), meaning that P is a forward path.
If it is the latter case, then P must go from the floor F to the ceiling U , meaning that that P is
an up-cross path. This proves the first statement of the lemma.
14

Now suppose that Find-Forward terminates without finding any path P (thus, it returns an
empty path). Then we will show that there is no forward nor up-cross path w.r.t. CU,F . By
Lemma 10, we know that, prior to and after the call to Find-Forward(CU,F , vz), no grey vertices
have a path to red or green vertices (because, otherwise, some of them would have white, red
or green out-neighbors). Thus, if there is a path Q in CU,F that goes from v to red or green
vertices, then all the inner vertices of Q must be white. Let Z be the vertices scanned by FindForward(CU,F , vz) (those that marked grey by the algorithm plus the vertex v). Then we known
that there is a vertex x ∈ V (Q) ∩ Z and a vertex y ∈ V (Q) − Z; otherwise, the path Q would
have scanned by Find-Forward, and it would have returned a non-empty path. We may assume
that xy is an arc of Q. Since y is not scanned by Find-Forward, it must be white while x is grey.
But, then we have a contradiction since a grey vertex x has a white out-neighbor y. Hence, if
Find-Forward(CU,F , vz) returns an empty path, there is no path from v to red or green vertices.
This proves the lemma.
Lemma 12 (Properties of the Collection of Strips). Let S be the collection of strips computed by
Algorithm 1. Then the following statements hold.
• Any arc e ∈ E(C) is contained in at most one floor and at most one ceiling, i.e., there is at
most one strip CU,F ∈ S such that e ∈ E(U ) (resp., E(F )).
• No two strips share inner arcs, i.e., for any strips CU,F , CU 0 ,F 0 ∈ S, (E(CU,F ) − (E(U ) ∪
E(F ))) ∩ (E(CU 0 ,F 0 ) − (E(U 0 ) ∪ E(F 0 ))) = ∅.
• Any strip CU,F ∈ S has no up-cross or forward path.
• Suppose the initial strip U ∗ in Main-Decompose (Algorithm 1) has no path outgoing from its
inner vertex to U or F . Then any strip CU,F ∈ S that has no down-cross path.
• Suppose F ∗ is a useful path. Then, for any strip CU,F ∈ S, all the arcs in U and F are useful.
Proof. We prove the first property by induction. Consider the work of the subroutine Decompose (Algorithm 3). If Decompose(CU,F , v) terminates without any recursive call, then it returns
{CU,F }. Thus, the first property holds. If Decompose(CU,F , v) makes other recursive calls (i.e.,
Decompose(CUdown ,Fdown , w) and Decompose(CUup ,Fup , v)), then we know by the construction of
Udown , Uup and Fdown , Fup that each of these pairs are arc disjoint. Thus, the property inductively
holds.
To prove the second property, let us consider the work of the decomposition algorithm (Algorithm 3). We will show by reverse induction that a collection of strips returned from each recursive
call to Algorithm 3 are disjoint in the inner part (i.e., inner arcs and vertices). This is true when
the algorithm cannot find a forward path P . Inductively, assume that the assertion is true until
some recursive call where the algorithm finds a non-empty path P . By the condition in Step 5,
we know that the first arc vz of P must be an inner arc, and z is an inner vertex of CU,F . Hence,
by Lemma 8, P must be a path in CU,F . By coloring invariants (Lemma 9), the path P is either
a forward or up-cross path. Thus, in any case, P slices the strip CU,F into two regions, which
are disjoint in the inner parts. Also, by construction, these two regions are enclosed by the paths
Udown , Fdown and Uup , Fup , respectively. Thus, the strips CUdown ,Fdown and CUup ,Fup are disjoint in
the inner parts, i.e., they have no common inner vertices. Applying the same arguments inductively,
we prove the second property.
15

Now we prove the third property. Suppose for a contradiction that there is a strip CU,F ∈ S that
has a forward or up-cross path. Then, by Lemma 11, during the run of the decomposition algorithm
(Algorithm 3), Find-Forward would have returned a non-empty path P , and the algorithm must
have decomposed CU,F into smaller strips CUdown ,Fdown and CUup ,Fup .
Next we prove the forth property. We suppose that the initial ceiling U ∗ in Main-Decompose
(Algorithm 1) has no path outgoing from its inner vertex to U or F . We will show that all the
strips in S has no down-cross path. We prove a stronger claim that the condition holds for every
call to Decompose(CU,F , v) (Algorithm 3). To be precise, consider a call to Decompose(CU,F , v).
Assume that no inner vertex of U has a path to U or F . Thus, CU,F has no down-cross path. If
there is no more decomposition, (i.e., Find-Forward never returns a non-empty path), then we are
done. Otherwise, if Find-Forward returns a non-empty path P , then the decomposition algorithm
produces two strips CUdown ,Fdown and CUup ,Fup .
Let us first examine the down-strip CUdown ,Fdown . If there is a path Q from the ceiling Udown to
the floor Fdown , then we know by Lemma 10 that all the inner vertices of Q must be white. This
path Q must go from a vertex x in V (Udown ) − V (P ) to a vertex y in the floor Fdown , which must
be a subpath of F by a construction. Observe that Q must be right to P w.r.t. the arc vz (in the
call Find-Forward(CU,F , vz)). But, then Find-Forward must have processed an arc xa of Q before
processing an arc xb of P . Thus, a cannot be a white vertex because its color must have been
changed, a contradiction. (Indeed, Find-Forward would have returned a path different from P .)
Next we examine the up-strip CUup ,Fup . We apply similar arguments. Suppose CUup ,Fup has a
path Q from Uup to Fup . Observe that in any case Uup must be a subpath of the ceiling U . Since
there is no path from an inner vertex of U to U or F , we know that Q must go from an inner vertex
of Uup to a vertex x of P . But, then by concatenating Q with a subpath of P starting from x, we
must have a path Q0 that goes from U to either U or F , a contradiction. Therefore, we inductively
conclude that there is no down-cross path in any strip CU,F in S, proving the forth property.
Finally, we prove the last property. Consider the construction of the up and down strips during
the decomposition of CU ∗ ,F ∗ . All the paths Uup , Fup , Udown , Fdown are extended forward paths of
F ∗ and thus useful by Lemma 5. Inductively, we repeat the same arguments on CUup ,Fup and
CUdown ,Fdown , we have that the boundary arcs of any strip CU,F ∈ S are useful.
Running Time Analysis. Now we analyze the running time of our algorithm. We claim that
our decomposition algorithm (Algorithm 1) runs in linear time. Our proof requires analyzing how
many times we scan each vertex and each arc in the component C.
Claim 13. The decomposition algorithm scans each arc at most O(1) times and scans each vertex
v at most O(1) times the total degree of v (indegree plus outdegree).
Proof. Consider the run of the algorithm Decompose (Algorithm 3). The algorithm scans an arc
in this call only if uv is an arc the floor F or is an arc leaving the floor. Since the algorithm keeps
moving the pointer to the next arc every time it scans an arc on the floor, the algorithm never
scans an arc on the floor twice, and such pointer is passed down to the deeper call, which means
that the entire process scans each arc once.
Next consider the run of the algorithm Find-Forward (Algorithm 2). If the algorithm founds a
black arc vw, then it will stop the process and return to the main procedure. Otherwise, it marks
vw as black and scans the arc next to vw in the counterclockwise order. The algorithm thus scans
an arc again only when it has scanned all the arcs leaving v. Thus, the procedure scans each arc
at most twice. In sum, the algorithm scans any arc at most O(1) times.
16

Observe that any vertex v has been marked grey before its leaving arcs are being scanned (and
perhaps re-colored as green or red later), any scanning process will stop whenever it reaches v.
After the algorithms scans all the arcs entering v, the algorithm will never scan v again, which
means that the total time the algorithm scans each vertex v is O(1) times the total degree of v
(indegree plus outdegree). This completes the proof.
It follows from Claim 13 that the decomposition algorithm scans every element (arcs an vertices)
of the component C at most O(1) times. This implies a linear running time of the decomposition
algorithm. Therefore, Lemma 7 immediately follows from Lemma 12 and the running time analysis.

5

The Outside Case: Determining useless arcs when s is not in
the component

In this section, we describe an algorithm that determines all useful arcs of a strongly connected
component C when the source s is in the infinite face.
We first outline our approach. Consider a strongly connected component C. If the boundary of
C is not a cycle, then the strong connectivity implies that we can extend some path on the boundary
to form a clockwise cycle, which contradicts to our initial assumption that the embedding has no
clockwise cycle.
If all arcs in the boundary of C are useless, then no arcs of C are useful. Otherwise, we claim
that some arcs of Q are useful and some are useless. Moreover, these arcs partition Q into two
paths Q1 and Q2 such that Q1 is a useful path and all arcs of Q2 are useless.
Lemma 14. Consider the boundary of a strongly connected component C. Let Q be the cycle that
forms the boundary of C. Then either all arcs of C are useless or there are non-trivial paths Q1
and Q2 such that
• E(Q) = E(Q1 ) ∪ E(Q2 ).
• Q1 is a useful path.
• All arcs of Q2 are useless.
Moreover, there is a linear-time algorithm that computes Q1 and Q2 .
Proof. First, we claim that all arcs of C are useless if and only if Q has no entrance or has no exit.
If Q has no entrance or has no exit, then it is clear that all arcs of C are useless because there
can be no simple s, t-path using an edge of C.
Suppose Q has at least one entrance u and at least one exist v. We will show that Q has both
useful and useless arcs, which can be partitioned into two paths as in the statement of the lemma.
Observe that no vertices of Q can be both entrance and exit because of the degree-three assumption. (Any vertex that is both entrance and exit must have degree at least four, two from Q
and two from the entrance and the exit paths.)
For any pair of entrance and exit u, v, let Quv be the u, v-subpath of Q. We claim that Quv is
a useful path. To see this, we apply Lemma 4. Thus, we have an s, u-path Pu and a v, t-path Pv
that are vertex disjoint. Moreover, Pu and Pv contain no vertices of Q except u and v, respectively.
Thus, R = Pu · Quv · Pv form a simple s, t-path, meaning that Quv is a useful path.
17

Notice that Q has no useless arc only if Q has two distinct entrances u1 , u2 and two distinct exits
v1 , v2 that appear in Q in interleaving order (u1 , v1 , u2 , v2 ). Now consider a shortest s, u1 -path Pu1 ,
a shortest s, u2 -path Pu2 , and the u1 , u2 -subpath Qu1 ,u2 of Q. These three paths together encloses
any path that leaves the component C through an exit v1 . Thus, any v1 , t-path must intersect
either Pu1 or Pu2 , contradicting Lemma 4.
Consequently, a sequence of entrances and exits appear in consecutive order on Q. Let us take
the first entrance u∗ and the last exit v ∗ . We know from the previous arguments that any pair of
entrance and exit yields a useful subpath of Q. More precisely, the u∗ , v ∗ -subpath Q1 of Q must be
useful and must contain all the entrances and exits because of the choices of u∗ and v ∗ . Consider
the other subpath – the v ∗ , u∗ -subpath Q2 of Q. The only entrance and exit on Q2 are u∗ and v ∗ ,
respectively. Thus, any path s, t-path P that contain an arc e of Q2 must intersect with the path
Q1 . But, then the path P together with the boundary Q enclose the region of C that has no exit.
Thus, P cannot be a simple path. It follows that no arcs of Q2 are useful.
To distinguish the above two cases, it suffices to compute all the entrances and exists of Q using
a standard graph searching algorithm. The running time of the algorithm is linear, and we need to
apply it once for all the strongly connected components. This completes the proof.

5.1

Algorithm for The Outside Case

Now we present our algorithm for the outside case. We assume that some arcs in the boundary of
C are useful and some are useless.
Our algorithm decides whether each arc in C is useful or useless by decomposing C into a
collection of minimal strips using the algorithm in Section 4. Then any arc enclosed inside a
minimal strip is useless (only boundary arcs are useful). Thus, we can determine the usefulness of
arcs in each strip. Observe, however, that the component C is not a strip because it is enclosed by
a cycle instead of two paths that go in the same direction. We transform C into a strip as follows.
First, we apply the algorithm as in Claim 14. Then we know the boundary of C, which is a cycle
consists of two paths Q1 and Q2 , where Q1 is a useful path and Q2 is a useless path. Let F ∗ = Q1 ,
and call it the lowest-floor. Note that F ∗ starts at an entrance sC and ends at an exit tC . We add
to C a dummy path U = (sC , u∗ , tC ), where u∗ is dummy vertex, and call U ∗ the top-most ceiling,
which is a dummy ceiling. This transforms C into a strip, denoted by CU ∗ ,F ∗ . (See Figure 5)
Now we are able to decompose CU ∗ ,F ∗ into a collection S of minimal strips by calling MainDecompose(CU ∗ ,F ∗ ). Since F ∗ is a useful path, we deduce from Corollary 6 that all the strips
CU,F ∈ S are such that both U and F are useful paths.
Next we show that no inner arcs of a strip CU,F ∈ S are useful, which then implies only arcs
in the boundaries of strips computed by the strip decomposition are useful. Therefore, we can
determine all the useful arc in C in linear-time.
Lemma 15. Consider a strip CU,F ∈ S computed by the strip-decomposition algorithm. Then no
inner arcs e of CU,F are useful. More precisely, all arcs in e ∈ E(CU,F ) − E(U ∪ F ) are useless.
Proof. Suppose for a contradiction that there is an inner arc e of CU,F that is useful. Then there is
an s, t path P containing e. We may also assume that P contains a link Q. That is, Q starts and
ends at some vertices u and v in V (U ∪ F ), respectively, and Q contains no arcs of E(U ∪ F ). By
Lemma 12, Q must be a backward path. Hence, it suffices to show that any backward path inside
the strip CU,F are useless.

18

U*

s

sC

u*

Component C

tC

t

F*

floor
Figure 5: The initial strip before the decomposition.
By the definition of the backward path Q, v must appear before u on F , and by Lemma 12, F
is a useful path, meaning that there is an s, t-path R containing F . Let s0 and t0 be the start and
end vertices of the strip CU,F (i.e., s0 and t0 are the common start and end vertices of the paths U
and F , respectively). Then we have four cases.
• Case 1: v = s0 and u = t0 . In this case, the path U and Q form a clockwise cycle, a
contradiction.
• Case 2: v = s0 and u 6= t0 . In this case, v has degree three in Q ∪ U ∪ F . Thus, the path
R ⊇ F must start at the same vertex as R; otherwise, v would have degree at least four. This
means that s = s0 , but then P could not be a simple s, t-path because s must appear in P at
least twice, a contradiction.
• Case 3: v 6= s0 and u = t0 . This case is similar to the former one. The vertex u has degree
three in Q ∪ U ∪ F . Thus, the path R ⊇ F must end at the same vertex as R; otherwise, u
would have degree at least four. This means that t = t0 , but then P could not be a simple
s, t-path because t must appear in P at least twice, a contradiction.
• Case 4: u 6= t0 and v 6= s0 . Observe that P must enter and leave CU,F on the right of F (and
thus R) at some vertices a and b, respectively. We may assume wlog that the a, u-subpath
and the v, b-subpath of P are contained in R. Moreover, it can been seen that u and v appear
in different orders on the path R (that contains F ) and the path P (that contains Q). Thus,
P must intersect either the s, b-subpath of R, say Rs,b , or the a, t-subpath of R, say Ra,t .
(Note that R contains no inner vertices of Q by the definition of a backward path.)
Suppose P intersects Ra,t at some vertex x, and assume that x is the last vertex of P in
the intersection of P and Ra,t . Since P enters R at the vertex a from the right, the x, asubpath of P must lie on the right of R. But, then the union of the x, a-subpath of P and the
a, x-subpath of R forms a clockwise cycle, a contradiction. (See Figure 6 for illustration.)
Now suppose P intersects Rs,b at some vertex y, and assume that y is the first vertex of
P in the intersection of P and Rs,b . Since P leaves R at the vertex b from the right, the
b, y-subpath of P must lie on the right of R. But, then the union of the b, y-subpath of P and
the y, b-subpath of R forms a clockwise cycle, again a contradiction.
19

Ceiling U
Path Q

u

v
Floor F

s

t

Figure 6: An illustration of Case 4 in the proof of Lemma 15

s'
C

s

C

s

s'

s

C

Figure 7: A reduction for simplifying the source structure for the inside case.
Therefore, all backward paths inside the strip CU,F are useless and so do inner arcs of CU,F .

6

The Inside Case: Determining useful arcs of a strongly connected component when s is inside of the component

In this section, we describe an algorithm for the case that the source vertex s is in the strongly
connected component C. In this case, the source vertex s is enclosed in some face fs in the
component C. It is possible that s is also enclosed in other strongly connected components (see
Figure 2). We shall perform a simple reduction so that s is inside this component C, has only
one outgoing arc, and every vertex has degree three as follows. First we collapse the maximal
component containing s inside fs into a vertex. To ensure the uniqueness of right-most paths
starting from s, we create a new vertex s0 pointing to s, and finally, we add additional vertices to
ensure the degree constraint (more precisely, we replace a degree d vertex by a binary tree on d
leaves). See Figure 7.

6.1

Overview

We decompose the problem of checking usefulness of component C into many subproblems and will
deal with each subproblem (almost) independently. The basis of our decomposition is in slicing the
component with the lowest-floor path F ∗ and the top-most ceiling U ∗ . These two paths then divide
20

Component C

s

Lowest floor F*

t’
t

Top most ceiling U*

Figure 8: the lowest-floor path F ∗ and the top-most ceiling U ∗ in the inside case.
Primary Strip

Ceiling Components

U*
s

F*

t’

Open Strip

Figure 9: The types of major strips in the inside case.
the component C into two parts: (1) the primary strip and (2) the open strip. Figure 8 illustrates
the paths F ∗ and U ∗ , and Figure 9 shows the schematic view of the primary and the open strips.
All types of strips and components will be defined next.
6.1.1

The lowest-floor path F ∗ .

We mainly apply the algorithm from Section 5 to the primary strip defined by two paths F ∗ and U ∗ ,
which may not be arc-disjoint. The path F ∗ is the lowest-floor path defined similar to the outside
case: We compute F ∗ by finding the right-most path P from s to t (hence, P is an s, t-path).
While t maybe outside of the component C, the right-most path P goes through some exit t0 on
the boundary of C. We let P 0 be the subset of P inside C. We then extend P 0 along the boundary
of C to include all the exits to obtain F ∗ (see Figure 10).
6.1.2

Flipped paths.

Unlike the outside case, the path F ∗ in the inside case does not divide the component C into two
parts because the source vertex s is inside some inner face of C. This leaves us more possibilities
of paths that we have not encountered in the outside case, called “flipped paths”.

21

Component C
s’
s

Figure 10: How to find F ∗ : path P is shown in solid red. The extension on the boundary is shown
as a dashed line.
To be precise, we say that an arc uu0 leaves F ∗ to the right if u ∈ V (F ∗ ) and uu0 lies on the
right of F ∗ . A path P leaves F ∗ to the right if its first arc of P leaves F ∗ to the right. We can
similarly say that an arc uu0 enters F ∗ from the right, if u0 ∈ V (F ∗ ) and uu0 lies on the right of
F ∗ , and a path P enters F ∗ from the right if its last arc enters F ∗ from the right. We can define
similarly for the case when a path leaves or enters F ∗ from the left. We also use the same notion
for path leaving (resp., entering) U ∗ .
Consider a simple path P which is internally vertex disjoint from F ∗ but whose end vertices
are in V (F ∗ ). Let u and v be the start and end vertices of P , respectively. We say that P is flipped
if it leaves F ∗ to the left and enters F ∗ from the right. Note that since F ∗ is right-most, no path
leaves F ∗ from the right and then enters F ∗ again from the right.
It is also impossible that a path leaves F ∗ to the right and enters F ∗ from the left as either case
it contradicts the fact that F ∗ is right-most or it introduces a clockwise cycle.
If P leaves F ∗ to the left and enters F ∗ from the left, P is not flipped. In this case, we can use
the same definition from the previous section. Recall that we can define an order φ of vertices in
V (F ∗ ). Thus, with respect to F ∗ and the ordering φ, the path P starting at u and ending at v can
either be forward or backward depending on φ(u) and φ(v).
If P is flipped and φ(v) > φ(u), we say that P is a forward flipped path. On the other hand, P is
a backward flipped path if P is flipped and φ(v) ≤ φ(u). For brevity, we refer to forward non-flipped
and backward non-flipped paths as only forward and backward paths, respectively. See Figure 11
for an illustration.
6.1.3

Primary Strip.

The primary strip is defined by two paths, which may not be arc-disjoint F ∗ and U ∗ . The path
F ∗ is the lowest-floor path. The path U ∗ is the top-most ceiling, which is an s, t-path such that
the strip CU ∗ ,F ∗ encloses all (non-flipped) forward paths (w.r.t. F ∗ ). U ∗ is essentially the left-most
path from s to t. Section 6.2 describes how we find U ∗ given F ∗

22

Backward
Path
U*
s

F*

Backward
Flipped Path
Forward
Flipped Path

t’

Open Strip

Figure 11: The types of paths in the open strip.
6.1.4

Open Strip.

The open strip Ĉ is defined to be everything outside the primary strip, i.e., Ĉ := C − CU ∗ ,F ∗ . See
Figure 11 for illustrations.
To deal with arcs in Ĉ, we first characterize the first set of useless arcs: ceiling arcs. An arc
e ∈ Ĉ = (u, v) is a ceiling arc if u can be reachable only from paths leaving F ∗ to the left and v can
reach t only through paths entering F ∗ from the left as well. These arcs form “ceiling components”.
(Note that paths that form ceiling components are all backward paths because all the forward paths
(w.r.t. F ∗ ) have been enclosed in CU ∗ ,F ∗ .) We shall prove that these paths are useless in Lemma 22.
Therefore, as a preprocessing step, after they are found, we delete them all from Ĉ.
To deal with remaining arcs in Ĉ, we first find strongly connected components H1 , H2 , . . . in Ĉ.
Arcs outside strongly connected components then form a directed acyclic graph D̂ that represents
essentially the structures of all flipped paths. We can process each component Hi using the outside
algorithm only if we know which adjacent arcs in D̂ are valid entrances and exits. For arcs in D̂
that belong to some flipped path, we can use a dynamic programming algorithm to compute all
reachability information needed to determine their usefulness.
Our algorithm can be described shortly as follows.
• Initialization. We compute the lowest-floor path F ∗ and the top-most ceiling U ∗ , thus
forming the primary strip CU ∗ ,F ∗ and the open strip Ĉ.
• The open strip (1): structures of flipped paths. We find all strongly connected components in Ĉ and collapse them to produce a directed acyclic graph (DAG) D̂. We compute
the reachability information of arcs in D̂ and use it to determine the usefulness of arcs in D̂.
• The open strip (2): process each strongly connected component. Then we apply
the outside algorithm to each strongly connected components in Ĉ.
• The primary strip. We determine the usefulness of arcs in the primary strip.
In the following subsections, we describe how to deal with each part of C.

23

6.2

Initialization: Finding the Primary and Open Strips

In this section, we discuss the initialization step of our algorithm, which computes the primary and
the open strips. In this step, we also compute the reachability information of flipped paths, which
will be used in the later part of our algorithm.
As discussed in the previous section, we compute the lowest-floor path F ∗ by finding the rightmost s, t-path, which is unique and well-defined because s has a single arc leaving it. The path F ∗
is contained in C because we assume that t is an exit vertex on the boundary of C.
The top-most ceiling U ∗ can be computed by simply computing the left-most path from s to t
and choosing such path that enters F ∗ from the left (this is to guarantee that U ∗ is not a flipped
path). This again can be done in linear-time by a standard implementation of depth-first-search.
Now we have the primary strip CU ∗ ,F ∗ , which we claim that it encloses all forward paths (w.r.t.
F ∗ ).
Lemma 16. Every forward path w.r.t. F ∗ is enclosed in CU ∗ ,F ∗ .
Proof. Suppose to a contrary that there exists a forward path P not enclosed by CU ∗ ,F ∗ . Then P
must intersect with U ∗ or F ∗ . If it is the former case, then P must have a subpath Q that leaves
and enters U ∗ on the left (this is because U ∗ is on the left of F ∗ ). We choose a subpath Q in which
the start vertex of Q, say u, appears before its end vertex, say v, on U ∗ . Such path Q must exist
because, otherwise, P would have a self-intersection inside CU ∗ ,F ∗ . We may further assume that
Q is a minimal such path, which means that arcs of Q lie entirely on the left of U ∗ . But, then U ∗
would not be a left-most path because the search algorithm would have followed Q instead of the
u, v-subpath of U ∗ , a contradiction.
The case that P intersects F ∗ is similar, and such path would contradict the fact that F ∗ is the
right-most path. Therefore, all the forward paths (w.r.t. F ∗ ) must be enclosed in CU ∗ ,F ∗ .
Next consider the remaining parts of the component, which forms the open strip Ĉ = C−CU ∗ ,F ∗ .
We have as a corollary of Lemma 16 that there is no simple s, t-path in the open strip that leaves
F ∗ from the right.
Corollary 17. No simple s, t0 -path that lies on the right of F ∗ .
Proof. Suppose there is an s, t-path P in the open strip that leaves F ∗ from the right. Then we have
three cases. First, if P also enters F ∗ from the right, then P cannot be a forward-path and cannot
have any forward subpath by Lemma 16. Thus, P must have a self-intersection, contradicting to the
fact that P is a simple path. Second, if P enters F ∗ from the left, then we can find a u, v-subpath
Q of P such that u appears before v in F ∗ and Q is arc-disjoint from F ∗ . But, then the rightfirst-search algorithm would have followed Q instead of the u, v-subpath of F ∗ , a contradiction.
Otherwise, if P never enters F ∗ , then it must go directly to t. But, then the right-first-search
algorithm would have followed the subpath of P that leaves F ∗ , a contradiction.

6.3

Working on the Open Strip (1): Dealing with Arcs in Flipped Paths

To check if an arc in a DAG D formed by contracting strongly connected components H1 , H2 , . . .
in the open strip is useful, it suffices to check if it is contained in some useful flipped path w.r.t.
F ∗.

24

H4
P1
H1

H3

H2
P2

F*

H5
Figure 12: An example of flipped backward paths P1 (useless) and P2 (useful). F ∗ is shown in red
and U ∗ is shown in blue. There are 5 humps (shown in gray).
We first prove characterization of useful flipped paths. Section 6.3.1 describe how we can
check if an arc belongs to any useful paths according to the characterization based on reachability
information.
We state our first observation that forward flipped paths are useful.
Lemma 18. Every forward flipped path w.r.t. F ∗ is useful.
Proof. Consider any forward flipped path P . By the definition of the forward flipped path, P shares
no arcs with F ∗ . Moreover, P starts at some vertex v ∈ F ∗ and ends at some vertex w ∈ F ∗ such
that v appears before w in F ∗ . Note that F ∗ is a path that goes from s to the vertex t0 in the
boundary of the component C. We extend F ∗ to a simple s, t-path R by adding a t0 , t-path that is
not in the component C. We then replace the u, v-subpath of R by P , thus getting a new path R0 ,
which is a simple path because R shares no arcs with P and contains no vertices of V (P ) − {v, w}.
Thus, R0 is a simple s, t-path, implying that P is useful.
If an arc is not contained in any forward flipped path, it must be in some backward flipped path.
In most cases, backward flipped paths are useless except when there exists an exit that provides
alternative route to t.
Consider the primary strip enclosed by the lowest-floor F ∗ and top-most ceiling U ∗ . If we remove
arcs that F ∗ and U ∗ share, i.e., F ∗ ∩ U ∗ , the strip can be decomposed into many subgraphs, which
we refer to as humps. Formally, a hump is a strip obtained from the primary strip by removing
F ∗ ∩ U ∗ . We can also order humps by the ordering of their first floor vertices. The structure of
humps is important in determining the usefulness of a flipped path. See Figure 12.
The lemma below shows the conditions when arcs in a backward flipped path can be useful.
Lemma 19. Let P be any backward flipped-path such that P starts at a vertex u ∈ F ∗ and ends at
a vertex v ∈ F ∗ . Then P̂ = P ∩ Ĉ (the subpath of P in the open strip) is useful iff P ends at some
hump H (thus, H contains v) such that either
1. both u and v are in the same hump H, and v is not the first vertex in H.
2. u is not in the hump H, and there is an exit after v in the hump H.

25

Proof. First, we show that if the end vertex v of P is not in any hump, then P̂ = P ∩ Ĉ is useless.
We assume wlog that the start vertex u of P is also not contained in any hump; otherwise, we
contract all vertices in the hump (that contains u) to the vertex u. Thus, P = P̂ . It suffices to
show that there is no s, u-path J that is vertex disjoint from P , which will imply that P cannot
be a useful path. To see this, assume a contradiction that there is an s, u-path J that is vertex
disjoint from P . Then J has to leave F ∗ at some vertex x and then enters F ∗ again at some vertex
y (it is possible that y = u) in such a way that x, y, u, v appears in the order (x, v, y, u) on F ∗ . Let
J 0 be the x, y-subpath of J. If J 0 is contained in the primary strip, then J 0 would induce a hump
containing v, a contradiction. So, we assume that J 0 is not contained in the primary strip. If J 0
leaves F ∗ from the right, then J 0 cannot enter F ∗ ; otherwise, it would contradict the fact that F ∗
is the right-most path. Hence, we are left with the case that J 0 leaves F ∗ from the left and then
enters again from the right. Since J and P are vertex-disjoint (and so is J 0 ), J 0 cannot enter F ∗ at
any vertex that appears after v (including u and y) because, otherwise, J 0 has to cross the path P .
Thus, we again have a contradiction. Consequently, since there is no path from s that can reach u
or the hump containing u without intersecting with P̂ , P̂ cannot be a useful path.
Next consider the case that v is contained in some hump H. Let w be a vertex in P ∩ U ∗ , i.e.,
w be a vertex in the ceiling intersecting with P . Also, let P̂ be P ∩ Ĉ.
For the backward direction, we construct a useful path Q containing P̂ by taking the union of
the prefix of the top-most ceiling U ∗ up to w, P̂ and the subpath PF of the floor F ∗ after v. In
Case (1), PF is the suffix of F ∗ after v, and in Case (2), PF starts from v and ends at the exit. It
can be seen that Q is a simple path from s to an exit, meaning that Q is a useful path and so is P̂ .
Let’s consider the forward direction. We prove by contraposition. There are two subcases we
have to consider: (i) u and v are in the same hump H, but v is the first vertex in the hump and
(ii) u is not in the hump H and there is no exit after v in H.
In Subcase (i), any useful path Q containing P̂ whose prefix up until P̂ is entirely in the primary
strip has to go through v; therefore, it cannot be simple. Consider the case when there is a useful
path Q containing P̂ outside the primary strip. The prefix Q0 of this path must reach w without
touching v (because v ∈ P̂ ). Observe that the union of H and P̂ contains a cycle enclosing the
source s, and by the construction of U ∗ , there is no path from s entering H ∩ U ∗ (otherwise, it
would have been included to U ∗ ). Consequently, because of planarity, the prefix Q0 must cross P̂ ,
meaning that Q cannot be simple.
Now we deal with Subcase (ii). Let x be the last floor vertex of H. First note that, by the
choice of F ∗ , any path from s to w not intersecting P̂ cannot cross F ∗ to the right; therefore, it
has to use x. Because of the same reason, any path from v ∈ F ∗ to t cannot leave F ∗ to the right;
thus, it must also go though x as well. Thus, a path from s to t containing P̂ in this case cannot
be simple.
6.3.1

Reachability information

After we compute the primary strip and the open strip, and collapse strongly connected components
in Ĉ, we run a linear-time preprocessing to compute reachability information.
For each vertex u in D̂ we would like to compute first(u) ∈ F ∗ defined to be the first vertex w
in F ∗ such that there is a path from s to u that uses w but not other vertex in F ∗ after w. We
also want to compute last(u) ∈ F ∗ defined to be the last vertex w0 in F ∗ such that there is a path
from u to t that uses w0 as the first vertex in F ∗ .
To find first(u), we perform left-first search tree T from s. We set first(u) for u ∈ Ĉ to be its
26

b2

b1
U*

s

b3
e

F*

t’

C
b’2

b’1

Figure 13: The arc e in the red path is useful when considering C as an outside case instance.
However, using the blue path as an entering path (at the entrance b3 ) and the green path as a
leaving path (at the exit b02 ) is not enough to show that. One can, instead, use the orange path (at
the entrance b1 ) as an entering path together with parts of the boundary to construct a forward
flipped path that contains e.
closest ancestor in the floor F ∗ . The mapping last(u) can be done similarly but going backward
from t.
6.3.2

Checking arcs in D̂

Now we describe our linear-time algorithm for determining the usefulness of arcs in D̂
Consider arc e = (u, v) ∈ D̂. If φ(first(u)) > φ(last(v)), then there exist a flipped forward path
containing e. Thus, by Lemma 18, e is useful.
If φ(first(u)) ≤ φ(last(v)), we need to check conditions in lemma 19. To do so, we need to
maintain additional information on every vertex v in F ∗ , namely the hump H(v) that contains it,
a flag representing if v is the first vertex in the hump, and a flag representing if the hump H(v)
contains a exit. Since these data can be preprocessed in linear-time, we can perform the check for
each arc e in constant time.

6.4

Working on the Open Strip (2): Dealing with Arcs in Strongly Connected
Components

Consider a strongly connected component Hi in the open strip. If no arcs going into Hi are useful
or no arcs leaving C are useful, clearly every arc in Hi are useless. However, it is not obvious that
applying the previous outside algorithm simply works because entering and leaving arcs determine
the usefulness of the path. See Figure 13, for example.
The following lemma proves that we can take the strongly connected component Hi and build
an outside case instance by attaching, for each useful arc in the DAG entering Hi or leaving Hi ,
corresponding to an entrance or an exit.
Lemma 20. Every arc in an outside instance of Hi is useful iff it is useful in the original graph.
Proof. The backward direction is straight-forward. Consider the forward direction: we would like
to show that if an arc e is useful in the instance, there exists a useful path containing it.
27

Suppose that Hi has n1 entrances and n2 exits. From Lemma 3 and an observation inside
Lemma 14 that entrance-exit pairs do not appear interleaving, we know that Hi is enclosed by a
counter-clockwise cycle and we can name all entrances as b1 , b2 , . . . , bn1 and all exits as b01 , b02 , . . . , b0n2
in such a way that they appear in counter-clockwise order as
b1 , b2 , . . . , bn1 , b01 , b02 , . . . , b0n2 .
Consider an arc e which is useful in this instance. Since e is useful, there is a vertex-disjoint
path P from some entrance bi to some exit b0j containing e. Since the boundary arcs form a counterclockwise cycle, we can extend P to start from b1 by adding boundary arcs from b1 to bi . We can
also extend P to reach b0n2 by adding arcs from b0j to b0n2 .
Since an arc entering C to b1 is useful and an arc leaving C from b0n2 is also useful, we can
construct a useful path containing e by joining a path from s to b1 , the path P , and a path from
b0n2 to t. Thus, e is useful.

6.5

Working on the Primary Strip

Given the primary strip CU ∗ ,F ∗ , we can use the algorithm from Section 5 to find all useful arcs
inside CU ∗ ,F ∗ . The next lemma proves the correctness of this step.
Lemma 21. A useful arc e in C is useful iff it is useful in CU ∗ ,F ∗ .
Proof. The backward direction is obvious. We focus on the forward direction. Assume for contradiction that there exist a useful arc e in C but e is not useful in CU ∗ ,F ∗ . Consider a useful path P
from s to t containing e. Since e is inside CU ∗ ,F ∗ , P must cross the lowest-floor F ∗ or the top-most
ceiling U ∗ . However, P cannot cross U ∗ as it would create a forward path outside the primary strip
(contradicting Lemma 16). Now suppose that P crosses F ∗ at some vertex w before e. If P do
not leave the primary strip after w, clearly e must be useful inside the primary strip. If P leaves
the primary strip at the ceiling after e, the subpath of P containing e is again a forward path.
We also note that P cannot leave CU ∗ ,F ∗ at the floor because it would cross itself. Since we reach
contradiction in every case, the lemma is proved.

6.6

The Ceiling Components are Useless

In this section, we prove that ceiling components are useless. A ceiling components are formed
from arcs e = (u, v) in Ĉ which can be reachable only from paths leaving F ∗ to the left and v can
reach t only through paths entering F ∗ from the left.
Lemma 22. Every ceiling arc e is useless.
Proof. Note that e does not lie in a forward path; otherwise e would be in the primary strip.
Let P be a useful path from s to t containing e. Let u0 be the last vertices of P ∩ U ∗ before
reaching e and v 0 be the first vertices of P ∩ U ∗ after leaving e.
Because of the degree constraint, P 0 must use the only incoming arc of u0 , defined to be eu and
the only outgoing arc of v 0 , defined to be ev . Let P1 be the prefix of P 0 from s to the head of eu
and P2 be the suffix of P 0 from tail of ev to t. The only way P2 can avoid crossing with P1 is to
cross U ∗ ; however, this creates a clockwise cycle.

28

U

Useful
Backward Paths

F
Vertices of Degree 4

A path from source

Figure 14: A strip CU,F is shown with inner useful arcs (shown in red). They are useful because of
a dotted path reaching an entrances at the floor path. Vertices of degree four are shown as squares.

7

Conclusions and open problems

We discuss briefly the open problems. In this paper we assume that each vertex has degree three
and the graph contains no clockwise cycles. Without the degree constraint, the structure of useful
paths becomes much more involved. Specifically, inner arcs in a strip forming backward paths can
be useful as shown in Figure 14. This also creates a lot of dependencies between strips inside the
strip decomposition.
An obvious open problem is to remove these assumptions and also to devise a linear-time
algorithm. Another interesting one would be to consider a larger class of graphs on surfaces.
Acknowledgement. We thank Joseph Cheriyan for introducing us the flow network simplification
problem. We also thank Karthik C.S. for pointing out some typos.

References
[BBV00]

Therese C. Biedl, Brona Brejová, and Tomás Vinar. Simplifying flow networks. In
Mathematical Foundations of Computer Science 2000, 25th International Symposium,
MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000, Proceedings, pages
192–201, 2000. 2

[BH13]

Glencora Borradaile and Anna Harutyunyan. Maximum st-Flow in Directed Planar
Graphs via Shortest Paths, pages 423–427. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. 3

[BK09]

Glencora Borradaile and Philip N. Klein. An O(n log n) algorithm for maximum st-flow
in a directed planar graph. J. ACM, 56(2), 2009. Preliminary version in SODA’06. 1, 2

[BKM+ 11] G. Borradaile, P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen. Multiplesource multiple-sink maximum flow in directed planar graphs in near-linear time. In
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 170–
179, Oct 2011. 3
29

[EK13]

David Eisenstat and Philip N. Klein. Linear-time algorithms for max flow and multiplesource shortest paths in unit-weight planar graphs. In Proceedings of the Forty-fifth
Annual ACM Symposium on Theory of Computing, STOC ’13, pages 735–744, New
York, NY, USA, 2013. ACM. 3

[Eri10]

Jeff Erickson. Maximum flows and parametric shortest paths in planar graphs. In
Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA ’10, pages 794–804, Philadelphia, PA, USA, 2010. Society for Industrial and
Applied Mathematics. 3

[FF56]

Lester R Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian
journal of Mathematics, 8(3):399–404, 1956. 1

[FHW80]

Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111–121, 1980. 2

[Fre87]

Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004–1022, 1987. 1

[Has81]

Refael Hassin. Maximum flow in (s, t) planar networks. Inf. Process. Lett., 13(3):107,
1981. 1

[HJ85]

Refael Hassin and Donald B. Johnson. An o(n log2 n) algorithm for maximum flow in
undirected planar networks. SIAM J. Comput., 14(3):612–624, 1985. 1

[HKRS97] Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. Faster
shortest-path algorithms for planar graphs. J. Comput. Syst. Sci., 55(1):3–23, 1997.
Preliminary version in STOC’94. 1
[INSW11] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.
Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose,
CA, USA, 6-8 June 2011, pages 313–322, 2011. 1
[IS79]

Alon Itai and Yossi Shiloach. Maximum flow in planar networks. SIAM J. Comput.,
8(2):135–150, 1979. 1

[KNK93]

Samir Khuller, Joseph Naor, and Philip N. Klein. The lattice structure of flow in planar
graphs. SIAM J. Discrete Math., 6(3):477–490, 1993. 2

[KRHS94] Philip N. Klein, Satish Rao, Monika Rauch Henzinger, and Sairam Subramanian. Faster
shortest-path algorithms for planar graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec,
Canada, pages 27–37, 1994. 1
[MN95]

Gary L. Miller and Joseph (Seffi) Naor. Flow in planar graphs with multiple sources
and sinks. SIAM Journal on Computing, 24(5):1002–1017, 1995. 3

[Rei83]

John 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. 1
30

[Wei97]

Karsten Weihe. Maximum (s, t)-flows in planar networks in o(|v|log|v|)-time. J. Comput. Syst. Sci., 55(3):454–476, 1997. Preliminary version in FOCS’94. 1, 2

31

