Characterizations and algorithms for topological containment of wheel graphs
by Rebecca Robinson
Abstract: Topological containment is an important substructure relation in graph theory. A graph G is
said to topologically contain another pattern graph H if a graph isomorphic to H can be
obtained from G by performing a series of deletions and contractions, where contractions are
limited to edges with at least one endvertex of degree 2.
The problem of topological containment has been shown by Robertson and Seymour to be
polynomial-time solvable for any fixed pattern graph. However, practical characterizations
and algorithms have only been developed for a few small pattern graphs. In this talk, I will
look at some previous results on topological containment for particular pattern graphs. I will
also talk about two new results: one characterizing graphs that do not topologically contain
the wheel with six spokes, and one that gives a characterization (up to bounded size pieces)
of graphs that do not topologically contain the wheel with seven spokes.
For More Information: contact: David Wood. email: firstname.lastname@example.org