{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108483"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108483","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms for flows and disjoint paths in planar graphs","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 polynomial-time algorithms or are faster than all previously-known 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 near-linear 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 vertex-disjoint S-T paths problem in near-linear time when the number of terminals is fixed but greater than 2. We also modify our algorithms to handle real capacities in near-linear time when they are three terminals. Second, we describe algorithms to compute element-connectivity and a related structure called the reduced graph. We show that global element-connectivity 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 vertex-disjoint 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 k-approximation 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 NP-hard in planar graphs. On the other hand, we show that the problem is polynomial-time 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 k-min-sum orientation problem.","abstract_html":"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 polynomial-time algorithms or are faster than all previously-known 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 near-linear 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 vertex-disjoint S-T paths problem in near-linear time when the number of terminals is fixed but greater than 2. We also modify our algorithms to handle real capacities in near-linear time when they are three terminals. Second, we describe algorithms to compute element-connectivity and a related structure called the reduced graph. We show that global element-connectivity 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 vertex-disjoint 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 k-approximation 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 NP-hard in planar graphs. On the other hand, we show that the problem is polynomial-time 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 k-min-sum orientation problem.","abstract_has_math":false,"creators":["Wang, Yipu"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Erickson, Jeff","Chekuri, Chandra","Chandrasekaran, Karthekeyan","Klein, Philip N"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-10-07T20:59:49Z","date_published":"2020-10-07T20:59:49Z","updated_at":"2026-07-22T22:24:48Z","subjects":["planar graphs","maximum flow","element connectivity","scaling algorithm","disjoint paths","orientation","ideal orientation","approximation algorithms","reduced graph"],"languages":["en"],"rights":["Copyright 2020 Yipu Wang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108483","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Erickson, Jeff","Chekuri, Chandra","Chandrasekaran, Karthekeyan","Klein, Philip N"]},{"key":"dc:creator","label":"Author","values":["Wang, Yipu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-10-07T20:59:49Z","2020-07-14","2020-08"]},{"key":"dc:type","label":"Dc Type","values":["Thesis","text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["planar graphs","maximum flow","element connectivity","scaling algorithm","disjoint paths","orientation","ideal orientation","approximation algorithms","reduced graph"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Yipu Wang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108483"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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 polynomial-time algorithms or are faster than all previously-known 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 near-linear 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 vertex-disjoint S-T paths problem in near-linear time when the number of terminals is fixed but greater than 2. We also modify our algorithms to handle real capacities in near-linear time when they are three terminals. Second, we describe algorithms to compute element-connectivity and a related structure called the reduced graph. We show that global element-connectivity 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 vertex-disjoint 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 k-approximation 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 NP-hard in planar graphs. On the other hand, we show that the problem is polynomial-time 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 k-min-sum orientation problem.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms","The student, Yipu Wang, accepted the attached license on 2020-07-13 at 13:56.","The student, Yipu Wang, submitted this Dissertation for approval on 2020-07-13 at 14:10.","This Dissertation was approved for publication on 2020-07-14 at 10:55.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15591 on 2020-10-02 at 15:13:12","Made available in DSpace on 2020-10-07T20:59:49Z (GMT). No. of bitstreams: 4 WANG-DISSERTATION-2020.pdf: 1403122 bytes, checksum: 74407b9877cbb40e3970b64f08e21353 (MD5) thesis_source.zip: 3139559 bytes, checksum: 70f86a1019fa3185c87248dee23c1872 (MD5) LICENSE.txt: 4206 bytes, checksum: 8c08dc7cca26a4058ed4d4d5c0f4b6b2 (MD5) PROQUEST_LICENSE.txt: 4552 bytes, checksum: b768f21a4464766d0e5462c0421e08a3 (MD5) Previous issue date: 2020-07-14"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithms for flows and disjoint paths in planar graphs"]}]}],"canonical_facts":{"dc:contributor":["Erickson, Jeff","Chekuri, Chandra","Chandrasekaran, Karthekeyan","Klein, Philip N"],"dc:creator":["Wang, Yipu"],"dc:date":["2020-10-07T20:59:49Z","2020-07-14","2020-08"],"dc:description":["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 polynomial-time algorithms or are faster than all previously-known 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 near-linear 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 vertex-disjoint S-T paths problem in near-linear time when the number of terminals is fixed but greater than 2. We also modify our algorithms to handle real capacities in near-linear time when they are three terminals. Second, we describe algorithms to compute element-connectivity and a related structure called the reduced graph. We show that global element-connectivity 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 vertex-disjoint 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 k-approximation 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 NP-hard in planar graphs. On the other hand, we show that the problem is polynomial-time 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 k-min-sum orientation problem.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms","The student, Yipu Wang, accepted the attached license on 2020-07-13 at 13:56.","The student, Yipu Wang, submitted this Dissertation for approval on 2020-07-13 at 14:10.","This Dissertation was approved for publication on 2020-07-14 at 10:55.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15591 on 2020-10-02 at 15:13:12","Made available in DSpace on 2020-10-07T20:59:49Z (GMT). No. of bitstreams: 4 WANG-DISSERTATION-2020.pdf: 1403122 bytes, checksum: 74407b9877cbb40e3970b64f08e21353 (MD5) thesis_source.zip: 3139559 bytes, checksum: 70f86a1019fa3185c87248dee23c1872 (MD5) LICENSE.txt: 4206 bytes, checksum: 8c08dc7cca26a4058ed4d4d5c0f4b6b2 (MD5) PROQUEST_LICENSE.txt: 4552 bytes, checksum: b768f21a4464766d0e5462c0421e08a3 (MD5) Previous issue date: 2020-07-14"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108483"],"dc:language":["en"],"dc:rights":["Copyright 2020 Yipu Wang"],"dc:subject":["planar graphs","maximum flow","element connectivity","scaling algorithm","disjoint paths","orientation","ideal orientation","approximation algorithms","reduced graph"],"dc:title":["Algorithms for flows and disjoint paths in planar graphs"],"dc:type":["Thesis","text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:48Z"}