Date on Master's Thesis/Doctoral Dissertation
8-2015
Document Type
Doctoral Dissertation
Degree Name
Ph. D.
Department
Mathematics
Degree Program
Applied and Industrial Mathematics, PhD
Committee Chair
Kezdy, Andre
Committee Co-Chair (if applicable)
Biro, Csaba
Committee Member
Biro, Csaba
Committee Member
Wildstrom, Jake
Committee Member
Powers, Robert
Committee Member
Bae, Ki-Hwan
Subject
Algorithms; Graph algorithms
Abstract
The PC-Tree algorithm of Shih and Hsu (1999) is a practical linear-time planarity algorithm that provides a plane embedding of the given graph if it is planar and a Kuratowski subdivision otherwise. Remarkably, there is no known linear-time algorithm for embedding graphs on the torus. We extend the PC-Tree algorithm to a practical, linear-time toroidality test for K3;3-free graphs called the PCK-Tree algorithm. We also prove that it is NP-complete to decide whether the edges of a graph can be covered with two Kuratowski subdivisions. This greatly reduces the possibility of a polynomial-time toroidality testing algorithm based solely on edge-coverings by subdivisions of Kuratowski subgraphs.
Recommended Citation
Suer, Charles J., "The PC-Tree algorithm, Kuratowski subdivisions, and the torus." (2015). Electronic Theses and Dissertations. Paper 2244.
https://doi.org/10.18297/etd/2244
