Planar GraphYou are currentlybrowsing as guest. Click here to log in |
|
In graph theory, a planar graph is a graph which can be embedded in the plane. That is, it can be drawn on the plane so that its edges intersect only at its nodes. (see embedding).
Kuratowski's theorem states that a graph is planar if and only if it does not contain a topological $K_5$ or $K_{3,3}.$ Showing that $K_5$ and $K_{3,3}$ are non-planar is fairly easy using the Euler characteristic of the plane (V+R=E+2) but proving the other direction is decidedly awkward.
Last change to this page Full Page history Links to this page |
Edit this page (with sufficient authority) Change password |
Recent changes All pages Search |