Editing Planar graph (section)

== Properties ==
=== Euler's formula ===
<!--Linked to from [[Crossing number inequality#Proof]]-->
{{main|Euler characteristic#Plane graphs}}
'''Euler's formula''' states that if a finite, [[Connectivity (graph theory)|connected]], planar graph is drawn in the plane without any edge intersections, and {{mvar|v}} is the number of vertices, {{mvar|e}} is the number of edges and {{mvar|f}} is the number of faces (regions bounded by edges, including the outer, infinitely large region), then

:<math>v-e+f=2.</math>

As an illustration, in the [[butterfly graph]] given above, {{math|1=''v'' = 5}}, {{math|1=''e'' = 6}} and {{math|1=''f'' = 3}}. 
In general, if the property holds for all planar graphs of {{mvar|f}} faces, any change to the graph that creates an additional face while keeping the graph planar would keep {{math|''v'' − ''e'' + ''f''}} an invariant. Since the property holds for all graphs with {{math|1=''f'' = 2}}, by [[mathematical induction]] it holds for all cases. Euler's formula can also be proved as follows: if the graph isn't a [[tree (graph theory)|tree]], then remove an edge which completes a [[cycle (graph theory)|cycle]]. This lowers both {{mvar|e}} and {{mvar|f}} by one, leaving {{math|''v'' − ''e'' + ''f''}} constant. Repeat until the remaining graph is a tree; trees have {{math|1=''v'' = ''e'' + 1}} and {{math|1=''f'' = 1}}, yielding {{math|1=''v'' − ''e'' + ''f'' = 2}}, i. e., the [[Euler characteristic]] is 2.

In a finite, [[Connectivity (graph theory)|connected]], ''[[simple graph|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 {{math|1=3''f'' ≤ 2''e''}}; using Euler's formula, one can then show that these graphs are ''sparse'' in the sense that if {{math|''v'' ≥ 3}}:

:<math>e\leq 3v-6.</math>

[[File:Dodecahedron schlegel.svg|thumb|A [[Schlegel diagram]] of a regular [[dodecahedron]], forming a planar graph from a convex polyhedron.]]

Euler's formula is also valid for [[convex polyhedron|convex polyhedra]]. This is no coincidence: every convex polyhedron can be turned into a connected, simple, planar graph by using the [[Schlegel diagram]] of the polyhedron, a [[perspective projection]] of the polyhedron onto a plane with the center of perspective chosen near the center of one of the polyhedron's faces. Not every planar graph corresponds to a convex polyhedron in this way: the trees do not, for example. [[Steinitz's theorem]] says that the [[polyhedral graph]]s formed from convex polyhedra are precisely the finite [[Connectivity (graph theory)|3-connected]] simple planar graphs. More generally, Euler's formula applies to any polyhedron whose faces are [[simple polygon]]s that form a surface [[homeomorphism|topologically equivalent]] to a sphere, regardless of its convexity.

=== Average degree ===

Connected planar graphs with more than one edge obey the inequality {{math|2''e'' ≥ 3''f''}}, because each face has at least three face-edge incidences and each edge contributes exactly two incidences. It follows via algebraic transformations of this inequality with Euler's formula {{math|1=''v'' − ''e'' + ''f'' = 2}} that for finite planar graphs the average degree is strictly less than 6. Graphs with higher average degree cannot be planar.

=== Coin graphs ===
{{main|Circle packing theorem}}
[[File:Circle packing theorem K5 minus edge example.svg|thumb|Example of the circle packing theorem on {{math|''K''{{sup| −}}{{sub|5}}}}, the complete graph on five vertices, minus one edge.]]

We say that two circles drawn in a plane ''kiss'' (or ''[[Osculating circle|osculate]]'') whenever they intersect in exactly one point.  A "coin graph" is a graph formed by a set of circles, no two of which have overlapping interiors, by making a vertex for each circle and an edge for each pair of circles that kiss. The [[circle packing theorem]], first proved by [[Paul Koebe]] in 1936,  states that a graph is planar if and only if it is a coin graph.

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 segment]]s 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.

=== Planar graph density ===
The [[meshedness coefficient]] or density {{mvar|D}} of a planar graph, or network, is the ratio of the number {{math|''f'' − 1}} of bounded faces (the same as the [[circuit rank]] of the graph, by [[Mac Lane's planarity criterion]]) by its maximal possible values {{math|2''v'' − 5}} for a graph with {{mvar|v}} vertices:
:<math>D = \frac{f-1}{2v-5}</math>
The density obeys {{math|0 ≤ ''D'' ≤ 1}}, with {{math|1=''D'' = 0}} for 
a completely sparse planar graph (a tree), and {{math|1=''D'' = 1}} for a completely dense (maximal) planar graph.<ref>{{citation
 | last1 = Buhl | first1 = J.
 | last2 = Gautrais | first2 = J.
 | last3 = Sole | first3 = R.V.
 | last4 = Kuntz | first4 = P.
 | last5 = Valverde | first5 = S.
 | last6 = Deneubourg | first6 = J.L.
 | last7 = Theraulaz | first7 = G.
 | doi = 10.1140/epjb/e2004-00364-9
 | issue = 1
 | journal = European Physical Journal B
 | pages = 123–129
 | title = Efficiency and robustness in ant networks of galleries
 | volume = 42
 | year = 2004| bibcode = 2004EPJB...42..123B| s2cid = 14975826
 }}.</ref>

===Dual graph===
[[Image:dual graphs.svg|thumb|100px|A planar graph and its [[Dual graph|dual]]]]

Given an embedding {{mvar|G}} of a (not necessarily simple) connected graph in the plane without edge intersections, we construct the ''[[dual graph]]'' {{mvar|G*}} as follows: we choose one vertex in each face of {{mvar|G}} (including the outer face) and for each edge {{mvar|e}} in {{mvar|G}} we introduce a new edge in {{mvar|G*}} connecting the two vertices in {{mvar|G*}} corresponding to the two faces in {{mvar|G}} that meet at {{mvar|e}}. Furthermore, this edge is drawn so that it crosses {{mvar|e}} exactly once and that no other edge of {{mvar|G}} or {{mvar|G*}} is intersected. Then {{mvar|G*}} is again the embedding of a (not necessarily simple) planar graph; it has as many edges as {{mvar|G}}, as many vertices as {{mvar|G}} has faces and as many faces as {{mvar|G}} has vertices. The term "dual" is justified by the fact that {{math|1=''G''** = ''G''}}; here the equality is the equivalence of embeddings on the [[sphere]]. If {{mvar|G}} is the planar graph corresponding to a convex polyhedron, then {{mvar|G*}} is the planar graph corresponding to the dual polyhedron.

Duals are useful because many properties of the dual graph are related in simple ways to properties of the original graph, enabling results to be proven about graphs by examining their dual graphs.

While the dual constructed for a particular embedding is unique (up to [[isomorphism]]), graphs may have different (i.e. non-isomorphic) duals, obtained from different (i.e. non-[[homeomorphic]]) embeddings.