IMFM
Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA
Preprint series Vol. 48 (2010), 1125
ISSN 2232-2094
ALGORITHMS FOR THE EDGE-WIDTH OF AN EMBEDDED GRAPH
Sergio Cabello Eric Colin de Verdiere Francis Lazarus
Ljubljana, August 06, 2010
Algorithms for the Edge-Width of an Embedded Graph O	,
Sergio Cabello^ Eric Colin de Verdiere* Francis Lazarus§
CO
July 29, 2010
&
10

u
CD CO
u
a
CD U
Abstract
Let G be an unweighted graph of complexity n cellularly embedded in a surface (orientable or not) of genus g. We describe improved algorithms to compute (the length of) a shortest non-contractible and a shortest non-separating cycle of G.
If k is an integer, we can compute such a non-trivial cycle with length at most k in O(gnk) time, or correctly report that no such cycle exists. In particular, on a fixed surface, we can test in linear time whether the edge-width or face-width of a graph is bounded from above by a constant. This also implies an output-sensitive algorithm to compute a shortest non-trivial cycle that runs in O(gnk) time, where k is the length of the cycle.
We also give an approximation algorithm for the shortest non-trivial cycle. If a parameter 0 < e < 1 is given, we compute in O(gnje) time a non-trivial cycle whose length is at most 1 + £ times the length of the shortest non-trivial cycle.
Keywords: Topological graph theory, computational topology, edge-width, face-width, surface, embedded graph.
CO
1 Introduction
Let £ be a surface (orientable or not) of genus g with b boundaries. Let G be an (unweighted, undirected) graph embedded on £ of complexity n (this is the total number of vertices and edges CO of G), where all the faces of G are disks. In this paper, we are interested in the edge-width and face-width of G, which roughly measure how G "locally looks planar". Specifically, the edge-width of G is the minimum number of edges in a non-contractible cycle of G [2, 23]. The face-width of G (also known as representativity) is the minimum number of points in the image of G that are contained in a non-contractible curve on £ [24]. There are also the corresponding concepts of non-separating edge-width and non-separating face-width, where the requirement of being non-contractible is strengthened into being non-separating.
This paper gives improved algorithms to compute these parameters. Before describing our new results in detail, we present some motivations and related works.
*A preliminary version appeared in Proc. ACM Symp. on Computational Geometry, 2010, pp. 147-155. Research partially supported by the Slovenian Research Agency, program P1-0297 and project BI-FR/09-10-PRGTEUS-014, funded by the French Ministry of Foreign and European Affairs.
^Department of Mathematics, IMFM, and Department of Mathematics, FMF, University of Ljubljana, Slovenia. E-mail: sergio. cabello@fmf.uni-lj .si.
^Laboratoire d'informatique, Ecole normale superieure, CNRS, Paris, France. Email: Eric.Colin.de.Verdiere® ens. fr.
§GIPSA-Lab, CNRS, Grenoble, France. E-mail: Francis.Lazarus@gipsa-lab.grenoble-inp.fr.
Topological Graph Theory. Edge-width and face-width were introduced in the field of topological graph theory (see Mohar and Thomassen [22, Chapter 5] for a survey). Graph embeddings with large face-width share many properties with planar graphs; we list a selection of them. Every graph embedded in a surface with sufficiently large face-width or edge-width, that depends on the surface, is 5-choosable and thus 5-colorable [27, 9]. Every graph with large face-width can be made planar by cutting along cycles that are far apart from each other [28]. A given graph is a minor of every graph of face-width k embedded on the same surface, when k is sufficiently large [23]. Finally, for any fixed surface there exists a constant bounding the number of embeddings with face-width at least 3 that any 3-connected graph may have [21, 16], thus extending Whitney's result for planar graphs to arbitrary surfaces.
<
Related Algorithmic Results. The computational aspects of the edge-width and face-width have also been studied. The face-width of G is half the edge-width of the vertex-face incidence graph of G, and similarly for the non-separating edge-width; therefore, the problem boils down to computing a shortest non-trivial cycle on an embedded graph, where non-trivial means either non-contractible or non-separating. Such cycles are the fundamental tool to perform surgery on embedded graphs. The first algorithm, by Thomassen [26], finds a shortest non-trivial cycle in cubic time. In essence, for each vertex of G, the algorithm computes a breadth-first search (BFS) tree T rooted at that vertex, and, for every non-tree edge e, tests whether the cycle formed by T and e is non-trivial; finally, the shortest such cycle is returned. In particular, the shortest non-trivial cycle has no repeated vertex.
Other papers on this topic study the computation of shortest non-trivial cycles in the more general situation of (non-negatively) weighted graphs. Erickson and Har-Peled [11] extend Thomassen's algorithm to this setting and decrease its complexity to O(n2 log n), by interleaving Dijkstra's algorithm with tests for triviality. This is the best current result, and an algorithm with subquadratic
00 running time would give rise to a subquadratic-time algorithm to find the girth of sparse graphs [5]. In the same paper, Erickson and Har-Peled [11, Corollary 5.8] give an O(gn log n)-time algorithm that computes a non-trivial cycle whose length is at most twice the length of the shortest non-trivial cycle.
Efficient algorithms for the case where the genus is small have also been investigated [6, 19].
SThe best known algorithm by Cabello and Chambers [3] computes the shortest non-contractible (resp. non-separating) cycle on an orientable surface in O((g + b)g2nlogn) (resp. O(g3nlogn)). As a consequence, the (possibly non-separating) edge-width and face-width of a graph in a fixed orientable surface can be computed in O(n log n) time. In another paper [4], we also consider the more general scenario of finding shortest non-trivial cycles in directed graphs.
Kawarabayashi and Mohar (private communication) point out that their results in [16] imply that the face-width k of a graph can be computed in 2O(gk)n time, assuming that k > 3. This approach relies on graph minors, and in particular, the relations between the face-width and tree-width of embedded graphs. Their algorithm has an exponential dependency on the genus and the face-width, it uses an unknown (but computable) list of minimal graphs, and it does not extend to the problem of computing the edge-width.
m
The Unweighted Case. It is natural to ask whether the algorithms for the weighted case can be made faster when restricted to unweighted graphs. They all use shortest path trees, computed in O(n log n) time in the weighted case using Dijkstra's algorithm; this step can be speeded up to linear
a
time in the unweighted case, for which BFS trees are shortest path trees. However, the current results are also relying on the minimum cut problem in planar graphs [19] or on dynamic trees [3],
r
o
CSI
CSI CSI
and require an extra logarithmic factor that is independent from the shortest path tree computation. The O(n2 log n) time algorithm by Erickson and Har-Peled [11, Lemma 5.2] immediately gives an O(n2) time algorithm for the non-contractible case, but in the non-separating case, the complexity is still O(n2 log n), because the extra logarithmic factor appears in their recurrence, independently VO of the shortest path tree computation.
o
CSI CSI
£
CO CO
CO CD
■ i-H
u
Our Results. Recall that, in this paper, G is an unweighted graph of complexity n cellularly embedded on a surface £ (orientable or not) of genus g with b boundaries. Our first result is an efficient algorithm to decide whether the edge-width is bounded from above by a given integer:
Theorem 1. Given an integer k, we can decide in O((g + b)nk) time (resp. O(gnk) time) if the edge-width (resp. non-separating edge-width) of G is at most k. If it is the case, we can also obtain ^^ a shortest non-contractible (resp. non-separating) cycle in G.
In particular, on a fixed surface, we can decide in linear time whether the edge-width is bounded from above by a constant.
By running the algorithm of Theorem 1 for exponentially increasing values of k, we obtain an efficient output-sensitive algorithm:
Corollary 2. Let k be the edge-width (resp. non-separating edge-width) of G. We can compute a shortest non-contractible (resp. non-separating) cycle in G in O(gnk) (resp. O((g + b)nk)) time.
We also give an efficient algorithm to compute an approximation of the edge-width; this is an enhancement over the 2-approximation algorithm by Erickson and Har-Peled [11, Corollary 5.8] C^ mentioned above:
Theorem 3. Let e be a parameter such that 0 < e < 1. We can compute a non-contractible (resp. non-separating) cycle in G whose length is at most 1 + e times the length of the shortest such cycle, in O((g + b)n/e) (resp. O(gn/e)) time. In particular, we approximate the (possibly non-separating) edge-width of G up to a factor of e.
Incidentally, we give alternate algorithms to find shortest non-trivial loops (possibly in weighted graphs). Our algorithms are (arguably) simpler to implement than those by Erickson and Har-Peled [11, Lemma 5.2]; some ideas of the proof are inspired from the paper by Erickson and Whittlesey to compute shortest homotopy generators [12]. Compared to Erickson and Har-Peled [11], our algorithms are faster by a logarithmic factor for the non-separating case in unweighted graphs, and have the same asymptotic running-time otherwise:
Theorem 4. We can compute a shortest non-contractible or non-separating loop through a given basepoint in G in O(n) time.
Again, we note that all the results above about the (possibly non-separating) edge-width parameter have immediate counterparts for the (possibly non-separating) face-width, because the vertex-face incidence graph r of G (also called radial graph) is also embedded on £, has the same asymptotic complexity as G, and the face-width of G equals half of the edge-width of r [22, Propo-4J sition 5.5.4]. We also emphasize that all of our algorithms are quite simple and do not require heavy data structures like self-adjusting top trees (needed by Cabello and Chambers [3]).
Our output-sensitive complexity can be combined with combinatorial bounds on the edge-width and face-width that are known. Hutchinson [15] showed that a triangulation with m vertices in an orientable surface without boundary has edge-width 0( \Jmjg log p) if g < m and G(\ogg) if g > m. This result can be extended to non-orientable surfaces, and the same bound applies to the
CO <
face-width of arbitrary embedded graphs [6, Lemma 13 and Theorem 14]. Therefore, our algorithm implies that the edge-width of a triangulation and the face-width of an arbitrary graph in a surface (orientable or not) without boundary can be computed in O(n3/2g1/2 log g) time, provided that ^ g < n. This time bound is subquadratic unless g log2 g = Q(n).
vO
Applications. In topological graph theory there are several results of the following form: for any fixed surface £ there exists a constant c = c(£, n) such that any graph embedded in £ with face-width (or edge-width) at least c has property n. See for example [27, 9, 28, 23, 21], and [22, Chapter 5]. Our results provide a linear-time algorithm to test if the hypotheses of those results are fulfilled.
Getting bounds on the edge-width or the face-width has been explicitly used as subroutine in algorithms that work in linear time on a surface of bounded genus, for computing crossing numbers of graphs [17], for graph isomorphism of graphs that admit polyhedral embeddings [16], and for finding certain induced cycles in embedded graphs [18]. In these papers, the authors use the 2-approximation of the edge-width mentioned above. Using this 2-approximation instead of the real edge-width affects exponentially the running time; however, this is hidden in the O-notation because the authors consider a fixed surface. Using our Theorem 1 instead removes this overhead.
Also, there is a closed formula telling the orientable genus of a graph that can be embedded in the projective plane. Indeed, Fiedler et al. [13] have shown that a graph G that can be embedded in the projective plane with face-width k = 2 has orientable genus |_k/2_|. Our results imply an algorithm to compute the orientable genus g(G) of such graphs in O(g(G)n) time.
The techniques we use here to prove Theorem 4 are also useful in another paper [4], where we obtain efficient algorithms that find shortest non-trivial cycles in a more general setting than previously studied, namely, for directed weighted graphs on surfaces.
C^
Overview of the Techniques. Our algorithm to obtain Theorem 1 consists of two steps: (1) We first compute a set of vertices K such that any non-trivial cycle has to use some vertex of K. (2) For every vertex s in K, we compute the shortest non-trivial cycle passing through s in the graph induced by the vertices at distance at most k/2 from s. The key idea in our approach is to find an efficient way to carry Step (2) simultaneously for several basepoints that are far apart on the surface. This idea, in turn, requires to choose K in Step (1) adequately. This strategy also requires to be able to test in constant time whether a cycle with a special structure is trivial; we introduce a technique for this purpose, which implies Theorem 4, of independent interest.
For the proof of Theorem 3, we start by computing a 2-approximation of the edge-width. Then we proceed as in the previous paragraph, but since we are only interested in an approximately shortest non-trivial cycle, we can discard some vertices of K to speed up the algorithm.
The rest of the paper is organized as follows. After some preliminaries (Section 2), we prove Theorem 4 in Section 3. In Section 4, we introduce two other tools to compute shortest non-trivial loops with given basepoints in "parallel" and to achieve Step (1) above; we also recall the 2-
o
CSI
CSI CSI
u
approximation algorithm. Finally, in Section 5, we prove the main results: Theorem 1, Corollary 2, eand Theorem 3.
u
a
2 Background and Terminology
2.1 Graph Theory
All the considered graphs may have loop edges and multiple edges. We sometimes denote by xy an edge with endpoints x and y: even if this notation is ambiguous in presence of multiple edges, it
will always be clear from the context which edge is considered. A walk in a graph is a sequence of edges e\,... ,em with the property that the target of e» is the source of ei+1, for i = 1,... ,m — 1; such a walk is closed if the target of em is the source of ei. A path is a walk without repeated vertices; a cycle is a closed walk without repeated vertices. A loop with basepoint s is a closed walk with a distinguished occurrence of vertex s. We denote by V(G) and E(G) the set of vertices and edges of a graph G, respectively. For a subset X C V(G), we use G[X] to denote the subgraph of G induced by X. For an edge e of G, we denote by G — e the graph G without that edge.
Suppose G is connected; consider a spanning tree T of G. For any vertex s and any edge uv of G, we denote by t(T, s, uv) the loop consisting of the path in T from s to u, the edge uv, and the path in T from v to s. We also denote by t(T, uv) the closed walk consisting of the edge uv and the path in T between u and v. Note that t(T, uv) is a cycle, if uv is not in T.
m <
lO CSI
£
CO CO
2.2 Surfaces
We review some basic topology of surfaces. See any of the books by Hatcher [14], Massey [20], or Stillwell [25] for a comprehensive treatment.
A surface (or 2-manifold) £ possibly with boundary is a compact, connected, topological space where each point has a neighborhood homeomorphic either to the plane or to the closed half-plane; the points without neighborhood homeomorphic to the plane comprise the boundary of £. A surface is non-orientable if it contains a subset homeomorphic to the Mobius band, and orientable otherwise. Here and in the sequel, surfaces are considered up to homeomorphism; in particular, a ^ disk is just a surface homeomorphic to the standard unit disk in R2.
An orientable surface is homeomorphic to a sphere where g disjoint disks are removed, a handle (a torus with one boundary component) is attached to each of the remaining g circles, and then b disjoint disks are removed, for unique integers g,b > 0. A non-orientable surface is homeomorphic to a sphere where g disjoint disks are removed, a Mobius band is attached to each of the remaining g circles, and then b disjoint disks are removed, for unique integers g > 1 and b > 0. In both cases, g is called the genus of the surface. For simplicity, we define the reduced genus g to be 2g, if £ is orientable, and g, otherwise. £ denotes the surface without boundary obtained by attaching a disk to each boundary component of £.
2.3 Graph Embeddings
An embedding of a graph G in a surface £ is a drawing of G on £ without crossings. More precisely, the vertices of G are mapped to distinct points of the interior £; each edge is mapped to a path in the interior of £, such that the endpoints of the path agree with the points assigned to the vertices of that edge. Moreover, all the paths must be without intersection or self-intersection except, of course, at common endpoints. We sometimes identify a graph G with its embedding on £. The faces of G are the connected components of the complement of the image of G in £.
In this paper, G is cellularly embedded on E if the faces of G on E are (homeomorphic to) open disks. In particular, each face of a cellular embedding on £ is homeomorphic to an open disk with zero, one, or more disjoint open disks removed; the boundaries of these open disks belong to the boundary of £. For a cellularly embedded graph G with V vertices, E edges, and F faces, Euler's formula states that V — E + F = 2 — g.
We assume that the embedding is represented in a suitable way, like for example the gem representation, using the incidence graph of flags (vertex-edge-face incidences) discussed by Epp-stein [10], or rotation systems [22]. For orientable surfaces, one can also use the DCEL that is customary in Computational Geometry (see, e.g., de Berg et al. [8]). More precisely, we store
lO CSI
the embedding of G on S, and mark within each face of the embedding the number of boundary Q components of E it contains.
If G is a graph embedded on E without isolated vertices, we will denote by E\G the surface with boundary obtained after cutting E along G. Note that E\G is a surface with boundary. In contrast, E \G is a set operation where we remove from E the points in (the image of the embedding of) G. In particular, if G is cellularly embedded, E\G is a union of closed disks, whereas E \ G is 4J a union of open disks.
We say that G seVaraU, E f E\\C (e<iuivalently E \ G) has at >east two connected compel.
2.4 Homotopy and Homology
Let G be a graph embedded on E. Homotopy and homology are two equivalence relations on the set of loops in G with a given basepoint. Here, we stick to a concise description of these notions and refer to one of the aforementioned books for a more formal and detailed treatment.
Let us fix a common basepoint for all loops considered in this section. Two loops in G are homotopic if one can be deformed continuously to the other on the surface, keeping the basepoint fixed during the deformation. It turns out that the equivalence classes, called homotopy classes, form a group, where the multiplication in the group corresponds to the concatenation of the loops. The zero element is the set of loops that are homotopic to the constant loop; such loops are called contractible, or homotopically trivial. An important characterization is that a simple loop is contractible if and only if it bounds a disk on the surface.
Homology is a coarser equivalence relation than homotopy. The homology group is the abelian-ization of the homotopy group. A loop in G is null-homologous, or homologically trivial, if it belongs to the zero homology class. We also have a nice characterization for simple loops: a simple loop is null-homologous on E if and only if it separates E (or, equivalently, E). As in previous papers, when we write "separating on E", we really mean "null-homologous on E": these two notions coincide for simple loops, and the latter is also defined for non-simple loops, which turns out to be useful.
2Therefore, contractible implies separating, even for non-simple loops.
If G is cellularly embedded on E, then G contains non-contractible cycles except when E is the sphere or the disk. Also, G contains non-separating cycles except when E is the sphere.
When considering the problem of finding a shortest non-contractible loops or cycles, we assume every face of G contains at most one boundary of E. This is possible since several boundary components of E in one face of G can be replaced with one single boundary component without changing the contractibility character of the loops in G. When considering the computation of shortest non-separating loops or cycles, we assume our input surface E has no boundary. This is valid since a cycle is separating in E if and only if it is separating in E.
Henceforth, we use the term non-trivial as a shorthand for non-contractible or non-separating.
g 2.5 Duality
Let G be a graph cellularly embedded in E. Its dual graph, denoted by G*, has for vertices the set of faces of E and for edges the set of edges (dual to) E(G): two faces are adjacent if they share an edge of G. The edge dual to e is denoted by e*, and it connects the two faces adjacent to e in the embedding. The dual graph G* has a natural embedding in E: each vertex f * of G*, corresponding to face f of G, is assigned to a point pf of the interior of the face f; for each edge uv of G, incident to faces f and f', the dual edge (uv)* is assigned a curve that connects the points pf and pf and crosses G precisely at the edge uv. For our discussion, it is convenient to make the following assumptions: for every face f of G containing a boundary component (which is unique in that face
£
CO CO
by our assumption of Section 2.4) the point pf belongs to that boundary component, and we add to G* a loop edge, whose image is the boundary component. (Such loop edges correspond to no edge of the primal graph G.) For a set of edges A C E(G), we use the notation A* = {e* | e € A}.
vO 2.6 Deformation retract
o
A subspace A of a topological space X is a deformation retract of X if there is a continuous map F : X x [0,1] ^ X such that for every x in X and a in A, we have F(x, 0) = x, F(x, 1) € A, and F (a, 1) = a.
It is known that if A is a deformation retract of X, then X and A have the same homotopy type. The (quite intuitive) consequence that will be useful to us is that, under this condition, A and X have the same number of connected components, and A has a non-contractible loop if and only if X has a non-contractible loop.
lO
c^
i—i 3 Shortest Non-Trivial Loops
i—i
In this section, we prove Theorem 4; the tools developed here will be useful for the proof of Theorems O 1 and 3 as well.
As already noted, for the non-contractible case, Theorem 4 follows directly from Erickson and Har-Peled [11, Lemma 5.2] by replacing Dijkstra's algorithm with a breadth-first search. For the non-separating case, this result is new and improves upon previous papers [11, 6, 3] in the case of unweighted graphs. The ideas are closely related to Erickson and Whittlesey's algorithm to compute a shortest system of loops [12] (specifically, a shortest non-separating loop is the first loop computed by their greedy algorithm, although they do not compute it in linear time). The idea of computing shortest non-trivial loops using this method appears in one of the authors' course
00 notes [7]. CSI
Let T be an arbitrary spanning tree of G; let C* be the subgraph of G* with the same vertex set as G* and edge set E(G*) \ E(T)*. (In particular, C* contains every loop edge of G* in a boundary component of £.)
o
CSI
I
CO CO
Lemma 5. C* is a cut graph of £; that is, £ \ C* is (homeomorphic to) an open disk.
Proof. £ \ C* can be obtained by taking all faces of G* (which are open disks) and gluing them in a tree-like fashion according to the tree T, i.e., along the edges of E(T)*. Since attaching disks in this way gives a disk, we obtain that £ \ C* is a disk.	□
The following lemma was also noted and used by Erickson and Whittlesey [12, Section 3.4].
-H
Lemma 6. Let e € E(G) \ E(T). Then C* — e* is a deformation retract of £ \ t(T, e).
&
Proof. The cycle t(T, e) cuts C* at exactly one point. Therefore this cycle corresponds to a path intersecting the boundary of the closed disk £\C* exactly at its endpoints. (See Figure 1.) Both halves of the disk retract to the corresponding portion of the boundary of the disk. Therefore,
£ \ r(T, e) retracts to C* \ (e* n r(T, e)). This in turn retracts to C* -e*.	□
W
Corollary 7. Let e € E(G) \ E(T). The cycle t(T, e) is separating on £ if and only if C* — e* is not connected.. The cycle t(T, e) is contractible if and only if C* — e* has a connected component that is a tree (possibly reduced to a single vertex).
VD O
m 2
10
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
$H
a
CD U
Figure 1: The retraction in the proof of Lemma 6. The boundary of the disk is the boundary of £\C *.
Proof. The cycle t(T, e) is separating if and only if £ \ t(T, e) is not connected; by Lemma 6, this holds if and only if C* — e* is not connected.
t(T,e) is contractible if and only if one component of £ \ t(T,e) is a disk, i.e., has no non-contractible loop. By Lemma 6, this holds if and only if one component of C* — e* has no non-contractible loop, i.e., is a tree.	□
A cycle t(T, e) is of one of the following three topological types: contractible, non-contractible but separating, and non-separating. We can partition the edges e* of C* into three sets, depending on the corresponding type of t(T, e). Figure 2 illustrates this classification.
For later use, it will be convenient to use Enon-con(T) (resp. Enon-sep(T)) for the set of edges e in E(G) \ E(T) such that t(T,e) is non-contractible (resp. non-separating). As before, we use Enon-triv (T) as an ambiguous term to refer to Enon-con (T) or Enon-sep (T) as needed.
Lemma 8. The sets Enon-con(T) and Enon-sep(T) can be computed in O(n) time.
Proof. We construct the cut graph C* in linear time. By Corollary 7, Enon-con (T) can be obtained by the following procedure: starting with C*, we repeatedly remove edges with an incident vertex of degree one; the edge set of the resulting graph is then exactly Enon-con(T)*. To obtain Enon-sep (T), note that, by Corollary 7, Enon-sep(T)* is precisely the set of non-bridge edges in C*. The computation of the bridge edges of a graph in linear time using depth-first search is part of the folklore (see Aho et al. [1, Section 5.3] for the similar problem of determining biconnected components).	□
Let s be an arbitrary vertex of G. We have the following structural result on shortest non-trivial loops based at s.
Lemma 9. Assume T is a BFS tree from root s. Every shortest loop among the loops t(T,s,e), where e € Enon-triv, is a shortest non-trivial loop through s.
Proof. A proof appears in Thomassen [26] in a more general setting. We provide an ad hoc short proof. Let £ be a non-trivial loop with basepoint s. We show that some non-trivial loop t(T, s, e) is no longer than £. Let e\,e2,... ,ek be the edges of £, in the same order as they appear along £.
e
VD O
m
M <
io
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
u
a
CD U
				
				
				
				
				
Figure 2: Top left: A graph G embedded in a double torus with a spanning tree T marked with bolder edges. Top right: The cut graph C* is marked with bold edges; thinner edges are from the primal graph. Bottom left: classification of the edges of C*. The bold solid edges are Enon-sep(T)*; the bold dashed edges are (Enon-con(T) \ Enon-sep (T))*; the thin edges are E(C*) \ Enon-con(T)*. The dotted parts of edges do not provide any information about their type. Bottom right: examples of the loop t (T, e) in bold for different types of e* € C*.
G\
o
CSI
I
Since t is homotopic in E (and therefore also homologous in E) to the concatenation of loops t(T,s,e1) ■ t(T,s,e2) ••• t(T, s,ek), at least one of the loops t(T, s, ei) is non-trivial. However, t(T, s, ei) is a shortest loop through s that contains ei because T is a BFS tree, whence t(T, s, ei) is no longer than Furthermore, ei cannot belong to T, for otherwise the loop t(T, s, ei) would be contract.ible (and separating).	□
o
We conclude the proof of Theorem 4.
CO
Proof of Theorem 4■ We construct a BFS tree T of G from s in linear time. We attach to each vertex u of G a label d(u) equal to its distance from s. We then compute Enon-triV(T), again in linear time, using Lemma 8. Among the edges e of Enon-triv(T), we select an edge eo minimizing the length of t(T, s, e), or equivalently, minimizing the sum d(u) + d(v) where u and v are the endpoints of e. Finally, we report the loop t(T, s, e0). The procedure takes linear time; its correctness follows from Lemma 9 and from the fact that r(T, e) is non-trivial if and only if r(T, s, e) is non-trivial. □
CSI
Our algorithm trivially extends to the weighted case, at the expense of a logarithmic factor, by ,—I replacing the BFS with a shortest path tree computation.
Also, the same ideas yield algorithms to compute shortest loops with an odd number of edges and shortest one-sided loops (which reverse the orientation of the surface, when it is non-orientable). Lemma 9 extends immediately to these two problems. To compute a shortest loop with an odd number of edges, it suffices to store, on each vertex of G, the parity of the number of edges to the root; then t(T, s, e) has an odd number of edges if and only if the parities of the vertices of G incident with e are the same. To compute a shortest one-sided loop, it suffices to choose local orientations of the surface at each vertex that are consistent across each edge of T; then t(T, s, e) is one-sided if and only if the orientations of the two vertices of G incident with e do not match across edge e. The results of the next section extend to the problem of finding shortest one-sided cycles, but do not extend to the problem of finding a shortest cycle with an odd number of edges.
C^
c^
4 Tools for Shortest Non-Trivial Cycles
4.1 Shortest Non-Trivial Loops with Remote Sources in Parallel
CO
The following result will be our tool to work with several sources simultaneously.
Lemma 10. Let V1,..., Vt be subsets of V(G) that are pairwise disjoint, let s1,..., st be vertices with si € V for each i, and let Li be the set of non-trivial loops through si contained in G[Vi]■ In O(n) time we can find a shortest loop in (Ji Li, or correctly report that IJi Li is empty■
Proof. We first describe the algorithm interlaced with an analysis of its running time, and then discuss its correctness.
For each i, we construct a BFS tree Ti with root si of the component of G[Vi] that contains si. To each vertex u of G, we attach two labels, c(u) and d(u). The label c(u) has value i if u is in the same connected component of G[V] as si, and has value 0 otherwise. The label d(u) is the distance between u and sc(u) if c(u) > 1, and undefined if c(u) = 0. Since the sets V1,..., Vt are disjoint, the labels c(u) and d(u) are uniquely defined. These labels can be computed in O(n) time using the BFS trees T1,...,Tt.
We then extend the forest T1,... ,Tt to a spanning tree T of G. This can also be done in
a
linear time. Next, we compute Enon-triv(T) using Lemma 8. Let E be the subset of the edges
uv € Enon-triv(T) such that c(u) = c(v) and this number is non-zero. If E is empty, we report that O ui Li is empty. Otherwise, we compute
xy = arg min{d(u) + d(v) | uv € E}
and return the loop t(T, sc(x), xy). The construction of Enon-triv(T) and E takes linear time, and we spend additional constant time per edge in E to find the edge xy. This concludes the description ^ of the algorithm.
We now show the correctness of the algorithm. Let Ei De the set of edges uv in E(G) with endpoints in Ti, i.e., such that c(u) = c(v) = i. Also, let Enon-triv(Ti) De the subset of the edges e in Ei such that t(Ti,si,e) is non-trivial.
By the same arguments as in the proof of Lemma 9, if Li is not empty, then it contains a shortest loop of the form t(Ti, si, e) for some edge e in Ei. As a consequence, a shortest non-trivial £ ,oopin Li is giwn Dy t(Ti, si,e) where
e = arg min{d(u) + d(v) | uv € Enon-triv (Ti)}. For any edge e in Ei, it holds that t(Ti, si, e) = t(T, si, e) and t(Ti, e) = t(T, e). It follows that
o
Enon-triv(Ti ) — Enon-triv(T) H Ei,
whence E = IJi Enon-triv(?i). The correctness of the algorithm directly follows.	□
4.2 Surface Decomposition
Lemma 11. Let s be a vertex of G. In O(n) time, we can compute a set K of vertices of G that intersects every non-trivial closed walk in G and is the union of the vertex sets of m shortest paths from s, where m = 2g + b for the non-contractible case and 2g for the non-separating case.
Proof. Assume first that £ has no boundary (this is the only relevant situation in the non-separating case). We use the tree-cotree decomposition of Eppstein [10]. Consider a BFS tree T from the vertex s. Let (T')* be an arbitrary spanning tree of G* — E(T)*. Thus T and T' are edge-disjoint in G; we let X be the remaining edges of G. It follows from Euler's formula that X has g edges.
Consider the set of loops L = {t(T, s,e) | e € X}: their union |J L is a cut graph. Indeed, £\(T U X) is a set of faces connected according to the dual tree T', hence a disk. But (J L is obtained from T U X by iteratively removing a degree one vertex with its incident edge, and this operation preserves the fact that the complement is a disk. Let K be the set of vertices in L. Since U L is a cut graph, each non-trivial closed walk must intersect K. Moreover, since T is a BFS tree, hh each of the g loops t(T, s, e) in L consists of two shortest paths from s.
K can be computed in linear time, as we describe next. Computing a BFS tree T from s, the spanning tree in the dual graph, and computing the set of edges X takes linear time. We mark in T the vertex s and the endpoints of the edges in X. By definition of the loops in L, the set K is the set of vertices of the minimal subtree of T that includes the marked vertices. This subtree is ih obtained in linear time by recursively removing unmarked degree one vertices.
It remains to consider the case where we want to compute a shortest non-contractible cycle on a surface £ with boundary. In this case we attach a handle to every boundary component of £, obtaining a surface £ without boundary. To make G cellular on £, we just have to add two loop edges per boundary component of £; see Figure 3. Let G be the new graph. Then we apply the previous construction to this new graph. We obtain a set K that intersects every cycle of G that is non-trivial on £; furthermore, K is in the union of 2g + b shortest paths from the source s. (The
VD O
CO
M <
10
Figure 3: Detail of the graph G cellularly embedded in E, as constructed in the proof of Lemma 11. We attach a handle to each boundary component and add two loop edges to obtain a cellular embedding.
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
u
a
CD U
two loop edges e1 and e2 defining a handle contribute to a single shortest path to K, namely, the shortest path from s to the common endpoint of ei and e2.) Hence K intersects also every cycle in G that is non-trivial in E. Furthermore, the shortest paths from s in G and G are the same, because we only added loop edges, so K lies on 2g + b shortest paths from s in G. To conclude, note that a cycle is contractible in E if and only if it is contractible in E. So we can take K = K. □
4.3 2-Approximation for the Edge-Width
Another tool we will need is the algorithm by Erickson and Har-Peled [11, Corollary 5.8] to compute a 2-approximation of the edge-width. They describe it in the case of weighted graphs; in our setting, we can shave off a logarithmic factor using Theorem 4. We sketch the proof for convenience, and also because most of the tools have already been presented.
Proposition 12. We can compute a non-trivial cycle whose length is at most twice the length of a shortest non-trivial cycle, in O((g + b)n) time for the non-contractible case and O(gn) time for the non-separating case.
Proof. Let n be a shortest path in G. Erickson and Har-Peled [11, Lemma 5.6] give an algorithm that computes in O(n log n) time a non-trivial loop intersecting n whose length is at most twice the length of the shortest non-trivial loop intersecting n. Their algorithm is the following: (1) contract n to a single point; (2) compute the shortest non-trivial loop £ through that point; (3) expand back n, and return the loop resulting from £ after the expansion. Since n is a shortest path, the expansion can at most double the length of the loop, which is therefore a 2-approximation of the shortest non-trivial loop intersecting n. Since our graph is unweighted, we can use Theorem 4 in step (2), and therefore the algorithm runs in O(n) time.
By Lemma 11, we can compute a set of O(g + b) or O(g) shortest paths intersecting every non-trivial loop. We can apply the previous algorithm to each of these shortest paths to obtain a non-trivial loop ££ whose length is at most twice the length of a shortest non-trivial cycle. By construction £' is either a cycle or a loop composed of a starting path concatenated with a cycle and the reverse of the starting path. In the latter case, we simply remove the starting and ending paths to get a non-trivial cycle.	□
o
c^
o
CSI
CO
5 Proofs of the Main Results
We are now ready to give the proofs of our main results.
VO 5.1 Output-Sensitive Algorithm
Proof of Theorem 1. We start by computing the set K of vertices as in Lemma 11. It then suffices to compute a shortest non-trivial loop based at some vertex in K, or to determine that every such loop has length larger than k.
Let Si be the set of vertices in K at distance exactly i from s (0 < i < n). Each Si has cardinality at most 2g + b (non-contractible case) or 2g (non-separating case). For simplicity, in the remaining part of the proof, we only consider the non-contractible case; the non-separating case is ^ the same, except that we can replace 2g + b by 2g. For each j, 0 < j < k, we put the elements of
C^
Sj, S(fc+1)+i, S2(fc+1)+j, • • •
1—1
into at most 2g + b batches, each containing at most one element from each of these Si. In total, we have a partition of K into O((g + b)k) batches such that any two vertices in the same batch are at distance at least k + 1 from each other (because an element in Si and an element in Sj are at distance at least |i — j| from each other by the triangle inequality).
Now, consider a single batch {s1,..., st}. For each i, let Vj be the set of vertices at distance at most k/2 from si; the Vj's are pairwise disjoint. We can thus apply Lemma 10: if there exists a non-trivial loop based at some si that has length at most k, we obtain the shortest such loop.
We apply this operation for every batch; thus we computed, for each vertex of K, the shortest loop based at that vertex, unless that loop has length larger than k. If the shortest of the resulting 00 loops has length at most k, this is the output of the algorithm. Otherwise (or if no loop has been found), we report that no non-trivial loop with length at most k exists.
The set K and the O((g + b)k) batches can be computed in O(n) time. Then the O(n) time algorithm of Lemma 10 is applied once for each of the O((g + b)k) batches; thus the total running time is 0((g + b)nk).	□
The proof of our output-sensitive algorithm is now easy:
Proof of Corollary 2. The edge-width can be computed applying Theorem 1 with k = 20,21, until a non-contractible cycle is found. The total cost is
O((g + b)n(2^log fcl+1)) = O((g + b)nk),
where k is the edge-width. (Alternately, we may use Proposition 12 to compute a 2-approximation of the edge-width, and then apply Theorem 1 only once.) The same arguments, with g + b replaced by g, yield the result for the non-separating edge-width.	□
W
CD ■ i u CD
5.2 Approximation Algorithm
Finally, we prove Theorem 3.
• i
Proof of Theorem 3. Again, we only consider the non-contractible case; the non-separating case is handled in the same way. Let k be the edge-width of G. Using Proposition 12, we compute in }_i O((g + b)n) time an integer k' such that k < k' < 2k.
2
Let K be the set of vertices of G obtained by applying Lemma 11; in particular, K intersects every non-trivial cycle. For i > 0, let Si be the set of vertices of K at distance i from the fixed vertex s. We put Si = S^\k<£/4~\ and consider the subset Ki = UiSi of K.
We claim that some non-trivial loop of length at most (1 + e)k must intersect Ki. Indeed, let £ be a shortest non-trivial cycle; £ contains a vertex v of K. From the construction of K, the vertices of the shortest path n from v to s are in K. This shortest path contains a vertex w in Ki at distance at most kke/4 < ke/2 from v. Using the subpath of n between w and v as an approach path to £, we obtain a non-trivial loop of length at most (1 + e)k through w. This proves the claim.
Recall that, as a consequence of Lemma 11, every set Si contains at most 2g + b elements. Let
t =
2 <
o
CSI
(l+g)(fc'+l) | fc'e/41
= O(1/e). For each j, 0 < j < t, we put the elements of
i i i
Sj > St+j, S2t+j, • • •
into at most 2g + b batches, each containing at most one element from each of these Si. In total, we have a partition of Ki into O((g + b)/e) batches such that any two vertices in the same batch are at distance at least t\kie/4] > (1 + e)(ki + 1) from each other (because an element in Si and an element in Sj are at distance at least |i — j| from each other by the triangle inequality). Within each batch, we apply Lemma 10, where for each source si in the batch we take Vi as the set of vertices at distance at most (1 + e)k'/2 from si. In O(n) time, we find a shortest non-trivial loop of length at most (1 + e)ki through a given vertex in the batch, or determine that no such loop exists.
We do this for each batch. This takes O((g+b)n/e) time in total. Finally, we return the shortest loop between the shortest non-trivial loops found over all batches. We know by the above claim that the computation will find in some batch a non-trivial loop of length at most (1 + e)k. As at the end of the proof of Proposition 12, it remains to extract a cycle from this loop, if needed. □
CSI
Acknowledgments
We thank Jeff Erickson for pointing out reference [15] and its implications, and Luca Castelli Aleardi for an inspiring discussion.
CO
CO References
[1]	A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer programs. Addison-Wesley, 1974.
fc
[2]	M. O. Albertson and J. P. Hutchinson. The independence ratio and genus of a graph. Transactions of the American Mathematical Society, 226:161-173, 1977.
[3]	S. Cabello and E. W. Chambers. Multiple source shortest paths in a genus g graph. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 89-97, 2007.
[4]	S. Cabello, E. Colin de Verdiere, and F. Lazarus. Finding shortest non-trivial cycles in directed graphs on surfaces. In Proceedings of the 26th Annual ACM Symposium on Computational Geometry (SOCG), pages 156-165, 2010.
"Jh
[5]	S. Cabello, M. DeVos, J. Erickson, and B. Mohar. Finding one tight cycle. ACM Transactions on Algorithms, 2010. To appear. Preliminary version in S0DA'08.
Jh
S. Cabello and B. Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete & Computational Geometry, 37(2):213-235, 2007.
E. Colin de Verdiere. Algorithms for graphs on surfaces. Course notes, available at http: //www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf,2008.
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.
M. DeVos, K.-i. Kawarabayashi, and B. Mohar. Locally planar graphs are 5-choosable. J■ Comb. Theory Ser. B, 98(6):1215-1232, 2008.
D. Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 599-608, 2003.
J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete & Computational Geometry, 31(1):37-59, 2004.
J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1038-1046, 2005.
J. R. Fiedler, J. P. Huneke, R. B. Richter, and N. Robertson. Computing the orientable genus of projective graphs. J. Graph Theory, 20(3):297-308, 1995.
A.	Hatcher. Algebraic topology. Cambridge University Press, 2002. Available at http://www. math.cornell.edu/~hatcher/.
J. P. Hutchinson. On short noncontractible cycles in embedded graphs. SIAM Journal on Discrete Mathematics, 1(2):185-192, 1988.
K.-i. Kawarabayashi and B. Mohar. Graph and map isomorphism and all polyhedral em-beddings in linear time. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 471-480, 2008.
K.-i. Kawarabayashi and B. Reed. Computing crossing number in linear time. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 382-390, 2007.
Y. Kobayashi and K.-i. Kawarabayashi. Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1146-1155, 2009.
M. Kutz. Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SOCG), pages 430-438, 2006.
W. S. Massey. Algebraic Topology: An Introduction, volume 56 of Graduate Texts in Mathematics. Springer-Verlag, 1977.
B.	Mohar and N. Robertson. Flexibility of polyhedral embeddings of graphs in surfaces. J. Comb. Theory Ser. B, 83(1):38-57, 2001.
B. Mohar and C. Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001.
[23]	N. Robertson and P. D. Seymour. Graph minors. VII. Disjoint paths on a surface. Journal of Combinatorial Theory, Series B, 45:212-254, 1988.
[24]	N. Robertson and R. P. Vitray. Representativity of surface embeddings. In B. Korte, L. Lovasz, and Promel, editors, Paths, flows, and VLSI-layout, pages 293-328. Springer-Verlag, Berlin, 1990.
[25]	J. Stillwell. Classical topology and combinatorial group theory. Springer-Verlag, New York, 1980.
[26]	C. Thomassen. Embeddings of graphs with no short noncontractible cycles. Journal of Combinatorial Theory, Series B, 48(2):155-177, 1990.
[27]	C. Thomassen. Five-coloring maps on surfaces. J. Comb. Theory Ser. B, 59(1):89-105, 1993.
lO
[28]	X. Yu. Disjoint paths, planarizing cycles, and spanning walks. Transactions of the American Mathematical Society, 349:1333-1358, 1997.
i—l
CO CD
Jh
CD CO
u
a
CD U