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.

Advertisements
Graph minors

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s