Tutte seminar - Steve Chaplick

Friday, April 13, 2012 3:30 pm - 4:30 pm EDT (GMT -04:00)

Path Graphs, PR-trees, and Split Decomposition

Speaker: Steve Chaplick
Affiliation: Wilfrid Laurier University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

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).