Files in this item
Files  Description  Format 

application/pdf WANGDISSERTATION2020.pdf (1MB)  (no description provided) 
Description
Title:  Algorithms for flows and disjoint paths in planar graphs 
Author(s):  Wang, Yipu 
Director of Research:  Erickson, Jeff 
Doctoral Committee Chair(s):  Erickson, Jeff 
Doctoral Committee Member(s):  Chekuri, Chandra; Chandrasekaran, Karthekeyan; Klein, Philip N 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  planar graphs
maximum flow element connectivity scaling algorithm disjoint paths orientation ideal orientation approximation algorithms reduced graph 
Abstract:  In this dissertation we describe several algorithms for computing flows, connectivity, and disjoint paths in planar graphs. In all cases, the algorithms are either the first polynomialtime algorithms or are faster than all previouslyknown algorithms. First, we describe algorithms for the maximum flow problem in directed planar graphs with integer capacities on both vertices and arcs and with multiple sources and sinks. The algorithms are the first to solve the problem in nearlinear time when the number of terminals is fixed and the capacities are polynomially bounded. As a byproduct, we get the first algorithm to solve the vertexdisjoint ST paths problem in nearlinear time when the number of terminals is fixed but greater than 2. We also modify our algorithms to handle real capacities in nearlinear time when they are three terminals. Second, we describe algorithms to compute elementconnectivity and a related structure called the reduced graph. We show that global elementconnectivity in planar graphs can be found in linear time if the terminals can be covered by O(1) faces. We also show that the reduced graph can be computed in subquadratic time in planar graphs if the number of terminals is fixed. Third, we describe algorithms for solving or approximately solving the vertexdisjoint paths problem when we want to minimize the total length of the paths. For planar graphs, we describe: (1) an exact algorithm for the case of four pairs of terminals on a single face; and (2) a kapproximation algorithm for the case of k pairs of terminals on a single face. Fourth, we describe algorithms and a hardness result for the ideal orientation problem. We show that the problem is NPhard in planar graphs. On the other hand, we show that the problem is polynomialtime solvable in planar graphs when the number of terminals is fixed, the terminals are all on the same face, and no two of the terminal pairs cross. We also describe an algorithm for serial instances of a generalization of the ideal orientation problem called the kminsum orientation problem. 
Issue Date:  20200714 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/108483 
Rights Information:  Copyright 2020 Yipu Wang 
Date Available in IDEALS:  20201007 
Date Deposited:  202008 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois