Date on Master's Thesis/Doctoral Dissertation


Document Type

Doctoral Dissertation

Degree Name

Ph. D.



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


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.