A recognition algorithm for the intersection graphs of paths in trees

Let F be a finite family of non-empty sets. An undirected graph G is an intersection graph for F if there is a one-to-one correspondence between the vertices of G and the sets of F such that two sets have a non-empty intersection exactly when the corresponding vertices are adjacent in G. If this is the case then F is said to be an intersection model for the graph G. If F is a family of paths within a tree T, then G is called a path graph. This paper proves a characterization for the path graphs and then gives a polynomial time algorithm for their recognition. If G is a path graph the algorithm constructs a path intersection model for G.