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 Co-Chair (if applicable)

Biro, Csaba

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.