Talk:Planar graph

From Wikipedia, the free encyclopedia

This article is a former featured article candidate. Please view its sub-page to see why the nomination failed. For older candidates, please check the archive.

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

1 Fourth picture
2 infinite graphs
3 Modifications
4 Newbie
5 Plane graph
6 Too technical

[edit] 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)

[edit] 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.

With this definition, the reunion of all infinite graphs is not a set (under ZFC) and thus has no cardinal --81.202.212.241 17:28, 3 October 2006 (UTC)

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)

More-or-less, yes. See "Planarity and Duality of Finite and Infinite Graphs", Carsten Thomassen, J. Comb. Theory B, 29 244-271 (1980).

[edit] 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

K 5

IS a minor of the graph isomorphic to

K 3,3

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)

The difference is that a minor of $K 5$ is not necessarily a subdivision of $K 5$ . It happens that a minor of $K 5$ is either a subdivision of $K 5$ or a subdivision of $K 3,3$ and thus Wagner and Kuratowski statements are equivalent. If you consider Hadwiger conjecture (a graph with chromatic number k has a $K k$ minor) and Hajos conjecture (a graph with chromatic number k includes a subgraph homeomorphic to $K k$ ) then the difference is essential: the first conjecture is still open while the second is false. It has also to be noticed that Wagner's characterization was motivation of Wagner's conjecture, later proved by Robertson and Seymour in a long series of papers: any minor closed familly of finite graphs is characterized by a finite set of forbidden minors.

--pom 00:32, 2 March 2006 (UTC)

Seems to me that a minor of

K 5

has at most 5 vertices, so it can't be a subdivision of

K 3,3

. Maybe it is the other way around? --Zero 12:41, 2 March 2006 (UTC)

Sorry, I "took my feet in the carpet" as we say in french. The good formulation is that if a graph has a

K 5

minor, it does not need to include a subdivision of

K 5

. However, graphs with a

K 5

minor include a subdivision of

K 5

K 3,3

pom 16:13, 2 March 2006 (UTC)

[edit] Newbie

I'm new to this, and I just want someone to clarify what is meant by "redrawing" the second picture. If you redraw it so that it is planar, could it look like this?:

.___________.
|\         //
| \      / /
|  \   /  /
|   \.   /
|   /  /
|  /  /
| / /
|//
.

Well, something like that? Sorry, I'm not very good at ASCII art. Chris53516 02:55, 5 July 2006 (UTC)

I think I answered my own question. See Four color theorem#Formal statement in graph theory for the graphic. Chris53516 03:01, 5 July 2006 (UTC)

[edit] Plane graph

No exact definition was supplied for plane graph - I hope mine is good enough. Rp 22:26, 5 July 2006 (UTC)

Actually, the usual definition of a plane graph is a graph embedded in the plane (up to topological equivalence). A plane embedding is defined by the circular order of the edges around the vertices (which define an embedding in the sphere) and the description of the unbounded face. pom 19:08, 3 October 2006 (UTC)

[edit] Too technical

I remember simplifying the 1st paragraph of the article in March. But already the second and third paragraphs are way too technical. This article should be readable by youngsters curious of mathematics. I suggest we try to present elementary notions and results (e.g., proof that K3,3 is not planar based on Euler equation for planer graphs) without using cryptic language. PhS 15:02, 20 November 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../p/l/a/Talk%7EPlanar_graph_20a6.html"

Category: Wikipedia featured article candidates (contested)