Date on Master's Thesis/Doctoral Dissertation
Applied and Industrial Mathematics, PhD
Algorithms; Graph algorithms
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.
Suer, Charles J., "The PC-Tree algorithm, Kuratowski subdivisions, and the torus." (2015). Electronic Theses and Dissertations. Paper 2244.