Algorithms and characterizations for subclasses of planar perfect graphs

Abstract

In this thesis, we consider two major subclasses of planar perfect graphs. We exploit certain decomposability and ordering properties to develop new characterizations and efficient algorithms. We study the Hamiltonian cycle problem for a subclass of 3-connected planar graphs called planar-3-trees. We obtain a characterization of Hamiltonian planar-3-trees based on certain forbidden subgraphs. The characterization is used to obtain a linear-time algorithm to recognize this class of graphs. We extend this characterization and the algorithm to the larger class of planar chordal graphs. The complexity status of the Hamiltonicity problem for planar chordal graphs is thus settled. Our algorithm is a simple linear-time algorithm which significantly improves upon the constants. We consider two problems: embedding graphs in a minimum number of pages and ordering the vertices of graphs in the form of queue layouts. We show that the class of 2-trees requires 2 pages for a book embedding and 3 queues for a queue layout. The first result is new, and the latter result extends known results on subclasses of planar graphs. We present a simple linear-time sequential algorithm and a fast parallel algorithm to find the center of a tree. Our algorithm is based on a simple principle, which is different from the known algorithms. We extend this principle to determine the center of k-trees in O(v2)O(v^2)O(v2) time. We also enumerate some of the center graphs of planar-3-trees. We show that planar permutation graphs can be decomposed into 3-connected, 2-connected components, and caterpillars of hair length one. We show that in both triconnected and biconnected components, a maximal path forms a dominating path. We exploit this characterization and develop a linear-time ratio-2 approximation algorithm for the bandwidth minimization problem.