TOPICS
Search

Forbidden Topological Minor


A forbidden topological minor (also known as a forbidden homeomorphic subgraph) for a family of graphs is a graph H such that no member of the family contains a graph subdivision of H as a subgraph. For example, Kuratowski's theorem states that a finite undirected graph is planar iff it contains neither the complete graph K_5 nor the utility graph K_(3,3) as a topological minor.

The following table summarizes known forbidden topological minor obstructions for several embeddability families. The torus row includes planar graphs and records a partial list (Myrvold and Woodcock 2018, p. 10).

familyknown obstructions
planar graphK_5, K_(3,3)
projective planar graph103 graphs
graphs with a torus graph embedding>250000 graphs

See also

Forbidden Induced Subgraph, Forbidden Minor, Graph Subdivision, Kuratowski's Theorem, Topological Minor

Explore with Wolfram|Alpha

References

Myrvold, W. and Woodcock, J. "A Large Set of Torus Obstructions and How They Were Discovered." Elec. J. Combin. 25, P1.16, 2018. https://doi.org/10.37236/3797.

Referenced on Wolfram|Alpha

Forbidden Topological Minor

Cite this as:

Weisstein, Eric W. "Forbidden Topological Minor." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ForbiddenTopologicalMinor.html

Subject classifications