Fork me on GitHub
Math for the people, by the people.

User login

planar graph

Defines: 
plane graph
Synonym: 
planar
Type of Math Object: 
Definition
Major Section: 
Reference

Mathematics Subject Classification

05C10 no label found

Comments

planar graph

\xyoption

all

Suppose that a graph can be embedded in the plane. (”is a planar graph”). Are all these embeddings isomorphic? (equivalent by way of a homeomorphism of the plane?) I don’t think so: the ”outside” face is different. Is this true on the sphere? It’s certainly not true on the torus or more elaborate compact manifold.

Even if these are not isomorphic, are the graphs obtained by taking the duals isomorphic? To be clear, what I am asking is this: Let GGG be a graph, and let ρ1subscriptρ1\rho_{1} and ρ2subscriptρ2\rho_{2} be embeddings into the sphere. Then (G,ρ1)Gsubscriptρ1(G,\rho_{1}) has a dual (G1,γ1)subscriptG1subscriptγ1(G_{1},\gamma_{1}) obtained by interchanging vertices and faces (well, really by a topological construction). But (G,ρ2)Gsubscriptρ2(G,\rho_{2}) also has a dual (G2,γ2)subscriptG2subscriptγ2(G_{2},\gamma_{2}); are G1subscriptG1G_{1} and G2subscriptG2G_{2} isomorphic as graphs? Using the Euler characteristic, you can show that they have the same number of vertices, but…

Does anyone know of a graph theory text that is both specific and rigorous on the subject?

> Suppose that a graph can be embedded in the plane. ("is a
> planar graph"). Are all these embeddings isomorphic?
> (equivalent by way of a homeomorphism of the plane?) I
> don't think so: the "outside" face is different. Is this
> true on the sphere? It's certainly not true on the torus or
> more elaborate compact manifold.
Here is a counterexample to the statement that all embeddings of planar graph in sphere are ambiently homeomorphic to each other (i.e., equivalent by homeomorphism of the sphere). Consider the following graph (use monospace font):

A B G
+-----+-----+
| /|\ |
| / | \ |
| E+ | +F |
| \ | / |
| \|/ |
+-----+-----+
C D H

+'s signify the vertices of the graph.

The above is one of the ways to draw it on the sphere. Another way is
when you flip the vertex E to the other side of BD. To see that these are not ambiently homeomorphic just note that E and F are in different ``insides'' and ``outsides'' of ABCD. That should be enough to convince that is really a counterexample. To make the proof absolutely rigourous you can appeal to Jordan curve theorem.

The proof above depends on the labelling of the graph. If you insist that you graph is unlabelled, then just attach 100 hanging edges to A, 200 hanging edges to B, 300 hanging edges to C, etc. Then A is the unique vertex of degree 102, B is the unique vertex of degree 205, etc, so you effectively labelled the vertices.

> Even if these are not isomorphic, are the graphs obtained by
> taking the duals isomorphic? To be clear, what I am asking
> is this: Let $G$ be a graph, and let $\rho_1$ and $\rho_2$
> be embeddings into the sphere. Then $(G,\rho_1)$ has a dual
> $(G_1,\gamma_1)$ obtained by interchanging vertices and
> faces (well, really by a topological construction). But
> $(G,\rho_2)$ also has a dual $(G_2,\gamma_2)$; are $G_1$ and
> $G_2$ isomorphic as graphs? Using the Euler characteristic,
> you can show that they have the same number of vertices,
> but...
This is false as well. Consider the following graph (use monospace font again):

+-----------------------+
| |
+-------+ +-+
| | | |
| +---------+-+ +-+
| | | | |
| +---------+-+ +-+
| | | |
+-------+ X +-+
| |
+-----------------------+

Its dual has the property that there is a vertex which is adjacent to every other (the fact in this graph to which it corresponds is marked by X). Now consider the following isomorphic graph:

+-----------------------+
+-------+ |
+--+ | +-+
| | | | |
| +-+ | +-+
| | | | |
| +-+ | +-+
| | | | |
+--+ | +-+
+-------+ |
+-----------------------+

In this drawing there is no vertex in dual graph that is adjacent to every other.

>
> Does anyone know of a graph theory text that is both
> specific and rigorous on the subject?
Depends on what meaning you ascribe to the words ``specific'' and ``rigorous''. Also, depends on what kind of graph theory you are interested in. The questions you are asking refer to the so-called topological graph theory. The only book I read myself which is solely devoted to topological graph theory is ``The Four-Color Problem: Assaults and Conquest'' by Thomas L. Saaty and Paul C. Kainen. It is a rather nice reading, but it has very little depth, and authors were trying to make the book accessible to readers with very modest background (read: no topology). Try typing 05C10 in MathSciNet and see what books you find.

Boris

> Here is a counterexample to the statement that all
> embeddings of planar graph in sphere are ambiently
> homeomorphic to each other (i.e., equivalent by
> homeomorphism of the sphere). Consider the following graph
> (use monospace font):
...
> This is false as well. Consider the following graph (use
> monospace font again):
...

Great! Thanks! I'll integrate something to the effect in the entry.

> > Does anyone know of a graph theory text that is both
> > specific and rigorous on the subject?
> Depends on what meaning you ascribe to the words
> ``specific'' and ``rigorous''. Also, depends on what kind of
> graph theory you are interested in. The questions you are
> asking refer to the so-called topological graph theory. The
> only book I read myself which is solely devoted to
> topological graph theory is ``The Four-Color Problem:
> Assaults and Conquest'' by Thomas L. Saaty and Paul C.
> Kainen. It is a rather nice reading, but it has very little
> depth, and authors were trying to make the book accessible
> to readers with very modest background (read: no topology).
> Try typing 05C10 in MathSciNet and see what books you find.

Well, all the books on graph theory I've read (which has not been many) and all the courses I took (which was also not many, and they were long ago) simply defined a planar graph to be "a graph that can be drawn on the plane without edges crossing" and then talked about "the" dual graph. This is just wrong...

I'll hit the library soon and see if I can find out some standard terminology for this, so that I can fix the entry "planar graph". So far my impression is that "planar graph" is used to mean both "a graph that can be embedded into the plane" and "a graph, along with an embedding into the plane" (which is equivalent to some combinatorial thing vaguely like a simplicial complex).

Oh, there is standard terminology for this.

Planar graph -- graph embeddable in plane
Plane graph --- graphe embedded in plane

Boris

> Oh, there is standard terminology for this.
>
> Planar graph -- graph embeddable in plane
> Plane graph --- graphe embedded in plane

Yes, that's also the way i learned it.

BTW i would disagree with the previous speaker that Saaty & Kainen is not "deep" because it's low on topological content. S&K has pretty interesting sections on Whitney and Tutte's wotk on matroids, vector spaces on edges.

Fritsch & Fritsch, The Four-Color Theorem, Springer 1998, ISBN 0-387-98497-6 goes all out on topology if you like that sort of thing (never to leave the plane for surfaces of higher genus, but very detailed on the minuti\ae\ of embedding, Jordan thm and all that). IM-not-so-HO it's misguided, graphs and coloring is not in final analysis about continuous manifolds (although there are interesting links with coloring and genus of embedding surface) but an essentially discrete subject.

Oh before i forget... Archibal, i added a bit to the Planar Graph subject just now (well you did make it world editable). Have a look, see what you think.

--regards, marijke
http://web.mat.bham.ac.uk/marijke/

Please see my reply just posted to bhukh, also has message to you.
--regards, marijke
http://web.mat.bham.ac.uk/marijke/

Given a planar graph, we can have different embeddings that correspond to non isomorphic dual graphs.

My question is the converse : given two plane graphs with the same dual graph, can we conclude that they are isomorphic ? Sphere-isomorphic ?
Or that they are 2 embeddings of the same planar graph ?

I tried hard to find these answers, but it seems that all papers and website are interested in the other way relation...

Subscribe to Comments for "planar graph"