A graph is a forbidden topological minor (also known as a forbidden homeomorphic subgraph) if its presence as a homeomorphic subgraph
of a given graph (i.e., there is an isomorphism from some graph
subdivision of one graph to some subdivision of the other) means it is not a
member of some family of graphs. For example, Kuratowski's
theorem states that a graph is planar if it does
not contain the complete graph and utility graph
as a topological minor (homeomorphic subgraph).
The following table summarizes some graph families which have forbidden topological minor obstructions.
family | obstructions |
planar graph | |
projective planar graph | 103 graphs |
toroidal graph |