Skip navigation
Please use this identifier to cite or link to this item:
Title: Testing and Verifying Planarity and Non-Planarity in Graphs
Authors: Greenspan, Thomas Harry Samuel
Advisors: Tarjan, Robert
Contributors: Dvir, Zeev
Department: Mathematics
Class Year: 2015
Abstract: This paper presents an efficient planarity test for arbitrary undirected graphs. The algorithm is a restructured and slightly modified version of the one presented by Hopcroft and Tarjan which runs in O(n) time and space where n is the number of vertices. Various data structures specific to the algorithm are used to simplify reasoning of correctness and run time. In addition this paper outlines how to extract justification for the answer given by the algorithm, either with an embedding of the graph if the graph is planar or a Kuratowski subgraph if the graph is non-planar. This extraction process also takes linear time and space.
Extent: 76 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File SizeFormat 
PUTheses2015-Greenspan_Thomas_Harry_Samuel.pdf642.88 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.