This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches previously employed to solve the problem: divide-and-conquer and factorizing permutations. It runs in linear-time, and is straightforward in its understanding, correctness, and implementation. It merely requires a collection of trees and simple traversals of these trees. The split-decomposition algorithm is similar in being straightforward in its understanding and correctness. An efficient implementation of the algorithm is described that uses the union-find data-structure. A novel charging argument is used to prove the running-time. The algorithm is the first to use the recent reformulation of split decomposition in terms of graph-labelled trees. This facilitates its extension to circle graph recognition. In particular, it allows us to efficiently apply a new lexicographic breadth-first search characterization of circle graphs developed in the thesis. Lexicographic breadth-first search is additionally responsible for the efficiency of the split decomposition algorithm, and contributes to the simplicity of the modular decomposition algorithm.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/29888 |
| Date | 31 August 2011 |
| Creators | Tedder, Marc |
| Contributors | Corneil, Derek |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0022 seconds