Path Graphs, PR-trees, and Split Decomposition
|Affiliation:||Wilfrid Laurier University|
|Room:||Mathematics & Computer Building (MC) 5158|
Path graphs are the intersection graphs of paths in trees. In this talk we introduce a new data structure, the PR-tree, to characterize the sets of path-tree models of path graphs. We then describe an O(nm) time algorithm to construct a PR-tree from a given graph via Split Decomposition (note: this matches the best known recognition algorithm for path graphs). From this algorithm we provide a new characterization of path graphs by split decomposition. Finally, we show that an implicit form of the PR-tree can be represented in O(n) space.
Note: for those familiar with PQ-trees and interval graphs (i.e., the intersection graphs of subpaths of a path), the PR-tree represents path graphs in the same way that the PQ-tree represents interval graphs (i.e., the PQ-tree of an interval graph G represents the set of all permutations of the maximal cliques of G where the maximal cliques incident with each vertex occur consecutively).
200 University Avenue West
Waterloo, ON N2L 3G1