11
$\begingroup$

Could it have been foreseen that - exemplarily - planarity and colorability would turn out to be such important concepts in graph theory (there's almost no textbook on graphs without two chapters devoted to these concepts), or did time have to come and show it? The latter might imply that it's just a historical and evolutionary incident because there are loads of conceivable x-arities, y-abilities and other graph properties. (Maybe the importance of planarity and colorability just has to do with the contingent fact that we live on a (locally) two-dimensional plane and our need of maps?)

But maybe there are more objective reasons internal to mathematics that are formulable?

Related questions: Why-are-planar-graphs-so-exceptional; generalizations-of-planar-graphs;why-is-edge-coloring-less-interesting-than-vertex-coloring

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ Post-delivered motivation: I wonder why questions for "importance" - of concepts and theorems - are in general not taken as seriously as questions for hard facts. Wouldn't this - taking them equally important - be a real step further in the venture of mathematics? (I admit that questions for importance may be trivial - because importance may be obvious in special cases - or mistaken, because there is no importance at all of trivial concepts.) $\endgroup$
    – Hans-Peter Stricker
    Commented Jan 10, 2011 at 20:54
  • 5
    $\begingroup$ I think half of your question is asked (and answered) here: mathoverflow.net/questions/7114/… $\endgroup$
    – Tony Huynh
    Commented Jan 10, 2011 at 21:28
  • 2
    $\begingroup$ As for your question why "importance" questions enthuse people less than actual mathematics: maybe importance is just not the right kind of measure in pure maths. What does importance mean, anyway? If I talked to the man on the street, I would have a hard time convincing him that anything I do is important. I don't even believe it myself, when I view it in the context of global challenges that humanity is facing. If you are simply asking for a [big-list] of examples of applications of these concepts, then maybe you should say so. $\endgroup$
    – Alex B.
    Commented Jan 11, 2011 at 8:57
  • 2
    $\begingroup$ I guess what I am getting at is: can you give me an example of what a good answer to "are there objective reasons internal to mathematics for why concept XYZ is important" would look like? I am having a hard time imagining such an answer that wouldn't ultimately confuse mathematics and physics. $\endgroup$
    – Alex B.
    Commented Jan 11, 2011 at 8:59
  • 3
    $\begingroup$ That seems like a prototypical "time had to come and show it and it's just a historical and evolutionary incident" type of explanation, since it is ultimately a consequence of the order in which things were discovered, so I am afraid I am still confused by what the question is really asking. $\endgroup$
    – Alex B.
    Commented Jan 11, 2011 at 9:30

6 Answers 6

Reset to default
13
$\begingroup$

A few reasons for the importance of planarity having little to do with the need for maps:

  • A matroid is both graphic and co-graphic if and only if it is the graphic matroid of a planar graph

  • Planar graphs are the graphs with Colin de Verdiere invariant ≤ 3. As such they form a sequence with the trees, outerplanar graphs, planar graphs, and linklessly embeddable graphs.

  • The graphs of three-dimensional convex polyhedra are exactly the 3-connected planar graphs (Steinitz's theorem).

  • A minor-closed graph family has bounded treewidth if and only if it does not include all the planar graphs.

Improve this answer
$\endgroup$
3
  • $\begingroup$ David, did you mean "a planar graph as a minor" rather than "all planar graphs"? $\endgroup$
    – Gil Kalai
    Commented Jan 12, 2011 at 19:48
  • $\begingroup$ @Gil: I think David does indeed mean all planar graphs. The point is that the family $\mathcal{F}$ is minor-closed. Obviously if $\mathcal{F}$ contains all planar graphs, then it does not have bounded tree-width. Conversely, if $H \notin \mathcal{F}$ for some planar graph $H$, then since $\mathcal{F}$ is minor-closed, no graph in $\mathcal{F}$ can have an $H$-minor. But this implies graphs in $\mathcal{F}$ cannot have arbitrarily large grid-minors (since large enough grids contain $H$-minors). By the Grid Theorem, $\mathcal{F}$ does have bounded tree-width. $\endgroup$
    – Tony Huynh
    Commented Jan 12, 2011 at 21:09
  • $\begingroup$ oops sorry I had a mistake in exchanging the "does not" and the quntifier "all". $\endgroup$
    – Gil Kalai
    Commented Jan 13, 2011 at 7:24
12
$\begingroup$

I think that planarity figures more heavily in typical undergraduate courses than its importance at research level would warrant. I'm not saying that it's not important at research level, but I do think that it is noticeably less important than graph colouring. In particular, there are whole areas of graph theory where planarity doesn't come up, whereas colouring is fairly ubiquitous.

Why the emphasis at the undergraduate level? This is easily explained: the 4-colour theorem is a very famous result, and the 5-colour theorem has a nice proof that is suitable for an undergraduate course. There is nothing wrong with this at all: not everything that goes into an undergraduate course is there as direct training for research.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I guess even if one viewed the undergraduate syllabus as exclusively direct training for research, there would be some value in teaching irrelevant but beautiful mathematics: it would make people want to go into research in the first place, which in the early stages seems at least as important to me as equipping them with the necessary knowledge and skills. $\endgroup$
    – Alex B.
    Commented Jan 11, 2011 at 8:50
  • 1
    $\begingroup$ It's also as good a time as any to introduce Euler's formula. A nice bridge to algebraic topology via triangulations of surfaces. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 11, 2011 at 19:38
  • 3
    $\begingroup$ I don't think that in resaerch level mathematics planarity is less important than colorability. $\endgroup$
    – Gil Kalai
    Commented Jan 12, 2011 at 19:39
  • 1
    $\begingroup$ I thought that statement might be disputable and don't want to go to the wall to defend it. A much much weaker statement is true though, which is that I personally come across colouring a lot more often than planarity. (I realize that this proves nothing.) $\endgroup$
    – gowers
    Commented Jan 12, 2011 at 21:46
  • $\begingroup$ I certainly agree that "coloring" is sort of a very general concept that one comes accross more often and can be used to formulate various things. (Especially, if you do not restrict yourself to graph coloring in the restricted sense.) $\endgroup$
    – Gil Kalai
    Commented Jan 13, 2011 at 7:29
8
$\begingroup$

The main feature of Kurtowski's theorem on planar graphs at the time was that it connected two seemingly unrelated aspects of graphs, one topological in nature and the other combinatorial. Since then different authors have proved many theorems about planar graphs and they are now a fairly understood family. So I guess, the reasons for the importance of planarity have changed a bit with time.

Since many hard problems simplify a lot in the planar case this makes them a very good pedagogical tool to introduce when teaching/motivating various results in graph theory. As far as I know, planar graphs where the main reason to support Tutte's flow conjectures, for example. Other problems/conjectures where the planar case makes an interesting toy model are Fleischner's conjecture, circuit decomposition (Hajos), strong perfect graph conjecture, strong embedding conjecture, strong cycle double cover conjecture etc.

Part of motivation comes from topological graph theory, too. If you are interested in graphs as discretized version of surfaces, the planar case is probably the first you want to look into. Here the subject may jump to fields other than graph theory, though, and you may start to ask about properties under scalings and subdivisions (think of dimer models for example), but then there are more reasons that enter the picture for why the planar case is interesting, such as conformality for instance.

Improve this answer
$\endgroup$
4
$\begingroup$

I agree with the points of David Eppstein's answer on the important of planarity. I can add also my answer to a similar problem. We still need a good answer on why colorability is so important. As Tim Gowers said it is studied in many areas of graph theory and in also outside graph theory. Colorability is computationally intractible yet it is mathematically more tractable compared to other computational intractible questions like Hamiltonianity.

Let me try to suggest some answers on why graph colorability is important (I think it is a tentative and partial list):

1) It is a very easy to define and a very natural concept.

2) It is related to real life questions like scheduling and map coloring.

3) It is related to an important algebraic notion (that came from its study) the chromatic polynomial.

4) It led to many important generalizations. Like chosability.

Improve this answer
$\endgroup$
0
$\begingroup$

Mesh Analysis a method used to solve circuits only applies to planar circuits.

Improve this answer
$\endgroup$
0
$\begingroup$

There is the circle packing theorem, every connected simple planar graph is isomorphic to a circle packing.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .