The first linear-time planarity testing algorithm was developed in 1974 by Hopcroft and Tarjan (H&T) [32] using a method to split a biconnected graph up into edge disjoint paths and then sequentially embed them to test for planarity (a path addition method). Shortly afterwards Booth and Leuker [5] developed an alternative vertex addition linear-time planarity test, based on the earlier work of Lempel, Evan and Cederbaum [47], using a new PQ-Tree data structure. Since then there have been many developments in PQ- Tree vertex addition (and related PC-Tree edge addition) methods including authors such as: Chiba et al. [14]; Shih & Hsu [35, 69]; Boyer and Myrvold [10, 11]; and Haeupler and Tarjan [29]. In comparison, path addition has changed very little from the original algorithm. In 1984, Williamson [84] showed how H&T's algorithm can be extended to find Kuratowski sub-graphs in the event of a non-planar graph; and, in 1993, Mehlhorn, Mutzel and Naher [53] produced an implementation (in C) of H&T's algorithm and extended it to create a planar embedding of a graph. This has remained the state-of-the-art in path addition algorithms for over a decade. Recently", de Fraysseix formulated an algorithm [15, 17], based on Tremaux Trees and a characterisation of planarity by W. Wu [87]; this may prove to be a highly optimised version of H&T's algorithm but is difficult to definitively prove as only an outline of its planarity testing phase is provided. These authors represent the majority of the work on path addition methods of planarity testing and embedding; indicating that it receives little attention compared to vertex or edge addition methods This thesis attempts to reinvigorate the field of path addition and demonstrates: • How Trernaux Trees, which allow undirected connected graphs to be represented as a simple partial order relationship are fundamentally related to H&T-‘^planarity testing algorithm and includes some related invariant properties of these trees; • That the restriction on H&T's planarity testing algorithm to test undirected biconnected graphs can be relaxed to undirected connected graphs; • How to generate all possible embeddings of a biconnected component and how to extend this to generate all possible embeddings of separable graphs; and • Empirical Testing of various graph types and sizes to validate these results.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:580367 |
| Date | January 2011 |
| Creators | Taylor, Martyn G. |
| Publisher | University of Kent |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.002 seconds