Talk:Planar graph

From Wikipedia, the free encyclopedia

Planar graph is a former featured article candidate. Please view the links under Article milestones below to see why the nomination failed. For older candidates, please check the archive.

November 8, 2005

Featured article candidate

Not promoted

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

Mid Priority

Field: Discrete mathematics

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Geometry guy 22:42, 17 June 2007 (UTC)

1 old comments
2 Fourth picture
3 infinite graphs
4 Modifications
5 Newbie
6 Plane graph
7 Too technical
8 Genus
9 Maximal Planar Graphs
10 Kuratowski's theorem

[edit] old comments

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

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

[edit] Genus

The article should probably explain somewhere the equivalence between "embeddable in a plane" and "embeddable in a sphere", mention that planar graphs are graphs of genus zero and hint to the fact that the genus gives a finer and more useful distinction than planar / non-planar. I would add this myself if I knew how to best present it. Ideas welcome. Morana (talk) 21:08, 7 April 2008 (UTC)

[edit] Maximal Planar Graphs

~~This is just a little something for everyone. It's a derivation I saw, but can't find a RS to confirm it. If we could it would be a good contribution to the article. So, the derivation is this:~~

~~Take any maximal planar graph G. It follows $V(G),E(G),F(G):\rightarrow V,3(V-2),2(V-2)$~~

~~Basically, the number of faces and edges can be derived from the number of vertices and visa versa. Has anyone seen anything on this before?~~ InfoNation¹⁰¹ | talk | 18:35, 22 April 2008 (UTC)

Nevermind. Didn't catch that part on the page until after a couple times through. InfoNation¹⁰¹ | talk | 18:38, 22 April 2008 (UTC)

[edit] Kuratowski's theorem

Either we need to clarify that a graph can be a subdivision of itself (subdividing zero times) or we need to add to the statement of Kuratowski's theorem that a graph can't also contain a subgraph that is isomorphic to K₅, etc. The article's definition of subdivision mentions repeating subdividing zero or more times which doesn't mean subdividing zero times. The concept of subdividing links to Homeomorphism (graph theory), which may make this all clear if I had studied it and thus been able to understand the article, but I haven't. The second option above is the way I've seen it in textbooks, which is what made me assume a graph is not a subdivision of itself. - Taxman ^Talk 14:43, 31 May 2008 (UTC)

Your assumption is mistaken. A graph is allowed to be a subdivision of itself. See the word "zero" in the phrase you quoted, "subdividing zero or more times". —David Eppstein (talk) 18:35, 31 May 2008 (UTC)

But you missed the emphasis above making the sentence mean something different. Here's the whole phrase from the article: "A subdivision of a graph results from inserting vertices into edges (for example, changing an edge •——• to •—•—•) and repeating this zero or more times.". That zero refers to repeating the subdivision process, not subdividing zero times. That is what I was referring to above. So, if you're correct, the sentence needs to be adjusted, but I don't yet see how to do this without being unwieldy. - Taxman ^Talk 03:01, 1 June 2008 (UTC)

Take out the word "repeating" that you find so confusing, and just say that the edge is subdivided zero or more times? —David Eppstein (talk) 03:44, 1 June 2008 (UTC)

It's not that it's confusing, it's wrong. Simple enough fix though, thanks. - Taxman ^Talk 13:02, 1 June 2008 (UTC)