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.

Share

COinS