IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 50 (2012), 1170
ISSN 2232-2094
MULTIPLE-SOURCE SHORTEST PATHS IN EMBEDDED GRAPHS
Sergio Cabello Erin W. Chambers Jeff Erickson
Ljubljana, February 2, 2012
Multiple-Source Shortest Paths in Embedded Graphs*
Sergio Cabello1 Erin W. Chambers* Jeff Erickson§ January 30, 2012
Abstract
Let G be a directed graph with n vertices and non-negative weights in its directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. We describe an algorithm to preprocess the graph in O(gn log n) time, so that the shortest-path distance from any vertex on the boundary of f to any other vertex in G can be retrieved in O(logn) time. Our result directly generalizes the O(n log n)-time algorithm of Klein [Multiple-source shortest paths in planar graphs. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of f. As an application of our algorithm, we describe algorithms to compute a shortest non-contractible or non-separating cycle in embedded, undirected graphs in O(g2n logn) time.
o
Keywords: computational topology, topological graph theory, parametric shortest paths, dynamic data structures
I
U _
* A preliminary version appeared in [8].
department of Mathematics, IMFM, and Department of Mathematics, FMF, University of Ljubljana, Slovenia, sergio. cabello@fmf.uni-lj.si. Research partially supported by the European Community Sixth Framework Programme under a Marie Curie Intra-European Fellowship, and by the Slovenian Research Agency, projects P1-0297, J1-7218 and J1-4106.
^Department of Mathematics and Computer Science, Saint Louis University, echambe5@slu.edu. Portions of this work were done while the author was affiliated with the University of Illinois, Urbana-Champaign. Research partially supported by an NSF Graduate Research Fellowship and by NSF grants DMS-0528086 and CCF-1054779.
CD	§Department of Computer Science, University of Illinois, Urbana-Champaign, jeffe@cs.uiuc.edu. Research partially
supported by NSF grants DMS-0528086 and CCF-0915519.
5H
1 Introduction
O
Let G be a directed graph with n vertices and non-negative weights in the directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. In this paper, we describe an algorithm to preprocess the graph in 0(gn log n) time and space, so that later the shortest-path distance from any vertex on the boundary of f to any other vertex in G can be retrieved in 0(log n) time. Our preprocessing algorithm constructs an implicit representation of all shortest path trees rooted at vertices of f. Storing all these shortest path trees explicitly would require 0(n2) space in the worst case.
Euler's formula implies that any graph with n vertices embedded in a surface of genus g has 0(g + n) edges. Our problem can be solved by solving the all-pairs shortest path problem in G in 0(gn + n2 log n) time using Dijkstra's algorithm [15] with Fibonacci heaps [29]. When g = 0(1), the running time can be reduced to 0(n2) using the faster shortest-path algorithm of Henzinger et al. [36]; see also [53]. Our algorithm improves both of these running times if and only if g = o(n). Thus, for the rest of the paper, we assume g = o(n), which implies that G has 0(n) directed edges.
Our results generalize (and were inspired by) an algorithm of Klein [42] that solves the corresponding multiple-source shortest path problem in planar graphs in 0(n log n) time. Other noteworthy results on multiple-source shortest paths for planar graphs include Frederickson's all-pairs shortest paths representation [28], Lipton and Tarjan's planar separator theorem [44], and Schmidt's 0(n log n) algorithm that supports distance queries for specific subsets of vertices on a grid [47].
Let v0, v1,..., vk be the sequence of vertices around the specified face f. Klein's algorithm begins with a shortest path tree T rooted at v0 and then proceeds in k phases; at the end of the ith phase, T is the shortest path rooted at vi. At the beginning of the ith phase, the algorithm deletes the directed edge in T leading into vi, adds the directed edge from vi to v^ 1, and declares vi to be the new root. The algorithm then transforms T back into a shortest path tree through a series of pivot operations; each pivot changes the predecessor of some vertex, replacing its previous incoming edge with a new directed edge, just as in the classical shortest-path algorithms of Dijkstra [15] and Bellman and Ford [26]. Specifically, at each iteration, Klein's algorithm pivots the leafmost unrelaxed directed edge into T. This characterization exploits the classical observation, originally by von Staudt [56], that for any spanning tree T of any planar graph G, the edges not in T comprise a spanning tree of the dual graph G*. Klein describes how to find the leafmost unrelaxed directed edge and pivot it into T in 0(log n) time, using a dynamic tree data structure [49, 52]. He also proves that each directed edge pivots into T at most a constant number of times; the 0(n log n) running time follows immediately. To allow for future shortest-path queries, Klein maintains T in a persistent data structure [16].
The main obstacle to extend Klein's algorithm to higher-genus graphs is that the complement of a spanning tree is no longer a dual spanning tree, so there is no 'leafmost' unrelaxed directed edge. Our algorithm follows Klein's basic approach, but uses a different strategy for choosing which directed edges to pivot. Conceptually, we move the root of T continuously around the boundary of f and maintain the correct shortest path tree at all times. Even though the source vertex moves continuously, the combinatorial structure of the shortest path tree changes only at certain critical events, when one or more directed edges pivot into the tree. Our approach can be seen both as an example of the kinetic data structure paradigm proposed by Basch, Guibas, and Hershberger [2, 33] and as a special case of the parametric shortest path problem introduced by Karp and Orlin [38, 57].
A key observation in our analysis is that if we move the source vertex along a single edge of G, any directed edge of G pivots into the shortest-path tree at most once; thus, the number of pivots is equal to the symmetric difference between the initial and final shortest path trees. Moreover, as the source vertex moves around the boundary of f, each directed edge pivots into T at most 0(g) times. Our algorithm finds and executes each pivot in 0(g log n) time, using a complex data structure composed of 0(g) dynamic trees [49, 52]. These two bounds immediately imply that we can move the source completely
£ CO CO
around f in 0(g2n log n) time; a more refined approach improves this time bound to 0(gn log n). We describe our algorithm in the simpler setting of planar graphs in Section 3 and in full generality in (N Section 4.
In Section 5, as applications of our shortest-path algorithm, we describe algorithms to compute a shortest non-contractible cycle and a shortest non-separating cycle in a combinatorial surface in 0(g2 n log n) time. Thomassen developed the first algorithm to compute shortest non-contractible or non-separating cycles, by exploiting the so-called 3-path condition in 0(n3) time [55]; see also Mohar and Thomassen [45, Sect. 4.3]. Erickson and Har-Peled described a faster algorithm that runs in 0(n2logn) time [22]. Cabello and Mohar [10] gave an algorithm which runs in time g0(g)n3/2logn, the first algorithm for this problem to have a running time which was bounded by a function of the
CD
genus. Cabello [7] later improved the running time using separators to g0(g)n4/3. Finally, for orientable surfaces Kutz [43] developed an algorithm with a running time of g0(g) n log n which computed a finite portion of the universal cover and then did standard shortest path computations in the resulting planar graph. Our algorithm has a better dependence on the genus and, for nonorientable surfaces of bounded genus, it is the first one to achieve a running time of 0(n log n). Since the preliminary version [8] of this work appeared, the results have been used in [3, 5, 21, 23, 24, 25, 27, 37, 39].
O IN
2 Background
2.1 Surfaces, Embeddings, and Duality
Surfaces. A surface (alternatively, a topological 2-manifold with boundary) is a Hausdorff topological space in which every point has an open neighborhood homeomorphic to either the plane R2 or the closed upper half-plane. The points that do not have neighborhoods homeomorphic to R2 constitute the boundary of the surface. A cycle in a surface S is (the image of) a continuous map y: S1 ^ S; a cycle is simple if this map is injective. The genus of a surface S is the maximum number of simple disjoint cycles y1, Y2, • • •, Yg such that the subspace S \ (y1 U ■ ■ ■ U yg) is connected. A surface is orientable if it contains no subspace homeomorphic to the Mobius band. We consider only compact, connected surfaces in this paper; up to homeomorphism, such surfaces are uniquely determined by genus, orientability, and the number of boundaries. When dealing with an orientable surface (which will be the majority of the time), we also fix an orientation on the surface, so that terms like 'left', 'right', 'clockwise', and 'counterclockwise' are well-defined.
Curves and Homotopy. A path is (the image of) a continuous map p: [0,1] ^ S; it is simple if this map is injective. The endpoints of a path p are the points p(0) and p(1). A loop is a path p with p(0) = p(1). An arc is a path whose endpoints are on the boundary of S. The term curve refers to a cycle, path, or arc. If two paths p and q satisfy p(1) = q(0), their concatenation p • q is the path defined by (p ■ q)(t) = p(t/2), if t < 1/2, and (p ■ q)(t) = q(21 - 1), if t > 1/2.
A homotopy between two paths p and q is a continuous map H : [0,1] x [0,1] ^ S such that H(0, ■) = p, H(1, ■) = q, H(■, 0) = p(0) = q(0), and H(■, 1) = p(1) = q(1). A homotopy between two arcs a and /3 is a continuous map H : [0,1] x [0,1] ^ S such that H(0, ■) = a, H(1, ■) = /3, H(■, 0) is always in the same boundary component, and H(■, 1) is always in the same boundary component. A homotopy between two cycles y and /3 is a continuous map H : [0,1] x S1 such that H(0, ■) = y and H(1, ■) = /3. Two curves /3, y are homotopic when there is some homotopy between them, and we denote it by ft ~ y. Being homotopic is an equivalence relation. Up to homotopy, each boundary component of S admits two parameterizations as simple cycles, one being the reverse of the other. We say that a cycle is homotopic to a boundary component of S when it is homotopic to any of these two parameterizations. If y is a
CM &
C
r
o
simple cycle homotopic to a boundary 5 of S, and y and 5 are disjoint, then S \ y has two connected O components, one of them a topological annulus with y and 5 as boundaries.
A curve is contractible if it is homotopic to a constant map. In particular, a contractible arc must have its endpoints in the same boundary component 5 and, after contracting 5 to a point, the obtained loop must be contractible. A simple curve is separating if S \ y has two connected components. (This concept is related to that of Z2-homology, but we will not use homology in this paper.) A simple cycle y is contractible if and only if it bounds a disk, that is, S \ y has two connected components, one of them being a topological disk.
5H &
Darts and Embeddings. Let G = (V, E) be a directed graph. Following Borradaile and Klein [4, 6], we refer to the directed edges in E as the darts of G. (The term arc has been used for something else above.) Each dart connects two vertices, called its tail and its head; we will write u^v to denote a dart with tail u and head v. Each dart u^v has a unique reversal, defined by swapping its endpoints; thus, the reversal of u^v is v^u. We will assume that whenever G contains a dart u^v, then it also contains its reversal u^v. This can be enforced adding any missing darts with a large enough weight, like for example twice the sum of the weights of all original darts. (In our presentation we need the weights to be finite.)
Each dart u^v defines an associated (undirected) edge uv, which does not carry any orientation. An edge uv represents the pair of darts [u^v, v^u}. For any directed graph G = (V, E), we define its associated undirected graph Gun = (V, E) by replacing each dart with the associated edge. In most cases, there is no need to distinguish between G and Gun and we will use G to denote any of them.
Informally, an embedding of a directed graph G on a surface S is an embedding of its associated undirected graph: vertices are mapped to distinct points and edges are mapped to simple paths on S that connect the corresponding vertices. The darts u^v and v^u are embedded using the path of uv, but with different orientation. A face of an embedding is a maximal connected subset of S that does not intersect the image of any edge or vertex. An embedding is cellular (or 2-cell [45]) if every face is an open topological disk; in particular, if the surface has boundary, every boundary cycle must be covered by edges of the graph. Any cellular embedding can be represented combinatorially by a rotation system and a signature. A rotation system is a permutation n of the darts of G, where n(e) is the dart that appears immediately after e in the circular ordering of darts leaving tail(e). A signature is a mapping i: E(Gun) ^ [0,1} assigning a bit to each edge that indicates whether the cyclic ordering at its endpoints m are in the "same" direction or the "opposite" direction.
When the surface is orientable, the signature is not needed, and we can assume that the rotation system gives a counterclockwise ordering of the darts emanating from each vertex. Every dart in an embedded graph G separates two (possibly equal) faces. For orientable surfaces we may talk of the left shore and right shore, respectively denoted left(e) and right(e). Reversing any dart swaps its shores: left(v^u) = right(u^v) and right(v^u) = left(u^v).
If G is embedded on an orientable surface of genus g, Euler's formula | V | — |E| +1F| = 2 — 2g implies that G has at most 3n — 6 + 6g edges and at most 2n — 4 + 4g faces, with equality if every face of the embedding is a triangle. If the surface is non-orientable, then Euler's formula |V| — |E| + |F| = 2 — g implies that G has at most 3n — 6 + 3g edges and at most 2n — 4 + 2g faces. We consider only graphs and surfaces with g = o(n), so in either case the overall complexity of any embedding is O(n).
Our algorithms require an explicit cellular embedding as part of the input. If no embedding is provided, it is easy to construct an embedding of any given graph on some surface, but the genus of this surface may be Q(n) even when the minimum possible genus is constant [12]. Determining whether a given graph G can be embedded on an surface of genus g is NP-complete [54], although there is an
U
CD
embedding algorithm that runs in gO(g)n log n time [40]. Moreover, for any fixed e > 0, approximating the genus of an n-vertex graph within a factor of O(n1-e) is NP-hard [12].
C^
Combinatorial Surfaces. A combinatorial surface M is a surface S together with an undirected multigraph G with non-negative edge weights embedded cellularly on S. This concept, which we will use in Section 5, was introduced by Colin de Verdiere [13] and it is equivalent to cellular embeddings of graphs. The combinatorial surface model is dual to the cross-metric surface model; see [14] for more discussion on this. The complexity of a combinatorial surface is the size of the multigraph that describes U it.
In combinatorial surfaces, all curves are restricted to lie on G, possibly with repeated edges or vertices. Thus, a curve is a walk in G. We say a curve is simple if it can be infinitesimally perturbed off of G to be simple in S; note that this allows a simple curve to follow the same edge multiple times. Similarly, two curves are non-crossing if they can be infinitesimally perturbed to non-crossing curves. The multiplicity of a curve is the maximum number of times that the same edge appears in the curve. The length of a curve y, denoted by |y|, is the sum of the edge weights of its edges, where each edge weight is counted as many times as the corresponding edge appears in the curve.
Duality. The dual of a surface-embedded graph G is another graph G* embedded on the same surface, whose vertices correspond to faces of G and vice versa. Two vertices in G* are joined by an edge if and only if the corresponding faces of G are separated by an edge of G; thus, every edge e in G has a corresponding dual edge e* in G*. Similarly, every vertex v of G corresponds to a face v * of G*, and every face f of G corresponds to a vertex f * of G*. Each dual edge e* is embedded so that it crosses the corresponding primal edge e exactly once and intersects no other primal edge. Duality is an involution—the dual of G* is isomorphic to the original graph G. We will use duality only in orientable surfaces. In this case we will use a duality for darts defined by e * := (right(e))*^(left(e))*. (For darts
CO
this is not an involution because ((u^v)*)* = v^u.)
For any subgraph H of G, let H* denote the corresponding subgraph of G*.
To simplify notation, we will consistently use the letters s, u, v, w, x, y, z to denote vertices in the primal graph G, and the letters a, b, c, d to denote vertices in the dual graph G*. Thus, a* will always denote a face of G. (However, e is always an edge of G, f is always a face of G, and g is always the genus of the underlying surface.)
£ CO CO
Tree and Cotrees. Let G be an undirected graph embedded on a surface of genus g without boundary. A spanning tree of G is just a tree formed by some subset of the edges of G that includes every vertex of G. If C* is a tree contained in the dual graph G*, we call the corresponding primal subgraph C a cotree of G; if moreover C* is a spanning tree of G*, we call C a spanning cotree. A tree-cotree decomposition of G is a partition of G into three edge-disjoint subgraphs: a spanning tree T, a spanning cotree C, and the leftover edges L = G \ (T u C) [18]. For any spanning tree T, we can complete a tree-cotree decomposition by choosing any spanning tree C* of the dual subgraph (G \ T)*. Euler's formula implies that | L | = 2g; in particular, when the underlying surface is the sphere, L is empty.
CD
■ i-H J-H
CD CO
u
2.2 Shortest-Path Trees
Definitions. Let G = (V, E) be a directed graph, and let w: E ^ R+ be a non-negative weight function O p on the edges. To shorten some expressions we define for every edge uv the weight
CD
w(uv) := w(u^v) + w(v^u).
U
CU
A shortest-path tree is a spanning tree of G that contains shortest paths from a source vertex s to every other vertex of G. Shortest-path trees are typically represented by storing two values at every vertex: dist(v) is the shortest-path distance from s to v, and pred(v) is the predecessor of v in the shortest path from s to v, or equivalently, the parent of v if we regard the tree as rooted at s. In particular, dist(s) = 0 and pred(s) = Null. We define the slack of any dart u^v as follows:
slack(u^v) := dist(u) + w(u^v) — dist(v).
So for any edge uv, we have
slack(v^u) + slack(v^u) = w(u^v) + w(v^u) = w (uv).
A dart is tense if its slack is negative, and an undirected edge is tense if either of its darts is tense. A classical result of Ford [26], exploited by almost all shortest-path algorithms, states that a collection of distances and predecessors describes a shortest-path tree if and only if there are no tense edges, dist(s) = 0, and slack(pred(v)^v) = 0 for every vertex v = s.
It is helpful to view the graph G as a continuous space, so that distances and shortest paths between points in the interior of edges are also well-defined. Specifically, each edge uv is homeomorphic to an interval [0,1]; each value A e [0,1] represents a point sA on uv such that the distance from sA to u is Aw(v^u), the distance from u to sA is Aw(u^v), the distance from sA to v is (1 — A)w(u^v), and the distance from v to sA is (1 — A)w(v^u). In particular, s0 = u and s1 = v.
For simplicity we will assume that shortest paths are unique, and the union of all shortest paths from a common source vertex forms a tree. This assumption may be enforced by adding random infinitesimal weights to each edge; using the isolation lemma of [46], this yields shortest paths with high probability.
o
Parametric Shortest Paths. Our algorithm can be viewed as a special case of the parametric shortest path problem introduced by Karp and Orlin [38]; see also [19, 20, 32, 57]. Suppose we are given a graph whose dart weights are linear functions of a parameter A; specifically, let wA(e) = w(e) + A ■ w'(e), for given functions w, w': E ^ R. (In Karp and Orlin's original formulation, w'(e) e {0,1} for every dart e.) Let TA denote the shortest-path tree rooted at some fixed source vertex s with respect to the weights wA. The parametric shortest-path problem asks us to compute TA for all A in a certain range.
To solve this problem, Karp and Orlin [38] propose maintaining TA while continuously increasing the parameter A. Although the shortest-path distances vary continuously as a function of A, the combinatorial structure of TA changes only at certain critical values of A. A critical value occurs when the slack of some non-tree dart y ^z decreases to zero; thus, y ^z is just about to become tense. At this critical value, the dart y ^z pivots into the shortest-path tree, replacing some other dart x^z; in other words, y becomes the new predecessor of z.1
The running time of any parametric shortest-path algorithm clearly depends on two factors: (1) the amortized time required to identify the next tense dart and pivot it into the tree and (2) the number of pivots. We also assume genericity in the sense that at most one pivot occurs at a time, which is again
CO
enforced by our assumption of unique shortest paths using infinitesimal perturbations and the isolation lemma [46].
Karp and Orlin's parametric shortest-path algorithm is an early prototypical example of the kinetic data structure paradigm of Basch, Guibas, and Hershberger [2, 33]. Their algorithms (and ours) can also be interpreted as a special case of the parametric objective simplex algorithm of Gass and Saaty [30, 41]; similar approaches have been applied to several other classical parametric optimization problems [1, 17, 34].
a "
1If z is an ancestor of y, this pivot introduces a cycle into TA; for all larger values of A, the total weight of this cycle is
CD negative, and the shortest-path tree TA is not well-defined. In our algorithm, darts will always have non-negative weight, so this condition never arises.
£ CO CO
o
IN
2.3 Dynamic Forest Data Structures
o
Our algorithms require dynamic forest data structures that implicitly maintain dart or vertex values under edge insertions, edge deletions, and updates to the values in certain substructures. We require two different data structures, which we call the primal tree structure and the dual forest structure, for reasons that will become clear later.
&
Primal tree structure. Our first data structure maintains a dynamic rooted forest with real values associated with the vertices; in our application, these values are shortest-path distances. The data structure supports the following operations:
•	CREATE(vai): Return a new tree containing a single vertex with value val.
•	CUT(e): Remove the edge e from the tree T that contains it. The subtree that contains the root of T keeps that node as its root; the other subtree takes as root the endpoint of e that it contains.
•	Link(u, v): Add the edge uv to the forest; the root of the subtree containing u becomes the root of the new larger tree. This operation assumes that u and v are initially in different trees.
•	GetNodeValue(v): Return the value associated with vertex v.
•	AddSubtree(A, v): Add the real value A to the value of every vertex in the subtree rooted at v.
We emphasize that the operations Link(u, v) and Link(v, u) give rise to the same undirected tree, but with different roots. Several dynamic forest data structures, including Euler-tour trees [35, 51] and self-adjusting top trees [52], support each of these operations in 0(log n) amortized time, where n is the number of vertices in the forest.
(N CO
Dual forest structure. Our second data structure maintains a dynamic undirected, unrooted forest, with two values val(u^v) and val(v^u) associated with every edge uv; that is, we associate separate values with each dart of the forest. In our application, we will have an orientable surface, each tree in the dynamic forest is a subgraph of the dual graph G*, and the value associated with any dart in the forest is equal to the slack of the corresponding primal dart. The data structure supports the following operations:
•	Create( ): Return a new one-vertex tree.
•	Cut(uv): Remove the edge uv from the forest.
•	Link(u^v, a, 13): Add the edge uv to the forest and set val(u^v) = a and val(v^u) = 5. This operation assumes that u and v are initially in different trees. The operations Link(u, v, a, 5) and Link(v, u, 5, a) yield identical results.
•	GetDartValue(u ^v): Returns the value val(u^v). This operation assumes that uv is an edge in the forest.
&
•	AddPath(A, u, v): For each dart x^y on the (unique) directed path from u to v, add A to val(x^y) and subtract A from val(y^x). This operation assumes that u and v lie in the same tree.
a
•	MinPath(u, v): Return a dart x^y on the (unique) directed path from u to v, such that val(x^y) is minimized. This operation assumes that u and v lie in the same tree.
£ CO CO
• Junction(£, u, v): Return the unique node that lies on the paths from t to u, from u to v, and from v to t in the forest. This operation assumes that the nodes t, u, and v lie in the same component of the forest.
Several dynamic forest data structures, including link-cut trees [49] and self-adjusting top trees [52], can be adapted to support each of these operations in 0(log n) amortized time. In their original formulations, these data structures maintain only a single value at each undirected edge. However, Goldberg, Grigoriadis, and Tarjan [31, 50] describe the necessary modifications to link-cut trees [49]

3
to support values on directed edges, specifically for use in network-simplex algorithms, of which our algorithm is an example. Similar modifications can be applied to any other dynamic tree structure.
The only operation we require that is not part of the standard dynamic-tree literature is Junction. Here we describe how to implement this operation using link-cut trees; similar methods can be used with more recent dynamic tree data structures. Internally, link-cut trees actually represent each component of the forest as a rooted tree. Link-cut trees support two additional operations:
o
IN
£ CO CO
Evert(v): Make vertex v the root of the tree that contains it.
LCA(u, v): Return the least common ancestor of vertices u and v. This operation assumes u and v lie in the same tree [49, p. 387].
We can implement JuNCTiON(t, u, v) simply by calling EvERT(t) and then returning LCA(u, v).
3 Algorithm for Planar Graphs
Before describing our algorithm in full generality, we first consider the special case g = 0. Given a planar graph G and one of its faces f, our algorithm computes an implicit representation of the shortest path tree rooted at every vertex on the boundary of f.
Our high-level approach is similar to Klein's algorithm [42]. We begin by computing a shortest-path tree T rooted at an arbitrary vertex on the boundary of f. We maintain T and the complementary dual spanning tree C* = (G \ T)* in appropriate dynamic forest data structures. Then, for each edge uv in order around the boundary of f , we modify the shortest path tree rooted at u until it becomes the shortest path tree rooted at v. However, our algorithm uses a different pivoting strategy to update the tree. Klein's algorithm moves the source directly from u to v and then performs a sequence of pivots to repair the tree; our algorithm maintains a parametric shortest-path tree as the source point moves continuously from u to v.
3.1 Moving Along an Edge
CO
Consider a single edge uv in G. Suppose we have already computed the shortest path tree Tu rooted at u. We transform Tu into the shortest-path tree Tv rooted at v using a parametric shortest path algorithm as follows. First, we insert a new vertex s in the interior of uv, bisecting it into two edges su and sv with the parametric weights
4J
w X(u—s) := Xw(u-v), wX(s—u) := Xw(v-u),
wX(v—s) := (1 — X)w(v-u) and wX(s—v) := (1 — X)w(u—v).
&
Every other dart x—y has constant parametric weight wX(x—y) := w(x—y). We then maintain the shortest-path tree Tx rooted at s, with respect to the weight function wX, as the parameter X increases
continuously from 0 to 1. The initial shortest-path tree T0 is equal to Tu, and the final tree T1 is equal to Tv.
CM	For any vertex x and any parameter value A e [0,1], let distxix) denote the distance from s to x
with respect to the weight function wA. We color each vertex x red if distA(x) is an increasing function of A, or blue if distA(x) is a decreasing function of A.2 Every vertex except s is either red or blue. If su is an edge in TA, then every vertex in the subtree rooted at u is red; symmetrically, if sv is an edge in TA, then every vertex in the subtree rooted at v is blue. T0 may contain only red vertices, and T1 may contain only blue vertices, but there is always an interval of values of A such that TA contains vertices of both colors. For example it holds wA(s^u) = wA(s^v) when A = w(u^v)/w(uv). We color an edge of G J3 green if it has one red endpoint and one blue endpoint.
Similarly, let slackA(x ^y) denote the slack of x^y with respect to the weight function wA:
slackA(x^y) := distA(x) + Wa(x^y) - distA(y).
We call a dart x^y active if slackA(x^y) is a decreasing function of A; only active darts can become tense.
The following lemma applies to arbitrary graphs, not just planar graphs or even graphs on surfaces.
IN
CM 00
slackA(x^y) = distA(x) + wa(x^y) - distA(y)
Lemma 3.1. The following claims hold for all real A e [0,1].
(a)	If su e Ta, there are no active darts.
(b)	Ifsv e Ta, the only active dart is s^v.
(c)	Otherwise, x ^y is active if and only if x is blue and y is red.
Proof: Consider an arbitrary dart x^y. If x is blue and y is red then, for some constants o0, o1, o2 > 0,
o
CM
= wA (s^-v) + o 1 + w( x ^ y) — wA(s^u) — o2 = (1 — A)w(u^v) + o1 + w( x ^y) — Aw(v^u) — o2 = 00 — Aw (uv),
and therefore x^y is active. Symmetrically, if x is red and y is blue, then slackA(x^y) is an increasing function of A, and so x^y is not active. Finally, if x and y are both red or both blue, then slackA(x^y) is constant, so x ^y is not active.
If su is not an edge in TA, then sv e TA, and thus every vertex except s is blue. In this case, 1—1 slackA(u^s) is constant and slackA(s^u) is increasing with A, so no dart is active.
Similarly, if sv is not an edge in TA, then su e TA, and thus every vertex except s is red. In this case, slackA(v^s) is constant and slackA(s^v) is decreasing with A, so s^v is the only active dart.	□
The proof of Lemma 3.1 has two immediate corollaries, which also apply to arbitrary graphs:
Corollary 3.2. Fix a real value A such that TA contains both su and sv. As A increases, the next dart to become tense (if any) is the active dart x^y such that slackA(x^y) is minimized.
Proof: If x ^ y is active, then slackA( x ^y) = o0 — Aw (uv) for some constant o0 > 0. Thus, the slack of every active dart decreases at exactly the same rate.	□
Corollary 3.3. As A increases continuously from 0 to 1, the number of pivots in TA is equal to the number of edges in Tu \ Tv.
Proof: Just before any dart x ^y pivots into the shortest-path tree, x is blue and y is red; after the pivot, both x and y are blue. Thus, any dart that pivots into TA never pivots out again.	□
a
CD	2Readers familiar with astronomy may recall that visible light from objects moving away from the earth is shifted toward
red, and visible light from objects moving toward the earth is shifted toward blue.
1—1 o
b
u
CD
Figure 1. A single pivot in a planar shortest-path tree. Thick (red and blue) lines indicate the shortest-path tree Tx; the dotted (green) path is nx; the hollow arrow indicates the pivoting dart x^y.
o
IN
0 o
1
CO ^
CO CO
3.2 Pivoting Quickly
To identify the next pivot quickly when G is planar, we maintain both the shortest-path tree Tx and its complementary spanning cotree Cx = G \ Tx in dynamic tree structures. Specifically, we store Tx in a primal tree structure, where the value of any node v is distx(v), and we store CX in a dual forest structure, where the value associated with any dual dart is the slack of the corresponding primal dart: val((x^y)*) := slackA(x^y).
To simplify notation related to the dart u^v, let a be the face tail((u^v)*) = right(u^v)*, let b be the face head((u^v)*) = left(u^v)*, and let nx denote the unique directed path from a to b in the in the dual spanning tree See Figure 1.
Lemma 3.4. If Tx contains both su and sv, then the next dart to become tense (if any) is the dart with minimum slack whose dual lies in the directed path nx.
Proof: Lemma 3.1 and Corollary 3.2 imply that the next dart to become tense is the active dart x^y with minimum slack. Thus, it suffices to prove that a dart is active if and only if its dual lies in nx.
The coloring of the vertices of G extends by duality to a coloring of the faces of G*. Because the red and blue vertices of G define subtrees of Tx, the union of the red dual faces and the union of the blue dual faces are both connected. Thus, both of these unions are topological disks whose common boundary is a cycle in G*, composed of the edge ab and the unique (undirected) path from a to b in Any active dart must cross this cycle in the opposite direction as the dart u^v.	□
Lemma 3.5. We can perform the next pivot into Tx in 0(log n) amortized time.
CO CD
$H
CD CO
u
a
CD U
Proof: Our algorithms for finding the next dart to pivot and executing the pivot are shown in Figure 2. Each algorithm performs a constant number of dynamic forest operations, plus a constant amount of additional work.
Under most circumstances, calling MiNPATH(a, b) gives us (the dual of) the next dart x^y to pivot into the tree, but there are several boundary cases. Two such cases are described by Lemma 3.1(a) and (b); another arises when there is too much slack for x^y to pivot before X reaches 1. To detect this latter case, we compute the value XX that would make the slack of x ^y zero and check whether it is below 1. All these cases are handled by our algorithm FindNextPivot.
If FindNextPivot returns a dart x^y, we perform the necessary data structure updates by calling Pivot(x^y). If A is the current slack of x^y, the parameter X must increase by A/w(uv) before x^y actually pivots into Tx. We increase the distances of the red vertices by AR = Aw(v^u)/w(uv) by calling AddSubtree(Ar, u), decrease the distances at the blue vertices by AB = Aw(u^v)/w(uv) by
A
1—1 o
b
u
CD
FindNextPivot: if pred(v) = s then return s^v if pred(u) = s then return Null
(x^y)* ^ MiNPATH(a, b) A ^ GetDartValue((x^y)*)
A ^ A + A/w(uv)
if A < 1
return x ^y
else
return Null
Pivot( x ^ y): A ^ GetDartValue((x^y)*) A ^ A + A/w(uv) Ab ^ Aw(u^v)/w(uv) Ar ^ Aw(v^u)/w(uv)
if pred(u) = s then AddSubtree(Ar, u) if pred(v) = s then AddSubtree(-Ab, v) AddPath(-A, a, b)
z ^ pred(y); pred(y) ^ x
CuT(zy); Link(x,y)
Cut((xy)*); Link((z^j)*,0, w(yz))
Figure 2. Algorithms to find and execute the next pivot when G is planar.
o
IN
calling AddSubtree(-Ab, v), and adjust the slacks of all the active darts and their reversals by calling AddPath(-a, a, b). Finally, we fix the underlying tree-cotree decomposition using two Cut and two Link operations.	□
0 Ö
o
1
CO ^
CO CO
When there are no edges left to pivot into the tree TA, the algorithm FindNextPivot returns Null. However, we still have to "slide" the source s by 1 — A to reach v. Thus, the distances in the primal tree have to be updated by calling AddSubtree(—(1 — A)w(u^v)/w(uv), v) and, if pred(u) = s, also AddSubtree((1 — A)w( v ^u)/w (uv), u).
Theorem 3.6. Let G be a directed plane graph with n vertices, and let s be any vertex in G. After O(n log n) preprocessing time, we can maintain a representation of the shortest-path tree Ts that supports the following operations:
•	Given any vertex v, return the shortest-path distance from s to v in O(log n) time.
•	Given any vertex v, return the last edge on the shortest path from s to v in O(1) time.
•	For any edge sv, change the source vertex from s to v in O(k log n) amortized time, where k is the number of edges in Ts \ Tv.
A nearly identical algorithm updates the shortest-path tree after changing the weight of any single edge, or deleting an edge, or inserting an edge (provided the graph remains planar), in O(klogn) amortized time, where k is the number of edges added to or deleted from the shortest-path tree.
3.3 Moving Around a Face
CO CD
$H
CD
m
u
a
CD U
Finally, we bound the running time of our algorithm as the source vertex moves all the way around the boundary of a given face f. Klein [42] noted that if one maintains the so-called leftmost shortest path tree, each edge enters and leaves the shortest path tree at most a constant number of times. (For graphs with unique shortest paths, the leftmost shortest path tree is the unique shortest path tree.) This property also holds for our algorithm.
Lemma 3.7. As the source points moves around the boundary off, each dart of G pivots into (or out of) the shortest path tree rooted at s at most once.
Proof: Without loss of generality, assume f is the outer face of G. Let T be any spanning tree T of G, let e be any edge of T, and let S be either component of T \ e. An easy inductive proof implies that the subtree S contains either no vertices of f, every vertex of f, or a contiguous interval of vertices of f.
o
00 csr csr
u
a
Figure 3. On a higher-genus surface, the boundary between the red and blue dual faces may consist of multiple cycles.
Consider an arbitrary dart x ^y. Let A be the set of vertices of f whose shortest-path trees contain x ^y. Equivalently, A is the set of vertices of f that lie in the subtree rooted at x in the shortest path tree rooted at y. Thus, either A is empty, A is the complete set of vertices in f, or A is a contiguous interval of vertices of d f. In the first case, x^y is never in the shortest path tree; in the second case, x^y is always in the shortest path tree; in the third case, x^y pivots in exactly once and pivots out exactly i-l once.	□
Like Klein [42], we can assume the input graph G graph has bounded degree. This assumption allows us to maintain the primal dynamic tree structure and the predecessor pointers at every node in a persistent data structure [16], so that we can access any version of the shortest-path tree in O(logn) time. (It is not necessary to make the dual forest structure persistent.) The resulting persistent data structure requires O(log n) space per pivot, or O(n log n) space overall. We conclude:
O
Theorem 3.8. Let G be a directed plane graph with n vertices, and let f be any face of G. In O(n log n) time and space, we can construct a data structure that supports the following operations:
•	Given any vertex u on the boundary of f and any other vertex v, return the shortest-path distance from u to v in O(log n) time.
•	Given any vertex u on the boundary off and any other vertex v, return the shortest path from u
to v in O(log n + k) time, where k is the number of edges in the path. &
4 Algorithm for Higher-Genus Graphs
Our algorithm for planar graphs does not immediately extend to graphs of higher genus, primarily because the complement of a spanning tree is no longer a cotree, and therefore the active darts can have much more complex structure than a single dual path. Even when the red and blue subtrees are separated by a single dual cycle at one value of A, a single pivot can split the red-blue boundary into multiple dual cycles; see Figure 3. Also, the analysis of the planar algorithm (implicitly) relies on the ^ Jordan Curve Theorem, which does not hold on surfaces of higher genus.
We first restrict our attention to orientable surfaces. In Section 4.4 we show how to reduce the case of non-orientable surfaces to orientable ones.
Jh
CD
4.1
Maintaining a Grove
Let G be a cellularly embedded graph on an orientable surface S of genus g > 0. Without loss of generality, we assume that G is a triangulation, so that every vertex of the dual graph G* has degree 3. Let F be a spanning forest of G with k components (that is, a spanning tree of G minus k — 1 edges) for some constant k. (In our application, we always have 1 < k < 3.) Euler's formula implies that the complementary dual subgraph X = (G \ F)* is a tree plus 2g + k — 1 extra edges. Following Erickson
and Har-Peled [22], we refer to X as a cut graph; removing X cuts the underlying surface £ into k O topological disks.
Our parametric shortest-path algorithm requires us to quickly identify active darts in this cut graph, and to maintain it as edges are inserted and deleted from F. To support these operations quickly, we decompose X into 0(g) edge-disjoint subtrees as follows.
Let X be the subgraph of X obtained by repeatedly removing vertices of degree 1 until no more remain; the subgraph of removed edges is a forest, which we denote H (for 'hair'). Equivalently, a dual edge e* is in X if and only if the endpoints of the primal edge e lie in different trees in F, or if both endpoints are in the same tree, but adding e to that tree creates a non-contractible cycle.
Euler's formula implies that X consists of 6g + 3k — 3 = 0(g) paths n1, n2, n3,..., which meet at 4g + 2k — 2 = 0(g) vertices of degree 3 [22, Lemma 4.2]. We refer to each path ni as a cut path, and each degree-3 vertex a branch point. For each index i, let Ci denote the union of ni with all trees in H that share a vertex with ni. We call each cut path ni the anchor path and its endpoints ai and bi the anchor vertices of the corresponding subtree Ci. We call the set of 0(g) edge-disjoint subtrees
o
IN

£ CO CO
CO
{C1,C2, C3,...} a grove.3
J2>
We maintain the grove by storing the subtrees Ci in the dual forest data structure described in Section 2.3. We maintain three separate copies of each branch point in this data structure, one for each subtree Ci that contains it. We also separately record (the correct copies of) the anchor vertices of each subtree Ci. Our grove data structure supports two restructuring operations:
•	GroveLink(u^v, a, fi): Add edge uv to the cut graph, and set val(u^v) = a and val(v^u) = ¡5.
This operation assumes that u and v are not in the same subtree Ci.
•	GroveCut(uv): Remove edge uv from the cut graph.
To insert an edge uv into X, we first determine the subtrees Ci and Cj that contain u and v, respectively. We then find the vertices a = Junction(u, ai, bi) and b = Junction(v, aj, bj). Next we insert the edge into the dynamic forest by calling Link(u^v, a, ¡5), which merges the two subtrees Ci and Cj into a single subtree C. We split C into five smaller subtrees by splitting a and b into three copies, each carrying one outgoing edge, using a constant number of Cut and Link operations. Finally, we store the anchor vertices of each of the five new subtrees; in particular a and b are the anchor vertices for the subtree containing uv. See Figure 4. The entire procedure takes 0(log n) amortized time.
To remove the edge uv, we follow the insertion procedure in reverse. We begin by determining which tree Ci that contains uv. We then merge the three copies of the anchors ai and bi into single vertices, thereby merging five trees into a single tree C. We remove the edge from the dynamic forest by calling Cut(uv), splitting C into two subtrees, one containing u and the other containing v. Finally, we update the anchor vertices of these two subtrees. Again, the entire procedure takes 0(log n) amortized time.
^ 4.2 Pivoting Quickly
Now we describe how to efficiently move the source of a shortest-path tree in G along a single edge uv, using the parametric shortest path approach described in Section 3.1. We cannot apply the planar algorithm directly, because the set of active darts is no longer dual to a directed path in G*. However, the grove structure we just described lets us quickly identify a superset of the active darts.
Suppose su and sv are both edges in the current shortest-path tree TA. Let R and B be the induced red and blue subtrees of TA, and let X = (G \ (R U B))*. We maintain the cut graph X in a grove, as described above. We also associate a color with each subtree Ci in the grove according to the colors of
a
CD	3The Oxford English Dictionary defines grove as "A small wood; a group of trees affording shade or forming avenues or
walks, occurring naturally or planted for a special purpose."

o
b
u
CD
W
-bcf
\>Cf
W
pa
pa
pa
pa
O IN
0
o
1
CO ^
CO CO
Figure 4. Maintaining a grove. Left to right: Inserting an edge. Right to left: Deleting an edge.
m
CD
$H
CD
m
u
a
CD U
FindNextPivot: if pred(v) = s then return s^v if pred(u) = s then return Null
minStep ^ 1 — A nextPivot ^ Null
for each subtree Q if C[ is green
(xi^yi)* ^ MinPath^, bi) A ^ GetDartValue((x^ if A/w (uv) < minStep nextPivot ^ (xt ^yt) minStep ^ A/w (uv)
return nextPivot

Pivot( x ^ y): A ^ GetDartValue((x^y)*) A ^ A + A/w (uv) Ab ^ Aw(u^v)/w(uv) Ar ^ Aw(v^u)/w(uv)
if pred(u) = s then AddSubtree(Ar, u) if pred(v) = s then AddSubtree(—Ab, v)
for each subtree Ci if Ci is green
AddPath(—A, ai, bi)
z ^ pred(y); pred(y) ^ x
Cut(z, y); GroveLink((z^ y )*,0, w (yz))
Link(x,y); GROVECuT((xy)*)
Figure 5. Naive algorithms to find and execute the next pivot when G has positive genus.
primal edges that cross the anchor path ni. If the crossing edges have two red endpoints, we color Ci red; if the crossing edges have two blue endpoints, we color Ci blue; if the crossing edges have one red endpoint and one blue endpoint, we color Ci green. Observe that the green edges of G are precisely the edges that cross green anchor paths.
We direct the green anchor paths so that they contain the duals of active darts; that is, for any dart x ^y where x is blue and y is red, the dual dart (x^y )* lies on some directed green anchor path. For each directed green anchor path ni, let ai denote its start vertex and bi its end vertex. The following
lemma is now almost immediate.
Lemma 4.1. We can perform the next pivot into TA in 0(g log n) amortized time.
Proof: The modified algorithms to find the next edge to become tense and pivot it into the shortest-path tree are shown in Figure 5. There are only a few differences from the planar algorithms. First, we must examine every directed green anchor path to find the next edge to pivot. Second, we must call AddPath on every green anchor path to update the slacks of the green edges. Finally, we must call GroveCut and GroveLink to repair the grove data structure. These algorithms perform 0(g) dynamic forest operations, plus constant additional work, so their amortized running time is 0(g log n).	□
o
IN
With a little more effort, we can improve the running time slightly. In addition to our other data structures, we maintain a priority queue of the green subtrees in the grove, where the priority of any subtree Ci is the minimum slack among all darts whose duals lie in ni. Because the grove never contains ~ more than 0(g) subtrees, each priority queue operation takes 0(logg) time.
To find the next dart to pivot, instead of looping over every subtree in the grove, we simply extract the minimum element from the priority queue. Within each call to GroveCut or GroveLink, we perform a constant number of priority queue operations as subtrees are created and destroyed.
Finally, instead of calling AddPath once for each green subtree in Pivot, we maintain a global offset for each green subtree in its priority queue record. This allows us to call AddPath just once on each green subtree, just before it is removed from the priority queue—when the subtree changes color, when the subtree is destroyed by GroveCut or GroveLink, or when the moving source point s reaches v. Thus, crudely, the number of calls to AddPath is less than the number of priority queue operations.
If we ignore priority queue operations and calls to AddPath, the remainder of FindNextPivot and Pivot requires 0(log n) amortized time. Thus, to complete our analysis, we need only an upper bound on the number of priority queue operations.
A single pivot can change the colors of several subtrees in the grove. When a subtree changes from red to green, we must insert it into the priority queue; when it changes from red to blue or from green to blue, we must delete it. To detect these color changes quickly, we separately maintain a reduced cut graph X, an abstract graph with a vertex for every branch point of X and an edge ?i for every cut path ni, with a cellular embedding on E consistent with the embedding of X. Each face of the reduced cut graph corresponds to a component of the primal forest F. We can easily update the reduced cut ^ graph in 0(1) time within each call to GroveCut or GroveLink.
Just after removing the old edge z — y from the shortest-path tree TX and adding its dual to the grove, color the subtree rooted at y purple. Now the reduced cut graph X has exactly three faces: one red, one blue, and one purple. Edges 'ei on the boundary of the purple face correspond to subtrees Ci that are pQ changing color; specifically:
•	If ei also bounds the red face, the corresponding subtree Ci is changing from red to green; we insert it into the priority queue.
£
•	If ei also bounds the blue face, the corresponding subtree Ci is changing from green to blue; we delete it from the priority queue.
•	If ?i has the purple face on both sides, the corresponding subtree Ci is changing directly from red to blue; we ignore it. (However, for purposes of analysis, we pretend to execute two priority queue operations.)
During a single pivot, the time to update X and traverse the purple face is less than the time spent i-H maintaining the priority queue, so we can ignore it.
Now recall that the grove always contains 0(g) subtrees. Let nred and nMue denote the number of red and blue subtrees, respectively. The number of priority queue operations for a single pivot is a constant (less than 20) plus the decrease in nred plus the increase in nMue. Over the entire parametric shortest path ^ algorithm, the total decrease in nred and the total increase in nred is at most 0(g).
Thus, if moving the source point across uv requires k pivots, the total number of priority queue operations is 0(g+k). Because we perform at most one call to AddPath for each priority queue operation, the number of calls to AddPath is also at most 0(g + k). We conclude:
Theorem 4.2. Let G be a directed graph with n vertices, cellularly embedded on an orientable surface of genus g, and let s be any vertex in G. After 0(n log n) preprocessing time, we can maintain a representation of the shortest-path tree Ts that supports the following operations:
•	Given any vertex v, return the shortest-path distance from s to v in O(log n) time.
•	Given any vertex v, return the last edge on the shortest path from s to v in O(1) time.
CM	• For any edge sv, change the source vertex from s to v in O((g + k) log n) amortized time, where k
is the number of edges in Ts \ Tv.
Again, nearly identical algorithms update the shortest-path tree after changing the weight of any single edge, or deleting an edge, or inserting an edge (provided the graph remains embedded), in O((g + k) log n) amortized time, where k is the number of edges added to or deleted from the shortest-path tree.
&
CD
pL| 4.3 Moving Around a Face
We next bound the running time of our algorithm as the source vertex moves all the way around the boundary of a given face f. We first show a bound on the number of times that an edge can enter or leave the shortest path tree during the entire traversal.
o
s
CO CO
Lemma 4.3. As the source point s moves around the boundary off, each dart of G pivots into (or out of) the shortest path tree rooted at s at most O(g ) times.
Proof: Fix an arbitrary dart x^y. Let A be the set of points s (not just vertices) on the boundary of f such that the shortest path tree rooted at s contains the dart x^y. A is the union of a set of disjoint, maximal paths A1,..., Ar on the boundary of f. Dart x^y enters the shortest path tree exactly r times, CM once at the initial endpoint of each interval Ai.
Fix a point vi in each component Ai, and let pi be the shortest path from vi to y. By construction, pi uses the dart x^y, and for all i = j, paths pi and pj do not cross.
Let S/f be the surface obtained by contracting the face f to a point. Suppose pi and pj are homotopic in S/f. Then in S, there is a subwalk f1 of f that together with pi and pj bound a disk (and thus a planar graph). This implies that the shortest path to y from every vertex of f1 must contain the dart x ^y, because of Lemma 3.7. It follows that vi and vj lie in the same connected component of A, which is only possible if i and j must be equal. We conclude that the paths p1, p2,...,pr are pairwise non-homotopic.
Finally, a double-counting argument using Euler's formula implies that the maximum possible number of pairwise non-crossing, non-homotopic paths in S/f is O(g) [11, Lemma 2.1]. Thus, r = O(g), and the proof is complete.	□
Recall from Theorem 4.2 that the time to move the shortest path tree across a single edge is O((g + k) log n), where k is the number of pivots. The previous lemma implies that the total number of pivots is O(gn), and the total number of edges in f is trivially O(n). Thus, the total running time to move the source of the shortest path tree along the boundary of a face is O(gn log n).
Finally, in order to make our primal data structure persistent, we require the graph to have bounded degree; however, our grove data structure requires the graph to be a triangulation. We can escape this seeming contradiction as follows. Given an arbitrary embedded graph G, we first replace every high-degree vertex with a small tree of degree-3 vertices, each consisting of darts with infinitesimal weight, and then we triangulate each face with edges whose darts have large enough weight. The edges whose darts have large weight never participate in any shortest path, so the maximum degree of any node in the shortest-path path tree is always at most 3, and so the primal tree structure can be made persistent efficiently. We conclude:
Theorem 4.4. Let G be an directed graph with n vertices, cellularly embedded in an orientable surface of genus g, and let f be any face of G. In O( gn log n) time and space, we can construct a data structure CM that supports the following operations:
•	Given any vertex u on the boundary of f and any other vertex v, return the shortest-path distance from u to v in O(log n) time.
•	Given any vertex u on the boundary off and any other vertex v, return the shortest path from u to v in O(log n + k) time, where k is the number of edges in the path.
$
4.4 Non-Orientable Surfaces
We can extend Theorem 4.4 to non-orientable surfaces working in the orientable double cover of the surface, which is an orientable covering space of (Our construction is essentially the same as used ^ in [9, 10], but is presented here for completeness.)
Recall that a cellular graph embedding of a graph G on a non-orientable surface consists of a rotation system, encoding the cyclic sequence of outgoing darts from each vertex, and a signature, consisting of a bit i(e) for each edge e. The signature indicates whether the cyclic sequences at its endpoints are in the "same" direction or the "opposite" direction.
The orientable double cover D of G is an embedded graph constructed as follows. For each vertex v in the original graph, create two vertices (v, 0) and (v, 1) in D. For each dart u^v in the original graph, create two darts (u^v,0) = (u,0)^(v,i(uv)) and (u^v, 1) = (u, 1)^(v, 1 — i(uv)) in D. The rotation system at (v, 0) and (v, 1) is just a copy of the rotation system of v. That is, if nG is the original rotation system and nD the rotation system in D, then for any dart u^v of G it holds nD(u^v, j) = (nG(u^v), j). Finally, darts (u^v, 0) and (u^v, 1) have the same dart weight and the same signature bit as u^v. This cover is orientable because, for any cycle, the sum of the signatures of its edges is 0 modulo 2. Note that this cover D has twice as many edges as G and can be constructed in linear time.
Any walk (u0, j0)(u1, j1)(u2, j2),..., (ut, jt) in D naturally projects to the walk u0u1u2... ut in G. A lift of a walk u0u1u2... ut in G is a walk (u0, j0)(u1, j1)(u2, j2),..., (ut, jt) in D. That is, the projection of a lift recovers the original walk. A lift is uniquely determined by the value j0. Indeed, since (ut, jt)(ut+1, jt+1) must be an edge of D, we have
ji+1 = jt + i(utut+1) = j + i(ut'ut+1) (modulo 2).
fa
This implies that a shortest path from u to v in G corresponds to either the shortest path from (u, j) to (v, 0) or the shortest path from (u, j) to (v, 1), where j e {0,1} is arbitrary. Therefore, the distance in G from u to v is the minimum between the distance from (u, j) to (v, 0) and the distance from (u, j) to
It is easy to see that a cycle in D is a facial cycle of D if and only it projects to a facial cycle of G. It follows that D has twice as many faces as G. Euler's formula then implies that the genus of D is g — 1.
We can now extend Theorem 4.4 to non-orientable surfaces. Given the graph G and a face f, we construct the orientable double cover D, choose one of the lifts f' of f in the double cover, and store the data structure of Theorem 4.4 for D and f'. This construction takes O(gn log n) time because D has size O(n) and smaller genus. Whenever we want to compute a distance in G from a vertex u, on the boundary of f, to a vertex v, we take the copy (u, j) of s on the boundary of f', query for the distances in D from (u, j) to (v, 0) and from (u, j) to (v, 1), and return the smallest. This takes O(log n) time. The shortest path from s to v can also be recovered using the projection of the shortest path in D from (u, j) p to (v, 0) or (v, 1), whichever is closer. We summarize:
CD
^h Corollary 4.5. Theorem 4.4 also holds for non-orientable surfaces.
5 Computing Shortest Non-Separating and Non-Contractible Cycles
O
Let E be a combinatorial surface with complexity n and genus g; this surface may or may not be orientable. In this section, we describe algorithms to find the shortest non-separating and shortest non-contractible cycles in E. Our use of the technique for maintaining shortest-path trees is condensed in the following lemma.

S CO CO
Lemma 5.1. Let a be an arbitrary simple cycle or arc in T. A shortest cycle crossing a exactly once can be obtained in O(gn log n) time.
Proof: Consider the surface obtained by cutting E along a: each vertex v in a gives rise to two vertices v' and v", and two boundary arcs or cycles a' and a". Let E' be the surface obtained by gluing disks to the boundary components that contain a' and a". (If a is an arc or a 1-sided cycle, then a' and a" can be contained in a single boundary.) A cycle in E that crosses a once at a point v becomes a path in E' between v' and v". Thus, a shortest cycle that crosses a once at v is a shortest path that connects v' to v" in E', and vice versa. All the points v' with v e a belong to a face of E'. Thus, Theorem 4.4 implies that we can find a closest pair (v0, v0') in 0(gn log n) time. Computing the shortest path from v0 to v0 gives the desired path.	□
For any simple arc or cycle a, let Cross(a) denote the set of cycles that cross a exactly once. If a is separating, then Cross(a) is empty, because every cycle crosses a an even number of times. Also, every cycle in Cross(a) is non-contractible, because contractible cycles are also separating, and therefore any O cycle must cross them an even number of times.
i
5.1 Shortest Non-Separating Cycle
CO
2Consider a surface E. It suffices to consider surfaces without boundary, because any shortest non-separating cycle in E is also non-separating in the surface obtained by attaching disks to the boundaries.
Cabello and Mohar [10] describe how to construct in 0(gn log n) time a set S of 0(g) simple cycle such that the shortest cycle in [J£eS Cross(i) is a shortest non-separating cycle. This set is constructed by fixing a shortest path tree Tx from any vertex x e G, fixing a tree-cotree decomposition (Tx, Cx, Lx), and then setting S to be the set of cycles formed by adding each of the edges e e Lx to Tx. Cabello and Mohar use Z2 homology and the fact that the cycles are formed from 2 shortest paths to prove that the shortest non-separating cycle must cross some cycle of S exactly once [10].
Once we have the set S, we compute the shortest non-separating cycle by applying Lemma 5.1 once for each simple cycle in S, and taking the globally shortest cycle.
Theorem 5.2. Let T be an surface, orientable or not, possibly with boundary, of complexity n and genus tl). g .We can find a shortest non-separating cycle in T in O( g2 n log n) time.
CD
5.2 Shortest Non-Contractible Cycle
The main technique for non-contractible cycles is to find a curve that intersects a shortest non-contractible cycle at most once and whose removal decreases either the genus or the number of boundaries of E. Our main tool to prove that such a curve exists is the following exchange argument.
J-i &
Lemma 5.3. Let E be a combinatorial surface and let tx be a shortest non-contractible loop with given basepoint x e E. There is a shortest non-contractible cycle in E that crosses Ix at most once.
Proof: Let C be any non-contractible cycle that crosses I x at least twice, at points y and z. Let y1 and y2 be the two subpaths of C from y to z, and let [1 and [2 be the subpaths of Ix from y to z so that [1 contains x. To simplify notation, we do not differentiate between a path and its reverse. We consider two cases, and in each case find a non-contractible cycle C that is no longer than C and crosses lx fewer times than C. This implies that some shortest non-contractible cycle crosses lx at most once.
First, suppose [2 ~ y1; the case [2 ~ y2 is symmetric. The loop [1 ■ y1 passes through x, and it is non-contractible because ([ ■ y1) ~ ([ ■ [2) = lx. We then have |[2| < |y1| because IIx| < |^1| + |y1|. The cycle C = y2 ■ [32 is non-contractible because (y2 ■ [2) ~ (y2 ■ y1) = C. The cycle C also crosses lx at least two fewer times than C, and |C| = |y2| + |[2| < |y2| + Ir1| < |C|.
Now suppose that [2 is not homotopic to y1 or y2. In this case, the cycles [2 ■ y1 and [2 ■ y2 are non-contractible. The cycle [1 ■ y1 or the cycle [1 ■ y2 is non-contractible (perhaps both); otherwise Y1 ~ [1 ~ Y2, which would imply that C = y1 ■ y2 is contractible. Let us suppose that [1 ■ y1 is non-contractible; the other case is symmetric. Since [1 ■ y1 is a non-contractible loop through x, we have |[1| + |[2| = |^x| < |[1| + |Y11, and so |[21 < |y1|. The cycle C = [2 ■ y2 is non-contractible because [2 * Y2. Cycle C also crosses Ix two fewer times than C, and |C| = |[2| + ^^ < |y1| + |y21 = |C|. □
o
IN
The following lemma discusses what happens with simple non-contractible cycles when pasting a disk into a boundary of the surface. It should be noted that any shortest non-contractible cycle is always simple.
Lemma 5.4. Let E be a surface with boundary and let 5 be one of its boundary components. Let S' be the surface obtained by pasting a disk to 5. A non-contractible simple cycle in E is either non-contractible
in E' or homotopic to 5 in E.
Proof: Consider a non-contractible simple cycle C in E. Let D5 be the disk that is attached to E to obtain E'. If C is contractible in E', then C bounds a disk DC in E'. The disk DC must contain D5, because otherwise, C would also bound a disk in E, implying that C is contractible in E. DC \ D5 is an annulus in E with boundary cycles C and 5. It follows that C and 5 are homotopic in E.	□
£ CO
We also have the following results regarding arcs in a surface with boundary.
CO
HH
Lemma 5.5. Let E be a surface with boundary, let 5 be one of its boundary cycles, and let a be a shortest non-contractible arc with endpoints in 5. There is a shortest non-contractible cycle in E that is either homotopic to 5 or that crosses a at most once.
Proof: Let C be a shortest non-contractible cycle in E. Assume C * 5, since otherwise the proof is complete. Lemma 5.4 implies that C is a shortest non-contractible cycle in E', the surface obtained by pasting a disk D at 5. In the surface E', place a new vertex p in D and connect it through edges with weight L to each vertex of 5. Consider the loop I with basepoint p that follows the edge p a(0), the arc a, and the edge a(1)p. If we choose L large enough, I is a shortest non-contractible loop in E' through p, so Lemma 5.3(a) implies that a shortest non-contractible cycle C' in E' crosses I at most once. We must have |C= |C |, and if L is large enough, C' must avoid the disk D. It follows that C' is a shortest non-contractible cycle in E that crosses a at most once.	□
Lemma 5.6. Let E be a surface with at least two boundary components, and let a be a shortest arc connecting two different boundaries of E. There is a shortest non-contractible cycle in E that crosses a at most once.
U
CU
o
IN
Proof: Let C be a shortest non-contractible cycle in E that crosses a the minimum number of times. We claim that C crosses a at most once. Assume for the purpose of contradiction that C crosses a at least twice, and let y and z be two such crossings. Let y1 and y2 be the two subpaths of C from y to z, let a be the subpath of a from y to z. Since a is a shortest arc connecting the two specified boundaries, we have |a| < |y1| and |a| < |y2|. If a * y1, then we have a contradiction: the cycle a ■ y1 is non-contractible, crosses a fewer times than C does, and |a| + |y1 | < |y2| + |y1| = |C|. Similarly, we must have a ~ y2. ^ But then y1 ~ y2, which implies that C is contractible, which is a contradiction.	□
The next lemma summarizes the algorithmic tools that we will use.
(D Lemma 5.7. Let E be a surface of complexity n.
(a)	Given a basepoint x, we can find a shortest non-contractible loop with basepoint x in 0(n log n) time. This loop has multiplicity 2.
(b)	Given a boundary 5, we can find in 0(n log n) time a shortest cycle homotopic to 5.
(c)	Given a boundary 5, we can find in 0(n log n) time a shortest non-contractible arc with endpoints in 5. This arc has multiplicity at most 2 and is edge-disjoint from 5.
(d)	If E has exactly two boundaries, we can find in 0(n log n) time a shortest arc with endpoints in both boundaries. This arc has multiplicity 1 and is edge-disjoint from the boundary of E.
Proof: (a) See Erickson and Har-Peled [22, Lemma 5.2].
(b)	See Cabello et al [9].
O
(c)	Contract 5 to a point p and construct a shortest non-contractible loop with basepoint p as in part (a). This is the desired arc in E.
C^
(d)	Select boundaries 5 and 5' of E, contract them to points p and p', and construct in 0(n log n) time the shortest path from p to p'.
C^	□
Lemma 5.8. Let E be a combinatorial surface with complexity n, genus g, and b boundaries. Let E' be the surface obtained by pasting a disk to each boundary of E. We can find a shortest non-contractible cycle in E in 0(bn log n) time plus the time used to find a shortest non-contractible cycle in E'.
Proof: Number the boundaries 51,52,..., 5b, and set E0 = E. For i > 1, let Ei be the surface obtained from Ei-1 by pasting a disk to 5i. In particular, Eb = E'. For each i, let Ci be a shortest cycle homotopic ^ to 5i in E^ 1. We can compute each cycle Ci in 0(n log n) time.
Lemma 5.4 implies that a shortest non-contractible cycle in E^ 1 is either Ci or a shortest non-contractible cycle in E^ 1. Thus, the shortest non-contractible cycle in E is either the shortest among C1,..., Cb or a shortest non-contractible cycle in E'.	□
find a shortest non-contractible cycle of E in 0((g2 + b)n log n) time.
U
Theorem 5.9. Let E be a combinatorial surface with complexity n, genus g, and b boundaries. We can
Proof: We apply Lemma 5.8 to E. We spend 0(bn log n) time, and have reduced the problem to find a shortest non-contractible cycle in a surface E' of genus g and no boundary. We next give an iterative algorithm that reduces either the genus or the number of boundaries of the subproblems in each iteration. Through the algorithm we use a variable minCycle to store the shortest non-contractible cycle found so far. In each iteration we find one new non-contractible cycle y whose length is compared against
U
CU
u
the length of minCycle, and minCycle is updated if needed. The algorithm stops when each remaining
O component is a topological disk.
CM	We distinguish three cases. S' denotes the surface in the subproblem. Through the algorithm the
surface S' has genus at most g and each component of S' has at most two boundaries.
CM
(a)	If S' is a surface without boundary, we choose a point x e S' and find a shortest non-contractible loop lx through x (Lemma 5.7(a)). Lemma 5.3 implies that there is a shortest non-contractible cycle in S' crossing lx at most once. We compute the shortest cycle y in Cross(lx) using Lemma 5.1 and update minCycle with y, if it is shorter. Then we set S' = S' \ lx. Note that if lx is separating, then S' has two connected components and Cross(lx) = 0. If S' has complexity m, we spend O(gmlog m) time in this iteration.
[V
(b)	If S' has a component with non-zero genus and exactly one boundary 5, we find a shortest non-contractible arc a with endpoints in 5 (Lemma 5.7(c)). Lemma 5.5 implies that there is a shortest non-contractible cycle in S' that either crosses a at most once or is homotopic to 5. We compute the shortest cycle in Cross(a) and the shortest cycle homotopic to 5 in O(gn log n) time (Lemmas 5.1 and 5.7(b)). The shortest of these two cycles is compared against minCycle, and minCycle is updated if necessary. We then set S' = S' \ a. If S' has complexity m, we spend O(gm log m) time in this iteration.
(c)	If S' has one component with exactly two boundaries, we find a shortest arc a connecting them (Lemma 5.7(d)). Lemma 5.6 implies that there is a shortest non-contractible cycle l in S' crossing a at most once. We compute the shortest cycle y in Cross(a) using Lemma 5.1, and update minCycle with y, if it is shorter. Then we replace S' with S' \ a. If S' has complexity m, we spend O(gm log m) time in this iteration.
This finishes the description of the algorithm. The algorithm has O(g) iterations; starting with no boundary, we iterate in case (a) once and then cases (b) or (c) at most 2g times. The arcs and loops that are used to cut, which are obtained from Lemma 5.7, have multiplicity at most two and are edge-disjoint from the boundary. Thus any subsurface S' considered in a subproblem has at most four copies of an edge of S. This means that any surface S' has complexity O(n) and in each iteration we spend
CO
O(gn log n) time.	□
CO
CO CD
Jh
CD CO
u
a
CD U

References
[1]	Pankaj K. Agarwal, D. Eppstein, L. J. Guibas, and M. Henzinger. Parametric and kinetic minimum spanning trees. In Proc. 39th Ann. IEEE Sympos. Found. Comput. Sci., pages 596-605, 1998.
[2]	Julian Basch, Leonidas J. Guibas, and John Hershberger. Data structures for mobile data. J. Algorithms, 31(1):1-28, 1999.
[3]	MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Daniel Marx. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM, 58:21, 2011.
[4]	Glencora Borradaile. Exploiting Planarity for Network Flow and Connectivity Problems. PhD thesis, Brown University, May 2008.
[5]	Glencora Borradaile, Erik D. Demaine, and Siamak Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. In Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., pages 171-182. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009.
[6]	Glencora Borradaile and Philip Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM, 56(2): 9:1-30, 2009.
[7]	Sergio Cabello. Many distances in planar graphs. Algorithmica, 62(1-2):361-381, 2012.
[8]	Sergio Cabello and Erin W. Chambers. Multiple source shortest paths in a genus g graph. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 89-97, 2007.
[9]	Sergio Cabello, Matt DeVos, Jeff Erickson, and Bojan Mohar. Finding one tight cycle. ACM Transactions on Algorithms, 6(4), 2010.
[10]	Sergio Cabello and Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete Comput. Geom., 37(2):213-235, 2007.
[11]	Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, and Kim Whittlesey. Splitting (complicated) surfaces is hard. Comput. Geom. Theory Appl., 41(1-2):94-110, 2008.
[12]	Jianer Chen, Saroja I? Kanchi, and Arkady Kanevsky. A note on approximating graph genus. Inform. Proc. Lett., 61(6):317-322, 1997.
[13]	Éric Colin de Verdière. Raccourcissement de courbes et décomposition de surfaces [Shortening of Curves and Decomposition of Surfaces]. PhD thesis, University of Paris 7, December 2003.
[14]	Éric Colin de Verdière and Jeff Erickson. Tightening non-simple paths and cycles on surfaces. SIAM J. Comput., 39(8):3784-3813, 2010.
[15]	Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.
[16]	James R. Driscoll, Niel Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. J. Comput. System Sci., 38(1):86-123, 1989.
[17]	Mark J. Eisner and Dennis G. Severance. Mathematical techniques for efficient record segmentation in large shared databases. J. ACM, 23(4):619-635, 1976.

[18]	David Eppstein. Dynamic generators of topologically embedded graphs. In Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 599-608, 2003.
[19]	David Eppstein and Kevin A. Wortman. Optimal embedding into star metrics. In Proc. 11th Workshop on Algorithms and Data Structures, volume 5664 of Lecture Notes in Comput. Sci., pages 290-301, 2009.
[20]	Jeff Erickson. Parametric shortest paths and maximum flows in planar graphs. In Proc. 21st Ann. ACM-SIAM Symp. Discrete Algorithms, pages 794-804, 2010.
[21]	Jeff Erickson. Shortest non-trivial cycles in directed surface graphs. In Proc. 27th Ann. Symp. Comput. Geom., pages 236-243, 2011.
[22]	Jeff Erickson and Sariel Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom., 31:37-59, 2004.
[23]	Jeff Erickson and Amir Nayyeri. Computing replacement paths in surface graphs. In Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1347-1354, 2011.
[24]	Jeff Erickson and Amir Nayyeri. Minimum cuts and shortest non-separating cycles via homology covers. In Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1166-1176, 2011.
[25]	Jeff Erickson and Pratik Worah. Computing the shortest essential cycle. Discrete Comput. Geom., 44(4):912-930, 2010.
[26]	Lester R. Ford. Network flow theory. Paper P-923, The RAND Corporation, Santa Monica, California, August 14, 1956. Cited in [48].
[27]	Kyle Fox. Faster shortest non-contractible cycles in directed surface graphs. CoRR, abs/1111.6990, 2011.
[28]	Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs with applications. SIAM J. Comput., 16(6):1004-1004, 1987.
[29]	M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34:596-615, 1987.
[30]	S. Gass and T. Saaty. The computational algorithm for the parametric objective function. Naval Research Logistics Quarterly, 2:39-45, 1955. Cited in [41].
[31]	Andrew V Goldberg, Michael D. Grigoriadis, and Robert E. Tarjan. Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math. Program., 50:277-290, 1991.
[32]	Andrew V Goldberg and Robert E. Tarjan. Finding minimum-cost circulations by cancalling negative cycles. J. ACM, 36(4):873-886, 1989.
[33]	Leonidas J. Guibas. Kinetic data structures — a state of the art report. In P K. Agarwal, L. E. Kavraki, and M. Mason, editors, Proc. Workshop Algorithmic Found. Robot., pages 191-209. A. K. Peters, Wellesley, MA, 1998.
[34]	Dan Gusfield. Parametric combinatorial computing and a problem of program module distribution. J. ACM, 30(3):551-563, 1983.

[35]	Monika R. Henzinger and valerie King. Randomized fully dynamic graph algorithms with polylog-arithmic time per operation. J. ACM, 46(4):502-516, 1999.
[36]	Monika R. Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci., 55(1):3-23, 1997.
[37]	Ken ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In Proc. 52nd Ann. IEEE Sympos. Found. Comput. Sci., pages 160-169, 2011.
[38]	Richard M. Karp and James B. Orlin. Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math., 3:37-45, 1981.
[39]	Ken-Ichi Kawarabayashi, Philip N. Klein, and Christian Sommer. Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In Proc. 38th Int. Colloquim Conf. on Automata, Languages and Programming - Volume Part I, volume 6755 of Lecture Notes in Comput. Sci., pages 135-146. Springer-verlag, 2011.
[40]	Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In Proc. 49th IEEE Symp. Found. Comput. Sci., pages 771-780, 2008.
[41]	victor Klee and Peter Kleinschmidt. Geometry of the Gass-Saaty parametric cost LP algorithm. Discrete Comput. Geom., 5(1):13-26, 1990.
[42]	Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 146-155, 2005.
[43]	Martin Kutz. Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In Proc. 22nd Ann. Symp. Computational Geometry, pages 430-438, 2006.
[44]	Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs. SIAM J. Applied Math., 36(2):177-189, 1979.
[45]	Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, 2001.
[46]	Ketan Mulmuley, Umesh vazirani, and vijay vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105-113, 1987.
[47]	Jeanette P Schmidt. All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J. Comput., 27(4):972-992, 1998.
[48]	Alexander Schrijver. On the history of combinatorial optimization (till 1960). In K. Aardal, G.L. Nemhauser, and R. Weismantel, editors, Handbook of Discrete 0ptimization, pages 1-68. Elsevier, 2005.
[49]	Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, 1983.
[50]	Robert E. Tarjan. Efficiency of the primal network simplex algorithm for the minimum-cost circulation problem. Math. 0per. Res., 16(2):272-291, 1991.
[51]	Robert E. Tarjan. Dynamic trees via Euler tours, applied to the network simplex algorithm. Mathematical Programming: Series A and B, 78:169-177, 1997.
[52]	Robert E. Tarjan and Renato F. Werneck. Self-adjusting top trees. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 813-822, 2005.
C^
[53]	Siamak Tazari and Matthias Müller-Hannemann. Shortest paths in linear time on minor-closed graph classes, with an application to steiner tree approximation. Discrete Applied Mathematics, 157(4):673-684, 2009.
[54]	Carsten Thomassen. The graph genus problem is NP-complete. J. Algorithms, 10(4):568-576, 1989.
Jh
[55]	Carsten Thomassen. Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory Ser. B, 48(2):155-177, 1990.
[56]	Karl Georg Christian von Staudt. Geometrie der Lage. Verlag von Bauer and Rapse (Julius Merz), Nürnberg, 1847.
IN
0 ö
o
1
CO
£ CO CO
m
CD
$H
CD
m
u
a
CD U
[57] Neal E. Young, Robert E. Tarjan, and James B. Orlin. Faster parametric shortest path and minimum balance algorithms. Networks, 21(2):205-221, 1991.