Forbidden Topological Minor
Alternate name
Definition
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 K_5 and utility graph K_(3, 3) as a topological minor (homeomorphic subgraph). The following table summarizes some graph families which have forbidden topological minor obstructions.
Related terms
