Algorithms for testing planarity of chordal graphs and hamiltonicity of planar chordal graphs.

Abstract

Design and analysis of graph algorithms is an active research area in Computer Science. Designing efficient algorithms for graph problems is both challenging and rewarding from the point of view of theory and applications. In this report, we present some new algorithmic results on planar chordal graphs. We also present certain additional results in algorithmic graph theory. Chapter 1 We present a summary of existing notions and results pertaining to chordal graphs, planarity, and hamiltonicity. Chapter 2 We establish conditions for the existence, in a chordal graph, of subgraphs homeomorphic to:

Complete graphs Complete bipartite graphs Wheels

Using these results, we develop a new characterization of planar chordal graphs. This characterization yields a simple linear-time planarity testing algorithm for chordal graphs. We also show that our results can be used to obtain simple polynomial-time algorithms for the Fixed Subgraph Homeomorphism problem on chordal graphs. Chapter 3 We develop new results on the hamiltonicity of chordal graphs. Using these results, we develop an O(n) algorithm for the Hamiltonian cycle problem on planar chordal graphs. Chapter 4 We present two additional results of algorithmic interest:

A new approach to the design of an optimal parallel algorithm for the lowest common ancestor problem. An improved algorithm for the Subgraph Listing problem.

We introduce a new strategy for scanning the vertices and edges of a graph. Based on this strategy, we develop a fast algorithm for listing all complete subgraphs of fixed order. This algorithm is as efficient as the best-known algorithm for this problem and performs much better on sparse graphs.