Intersection Graph Algorithms

Abstract

An intersection graph for a set of sets $C$ is a graph $G$ together with a bijection from the vertices of $G$ to $C$ such that distinct vertices in $G$ are adjacent if and only if their images under this bijection intersect. Of particular interest have been the classes of chordal graphs, the intersection graphs of sets of subtrees of a tree, and interval graphs, the intersection graphs of sets of intervals of the real line. I examine another class of intersection graphs, the class of directed path graphs: intersection graphs of sets of paths in a directed tree. This class properly contains the class of interval graphs, and is properly contained by the class of chordal graphs. I give a linear time algorithm for recognizing directed path graphs and for constructing intersection representations, and a polynomial time algorithm for deciding directed path graph isomorphism. Both algorithms use a data structure called a partial path tree, which is a kind of skeletal representation of the clique hypergraph of a directed path graph. I present linear time algorithms for finding partial path trees with specific roots and for finding partial path trees with arbitrary roots. I prove that partial path trees with identical roots are identical. Using this fact I develop a polynomial time algorithm for directed path graph isomorphism.