2 added 189 characters in body

As compared to classes of graphs embeddable in other surfaces.

Some ways in which they're exceptional:

1. Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, mostly algebraic in the former case.) Before writing this question, I didn't know whether generalizations to graphs embedded in other surfaces existed, but some lucky Google-fu turned up some references -- in particular there seems to be a generalization of Whitney's criterion due to Jack Edmonds for general surfaces, although frustratingly I can't find the paper, and the main reference I found implies that there might be a small problem on the Klein bottle. Anyone know if Edmonds' result is as easy to prove as Whitney's?

2. Kuratowski's classic characterization of planar graphs by forbidden minors. Of course this does generalize to other surfaces, but this result is both incredibly deep and difficult (as opposed to the proof of Kuratowski, which is by no means trivial but is obtainable by a sufficiently dedicated undergraduate -- actually my working it as an exercise is largely what motivated the question) and is in some sense "essentially combinatorial" in that it applies to a wider class of families that aren't inherently topologically defined.

3. In the other direction of difficulty, the four-color theorem. It's apparently not difficult to show (except for the plane) that what turns out to be the tight upper bound on the chromatic number of a graph embeddable on a surface (other than, for whatever reason, the Klein bottle) is, in fact, an upper bound -- the problem is showing tightness! Whereas it's pretty much trivial to show that $K_4$ is planar (to be fair, though, tightness is easy to check for surfaces of small genus -- the problem's in the general case), but the four-color theorem requires inhuman amounts of calculation and very different, essentially ad-hoc methods.

I realize that the sphere has genus 0, which makes it unique, and has trivial fundamental group, which ditto, but while I imagine this information is related to the exceptionalness of the plane/sphere, it's not really all that satisfying as an answer. So, why is it that methods that work everywhere else tend to fail on the sphere?

Related questions: reasons-for-the-importance-of-planarity-and-colorability

1

# Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces.

Some ways in which they're exceptional:

1. Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, mostly algebraic in the former case.) Before writing this question, I didn't know whether generalizations to graphs embedded in other surfaces existed, but some lucky Google-fu turned up some references -- in particular there seems to be a generalization of Whitney's criterion due to Jack Edmonds for general surfaces, although frustratingly I can't find the paper, and the main reference I found implies that there might be a small problem on the Klein bottle. Anyone know if Edmonds' result is as easy to prove as Whitney's?

2. Kuratowski's classic characterization of planar graphs by forbidden minors. Of course this does generalize to other surfaces, but this result is both incredibly deep and difficult (as opposed to the proof of Kuratowski, which is by no means trivial but is obtainable by a sufficiently dedicated undergraduate -- actually my working it as an exercise is largely what motivated the question) and is in some sense "essentially combinatorial" in that it applies to a wider class of families that aren't inherently topologically defined.

3. In the other direction of difficulty, the four-color theorem. It's apparently not difficult to show (except for the plane) that what turns out to be the tight upper bound on the chromatic number of a graph embeddable on a surface (other than, for whatever reason, the Klein bottle) is, in fact, an upper bound -- the problem is showing tightness! Whereas it's pretty much trivial to show that $K_4$ is planar (to be fair, though, tightness is easy to check for surfaces of small genus -- the problem's in the general case), but the four-color theorem requires inhuman amounts of calculation and very different, essentially ad-hoc methods.

I realize that the sphere has genus 0, which makes it unique, and has trivial fundamental group, which ditto, but while I imagine this information is related to the exceptionalness of the plane/sphere, it's not really all that satisfying as an answer. So, why is it that methods that work everywhere else tend to fail on the sphere?