Talk:Planar graph

In Kazimierz Kuratowski, the following version of Kuratowski's theorem was given:

a graph with no vertices of order 2 is nonplanar if and only if it contains a copy of K₅ or K_3,3.

This statement is incorrect. Take K₅, pick one of its edges, say A --- B, and introduce two new vertices X and Y to change the edge to

          Y  
          | 
          | 
    A --- X --- B

The resulting graph is non-planar, has no degree-two vertex, and has no subgraph of form K₅ or K_3,3. AxelBoldt 00:58 13 Jun 2003 (UTC)

---

I removed the paragraph

For a connected planar graph G we may construct a graph whose vertices are the regions into which G divides the plane (including a single external region). The edges represent adjacency of regions: there is one for each edge of G, and can be shown as crossing it. The resulting graph G* is naturally also planar: it is called the planar dual graph, or just dual graph, with respect to the given plane embedding of G. We have G** = G, justifying the name dual.

The case of a tree shows that G** need not equal G, and so this operation needs to be defined differently to deserve the name "dual". Maybe it should be restricted to graphs arising from simple polyhedra? AxelBoldt 19:57, 26 Oct 2003 (UTC)

OK, the double dual clearly doesn't work unless crossing an edge takes you into a different region. That looks like the only condition?

Charles Matthews 06:43, 27 Oct 2003 (UTC)

I think so, if we allow our graphs to have multiple edges. AxelBoldt 14:24, 27 Oct 2003 (UTC)

The dual graph is always taken to be a multigraph and the imbedding in the plane is important. The dual of a tree is a single vertex with a whole lot of loops on it (one loop for each edge of the tree), but the way that the loops are imbedded in the plane (which loops are inside which other loops) encodes the tree structure so it is still true that G** = G. --Zero 14:59, 27 Oct 2003 (UTC)

Aha! Now we're getting somewhere. We only need a clear description of how to get from one embedded connected multigraph to the (or a?) dual embedded multigraph.

If G is the graph consisting of a single edge connecting two vertices, would G* be the one-vertex graph with two separate loops, or with one loop inside the other? Or do we work on the sphere where the two are the same? AxelBoldt 09:40, 28 Oct 2003 (UTC)

It's a vertex with one loop; you put a vertex in the distinct regions (only 1) and where there's an edge (only 1) you cross it, so you only have a loop. Dysprosia 10:03, 28 Oct 2003 (UTC)

There is always one edge in G** for each edge of G. The dual of the graph you mention has one vertex with one loop on it. To answer the last part, the imbedding is regarded as being on the sphere for most purposes. That's one of the reasons it's a bit hard to define the concept of a dual precisely without more background theory on the nature of imbeddings. --Zero 10:10, 28 Oct 2003 (UTC)

Oops, above I meant the graph G with three vertices, connected by two edges. It seems there are the two possibilities for the dual I mentioned above; but if we do work on the sphere they are the same and all is well. AxelBoldt 10:25, 28 Oct 2003 (UTC)

If you mean something like

*
 \
  *
 /
*

the dual will be

  _
 /  \
| * |
\  /
  o  *
 /  \
| * |
 \_/

(the *s are to show the relative position of the previous vertices) Like Zero mentioned, we have an edge crossing for an edge. We can't have just one loop around that apex vertex. Dysprosia 10:28, 28 Oct 2003 (UTC)

    __________ 
   /   _      \
  |   /  \     | 
  \   | * |    |
   \  \  /     |
    -- o  *   /
        \    / 
         ----
       * 

would be another possibility for the dual; on a sphere, the two are equivalent, but not in the plane. AxelBoldt 11:41, 28 Oct 2003 (UTC)

Yepyep :) These graphs are isomorphic, I think, too... Dysprosia 11:41, 28 Oct 2003 (UTC)

---

If we allow infinite planar graphs: does Kuratowski remain true for countably infinite graphs? How about the four-color theorem? AxelBoldt 13:10, 30 Oct 2003 (UTC)

A graph is k-colorable if all its finite subgraphs are k-colorable, so 4CT is true even without the "countable". I think Kuratowski is more complicated. --Zero 13:41, 30 Oct 2003 (UTC)

---

Kuratowski showed:

that the only non-planar graphs are those that contain a subdivision of K₅ or K_3,3 obtained by replacing edges with paths.

The G** = G equality holds even for simple connected duals iff the edge-connectivity of G is strictly greater than 2. --- John Fremlin <john@fremlin.de> Sun Jan 18 03:00:37 GMT 2004

Fourth picture

I believe that it is possible to redraw the fourth picture without any intersections by moving the top-right point to a point a little to the right of the lower-left, and moving the top-left to down below the bottom. Is this an error, or am I missing something?

--Miko 10:45, July 23, 2005 (UTC)

If you referring to the K3,3 picture, you are mistaken. It is impossible. --Zero 11:11, 23 July 2005 (UTC)

It is possible to draw this graph with only one crossing. I can't understand your description, but if you take a closer look at your redrawing you should be able to find your crossing. Deco 21:31, 23 July 2005 (UTC)

infinite graphs

Does Kuratowski's theorem apply to infinite graphs? Infinite trees are mentioned - what other types of infinite graphs are there? It's clear that there are $2^{\aleph _{0}}$ infinite graphs - how many infinite planar graphs are there?

Define "infinite graph" first. mikka (t) 19:41, 16 August 2005 (UTC)

The definition is the same. A graph is a set V of vertices, and a set E of edges, each of which is a set of two vertices. If V is infinite, the graph is infinite. The graph, whether finite or infinite, is planar if it can be embedded in the plane so that no edges intersect.

Graph theorists often talk about the graph K_ω, for example; this is the graph which has a countably infinite set of vertices, and an edge between each distinct pair of vertices. -- Dominus 14:26, 8 November 2005 (UTC)

Modifications

The characterization by forbidden minors is due to Wagner, not to Kuratowksi (both characterization have been published in 1937). I have added the reference to Wagner's paper.

I have added several links to further characterizations, but many are missing.

What exactly is the difference between the two statements? A subgraph homeomorphic to $K_{3,3}$ or $K_{5}$ IS a minor of the graph isomorphic to $K_{3,3}$ or $K_{5}$. I have always heard both statements referred to interchangeably as Kuratowski's Theorem. I guess I'll leave it this way for now. ---SpaceMoose 12:15, 22 February 2006 (UTC)