Re: Plane colorings
Posted: Tue Mar 20, 2012 8:31 am UTC
jestingrabbit wrote:Sadly, I don't think they're closed under taking minors, so we can't rely on
There are clearly a few easy forbidden subgraphs, like K_4, or a square pyramid, but that's not going to get us anywhere quickly imo.
It is the right question though. The answer is probably something to do with triangles.
/stating the obvious.
I didn't ask for an efficient algorithm, it doesn't have to be as simple as "check whether the graph contains a copy of X, Y, or Z". Just an algorithm witnessing that the problem is decidable. And it can't possibly fail to be decidable, right? That would just be weird.
One avenue for finding an algorithm would be noticing that to finding an embedding of an n-vertex graph is equivalent to finding a real solution for a particular system of polynomial equations in 2n variables (or 2n-4, since WLOG the first two points are (0,0) and (0,1)). Are there known algorithms for this? I'm pretty sure that if a solution exists, a solution can be found inside the algebraics, and you should be able to bound the degrees of the minimal polynomials. If you can also bound the coefficients of the minimal polynomials, you can probably do brute-force checking with a computer algebra system.
* * *
As a side-note, the class of embeddable graphs is so badly not closed under minors that every graph is the minor of an embeddable graph. Given any graph, if you replace all edges with paths of length 2, the resulting graph is embeddable.