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 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
