Graph minors

A graph H is a minor of a graph G if H is isomorphic to a graph obtained by contracting edges, removing edges and/or removing isolated vertices from G. For example the graph with two vertices and one edge is a minor of any graph with at least one edge.

Problem: Fix a graph H. Find a polynomial time algorithm that decides if a given graph G has H as one of its minors. The algorithm must be polynomial in the number of vertices of G.

Notice that such an algorithm proves that planarity of a graph can be decided in polynomial time.

Graph minors

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s