PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Medium Entry average rating: No information on entry rating
planar graph (Definition)

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 :

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & A\ar@{-}[d] \ar@{-}[ddl] \ar@{-}[ddr] & \ & B\ar@{-}[dl] \ar@{-}[dr] & \ C \ar@{-}[rr] & & D } } \end{xy}$

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

Normally, the only manifolds $ M$ that are of interest are two-dimensional.

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.



Anyone with an account can edit this entry. Please help improve it!

"planar graph" is owned by archibal. [ full author list (5) | owner history (1) ]
(view preamble)

View style:

See Also: Wagner's theorem, Kuratowski's theorem, crossing lemma, crossing number, four-color conjecture

Other names:  planar
Also defines:  plane graph

Attachments:
example of planar graph with two different embeddings into the plane (Example) by archibal
Log in to rate this entry.
(view current ratings)

Cross-references: vertex, complete bipartite graph, torus, Wagner's theorem, manifolds, image, onto, homeomorphism, graph topology, function, topological manifold, embedding, grid, integer, line segment, complete graphs, pseudographs, multigraphs, connected components, vertices, interior, coloring, faces, regions, number, area, edges, sphere, surface, flat, plane, graph
There are 34 references to this entry.

This is version 9 of planar graph, born on 2002-02-05, modified 2006-10-17.
Object id is 1826, canonical name is PlanarGraph.
Accessed 14805 times total.

Classification:
AMS MSC: 05C10 (Combinatorics :: Graph theory :: Topological graph theory, imbedding)
Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy
planar graphs and embeddings by archibal on 2004-03-30 23:54:21
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?
[ reply | up ]
Interact
post | correct | update request | add derivation | add example | add (any)