#algorithms #mathematics #graph
epoch: 1267963380
Recently I learned a very beautiful result in graph theory, the graph minor theorem by Robertson & Seymour presented and proved in a series of 20 papers between 1983 and 1988. This theory is very rich and it has an immediate algorithmic consequence since there always exists a polynomial time algorithm to test a graph for a given minor.
One may define a class of graph properties called “hereditary” being closed under taking minors. Such a property can be expressed by a number of forbidden minors of a graph, minors it must not have. Surprisingly, the number of such minors is always finite.
Now, if you want to show your graph having some property you can do it like this:
1. Show the property to be hereditary.
2. Determine the forbidden minors (the harder part).
3. Show your graph not having these minors (algorithm always exists and is polynomial).
A simple example is a planarity test, proved by Wagner already in 1937. “A graph is planar iff it contains neither K5 nor K3,3 as a minor.” This is especially useful to show a graph not to be planar. All you have to do is to show it contains one of K5 or K3,3 as a minor! The theory of Robertson & Seymour is an extension of Wagner’s results but much deeper and with much more influence.
Powered by Tumblr; designed by Adam Lloyd and Ingo Schramm.
