Files in this item
Files  Description  Format 

application/pdf Kyle_Fox.pdf (3MB)  (no description provided) 
Description
Title:  Fast algorithms for surface embedded graphs via homology 
Author(s):  Fox, Kyle J. 
Director of Research:  Erickson, Jeff G. 
Doctoral Committee Chair(s):  Erickson, Jeff G. 
Doctoral Committee Member(s):  Chekuri, Chandra S.; Hoiem, Derek W.; Eppstein, David 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  computational topology
topological graph theory Homology minimum cut maximum flow nontrivial cycles 
Abstract:  We describe several results on combinatorial optimization problems for graphs where the input comes with an embedding on an orientable surface of small genus. While the specific techniques used differ between problems, all the algorithms we describe share one common feature in that they rely on the algebraic topology construct of homology. We describe algorithms to compute global minimum cuts and count minimum s,tcuts. We describe new algorithms to compute short cycles that are topologically nontrivial. Finally, we describe ongoing work in designing a new algorithm for computing maximum s,tflows in surface embedded graphs. We begin by describing an algorithm to compute global minimum cuts in edge weighted genus g graphs in g^O(g) n log log n time. When the genus is a constant, our algorithm’s running time matches the best time bound known for planar graphs due to Łącki and Sankowski. In our algorithm, we reduce to the problem of finding a minimum weight separating subgraph in the dual graph and provide two subroutines tailored to different kinds of separating subgraphs. We describe algorithms to compute short nontrivial cycles in edge weighted graphs. Some of the algorithms are tailored to take advantage of undirected edge weights, but others are designed to work in graphs where the edges are directed. For undirected graphs embedded on surfaces of genus g, our algorithms compute nonseparating, noncontractible, and nonnullhomologous cycles in 2^O(g) n log log n time, improving the previous best algorithms of Italiano et al. which run in g^O(g) n log log n time. For directed graphs, we give an algorithm to compute shortest nonnullhomologous cycles in O(g^2 n log n) time, matching the running time of Erickson’s algorithm for computing shortest nonseparating cycles. We also give an O(g^3 n log n) time algorithm for computing shortest noncontractible cycles in directed graphs. This last result improves upon the previous best algorithm by Erickson which runs in g^O(g) n log n time. We describe an algorithm to count minimum s,tcuts. Despite the problem being #Pcomplete in general graphs, our algorithm runs in 2^O(g) n^2 time. After running our algorithm once it becomes possible to sample minimum cuts uniformly at random in O(n log n) time per sample. This result directly generalizes an O(n^2) time algorithm for counting minimum s,tcuts in planar graphs by Bezáková and Friedlander. Like Bezáková and Friedlander, we reduce the problem of counting minimum s,tcuts to one of counting forward t,scuts in an embedded directed acyclic graph. Finally, we describe ongoing work toward computing maximum s,tflows. Borradaile and Klein describe an O(n log n) time algorithm to compute maximum s,tflows in planar graphs. We give a new algorithm that appears to generalize their techniques naturally to surfaces with positive genus, and similar to their algorithm we are able to send flow down augmenting paths in O(g log n + g^2) amortized time per path. We prove that our algorithm performs a quadratic number of augmentations, giving it an overall time bound of O(g n^2 (log n + g)). While we have been unable to find a proof so far, we believe our algorithm may actually run in nearlinear time when the surface has constant genus. 
Issue Date:  20140116 
URI:  http://hdl.handle.net/2142/46579 
Rights Information:  Copyright 2013 Kyle J. Fox 
Date Available in IDEALS:  20140116 
Date Deposited:  201312 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois