Graph Decompositions with Applications to Circle and Permutation Graphs (thesis)

Abstract:

Just as integers can be decomposed into prime factors, it is possible to define primeness on graphs so that graphs may also be decomposed into their prime components. Under the definitions presented in this work, several non-isomorphic graphs may yield identical factorings. An efficient implementation
of an algorithm which Cunningham introduced to decompose graphs is shown. A second algorithm to decompose graphs is also shown. This second algorithm is shown because it is also used in the inductive proof of a property of prime graphs - each vertex in a prime graph must be contained in a certain induced subgraph of the prime graph. A close link between prime graphs and certain classes of intersection graphs, namely circle graphs and permutation graphs, is established, and a recognition algorithm is presented for each.