Planar graph
Plane graphs can be encoded by combinatorial maps or rotation systems.
Instead of considering subdivisions, Wagner's theorem deals with minors: A minor of a graph results from taking a subgraph and repeatedly contracting an edge into a vertex, with each neighbor of the original end-vertices becoming a neighbor of the new vertex.
Klaus Wagner asked more generally whether any minor-closed class of graphs is determined by a finite set of "forbidden minors".
In the language of this theorem, K5 and K3,3 are the forbidden minors for the class of finite planar graphs.
In practice, it is difficult to use Kuratowski's criterion to quickly decide whether a given graph is planar.
However, there exist fast algorithms for this problem: for a graph with n vertices, it is possible to determine in time O(n) (linear time) whether the graph may be planar or not (see planarity testing).
Euler's formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and f is the number of faces (regions bounded by edges, including the outer, infinitely large region), then As an illustration, in the butterfly graph given above, v = 5, e = 6 and f = 3.
Euler's formula can also be proved as follows: if the graph isn't a tree, then remove an edge which completes a cycle.
In a finite, connected, simple, planar graph, any face (except possibly the outer one) is bounded by at least three edges and every edge touches at most two faces, so 3f <= 2e; using Euler's formula, one can then show that these graphs are sparse in the sense that if v ≥ 3: Euler's formula is also valid for convex polyhedra.
Not every planar graph corresponds to a convex polyhedron in this way: the trees do not, for example.
More generally, Euler's formula applies to any polyhedron whose faces are simple polygons that form a surface topologically equivalent to a sphere, regardless of its convexity.
It follows via algebraic transformations of this inequality with Euler's formula v – e + f = 2 that for finite planar graphs the average degree is strictly less than 6.
We say that two circles drawn in a plane kiss (or osculate) whenever they intersect in exactly one point.
This result provides an easy proof of Fáry's theorem, that every simple planar graph can be embedded in the plane in such a way that its edges are straight line segments that do not cross each other.
If one places each vertex of the graph at the center of the corresponding circle in a coin graph representation, then the line segments between centers of kissing circles do not cross any of the other edges.
The term "dual" is justified by the fact that G** = G; here the equality is the equivalence of embeddings on the sphere.
[6] If a maximal planar graph has v vertices with v > 2, then it has precisely 3v – 6 edges and 2v – 4 faces.
Apollonian networks are the maximal planar graphs formed by repeatedly splitting triangular faces into triples of smaller triangles.
A theorem similar to Kuratowski's states that a finite graph is outerplanar if and only if it does not contain a subdivision of K4 or of K2,3.
A Halin graph is a graph formed from an undirected plane tree (with no degree-two nodes) by connecting its leaves into a cycle, in the order given by the plane embedding of the tree.
[9] An upward planar graph is a directed acyclic graph that can be drawn in the plane with its edges as non-crossing curves that are consistently oriented in an upward direction.
Tutte's spring theorem even states that for simple 3-vertex-connected planar graphs the position of the inner vertices can be chosen to be the average of its neighbors.
Every simple outerplanar graph admits an embedding in the plane such that all vertices lie on a fixed circle and all edges are straight line segments that lie inside the disk and don't intersect, so n-vertex regular polygons are universal for outerplanar graphs.
[16] This result has been used to show that planar graphs have bounded queue number, bounded non-repetitive chromatic number, and universal graphs of near-linear size.
It also has applications to vertex ranking[17] and p-centered colouring[18] of planar graphs.
A map graph is a graph formed from a set of finitely many simply-connected interior-disjoint regions in the plane by connecting two regions when they share at least one boundary point.
Obviously, if the graph can be embedded without crossings into a (orientable, connected, closed) surface with genus g, it can be embedded without crossings into all (orientable, connected, closed) surfaces with greater or equal genus.
This can be interpreted as saying that it is possible to make any electrical conductor network with a two-sided circuit board where electrical connection between the sides of the board can be made (as is possible with typical real life circuit boards, with the electrical connections on the top side of the board achieved through pieces of wire and at the bottom side by tracks of copper constructed on to the board itself and electrical connection between the sides of the board achieved through drilling holes, passing the wires through the holes and soldering them into the tracks); one can also interpret this as saying that in order to build any road network, one only needs just bridges or just tunnels, not both (2 levels is enough, 3 is not needed).
