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 | graphs |