## You are here

Homeplanar graph

## Primary tabs

# planar graph

all

# Description

A *planar graph* is a graph which can be drawn on a plane (a flat 2-d surface) or on a sphere, with no edges crossing. When drawn on a sphere, the edges divide its area in a number of regions called faces (or “countries”, in the context of map coloring). When drawn on a plane, there is one *outer country* taking up all the space outside the drawing. Every graph drawn on a sphere can be drawn on a plane (puncture the sphere in the interior of any one of the countries) and vice versa. Statements on map coloring are often simpler in terms of a spherical map because the outer country is no longer a special case.

The number of faces (countries) equals $c+1$ where $c$ is the *cyclomatic number*, $c=m-n+k$ (where $m$ is the number of edges, $n$ the number of vertices, and $k$ the number of connected components of the graph). All this holds equally for planar multigraphs and pseudographs.

No complete graphs above $K_{4}$ are planar. $K_{4}$, drawn without crossings, looks like :

$\xymatrix{&A\ar@{-}[d]\ar@{-}[ddl]\ar@{-}[ddr]&\\ &B\ar@{-}[dl]\ar@{-}[dr]&\\ C\ar@{-}[rr]&&D}$ |

Hence it is planar (try this for $K_{5}$.)

A straight line drawing of a planar graph is a drawing in which each edge is drawn as a straight line segment. Every planar graph has a straight line drawing. This result was found independently by Wagner, Fáry and Stein. Schnyder improved this further by showing how to draw any planar graph with $n$ vertices on an integer grid of $O(n^{2})$ area.

# Definition

Ideally, this definition would just formalize what was described above. It will not, exactly. It will formalize the notion of a graph *with an embedding into the plane*.

###### Definition.

Let $M$ be a topological manifold. Then a *graph on $M$* is a pair $(G,\iota)$, where

1. $G$ is a multigraph,

2. $\iota$ is a function from the graph topology of $G$ into $M$, and

3. $\iota$ is a homeomorphism onto its image.

A *plane graph* is a graph on $\mathbb{R}^{2}$.

A *planar graph* is a graph $G$ that has an embedding $\iota$ making $(G,\iota)$ into a plane graph.

The most usual question for which this definition finds a use is “can the following graph $G$ be made into a graph on $M$?”. When $M$ is the plane, this is usually phrased as “Is $G$ a planar graph?”. Wagner’s theorem provides a simple criterion for answering this question. When $M$ is a torus, the answer changes: the complete bipartite graph $K_{{3,3}}$ can be made into a graph on the torus.

A graph on a manifold has a notion of “face” as well as the usual graph notions of vertex and edge.

## Mathematics Subject Classification

05C10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## planar graphs and embeddings

## planar graph

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 $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…

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

## Re: planar graphs and embeddings

> 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

## Re: planar graphs and embeddings

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

## Re: planar graphs and embeddings

Oh, there is standard terminology for this.

Planar graph -- graph embeddable in plane

Plane graph --- graphe embedded in plane

Boris

## Re: planar graphs and embeddings

> 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/

## Re: planar graphs and embeddings

Please see my reply just posted to bhukh, also has message to you.

--regards, marijke

http://web.mat.bham.ac.uk/marijke/

## Unicity of dual

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...