Graphs and Networks: Planar graphs

Planar Graphs

A Planar Graph is a graph which can be drawn on a plane without any of its edges crossing each other.
Every planar graph can be presented in such a way that all its edges meet only at their endpoints, a state called a Planar Embedding or Plane Graph.
A region of a plane, whose boundaries are formed by edges and vertexes of a graph, is termed a face. The unrestricted area outside the boundaries of a graph is also considered a face.

A subgraph of a planar graph that includes all the vertexes and is a cycle is recognised as a facial cycle or cycle of a face.
Outerplanar graphs are planar graphs that have a planar drawing where all vertices are on the outer face.
If every face of a planar graph is bounded by exactly three edges, the graph is a triangulation or maximal planar graph.

The Euler’s formula specifically connects the number of vertices, edges, and faces in any planar graph. The formula is v - e + f = 2.
If a planar graph is connected, has ‘e’ edges and ‘v’ vertices with ‘v’ ≥ 3, then ‘e’ ≤ 3’v’ - 6. This is known as a planarity criterion.
The maximum number of edges in a planar graph with ‘n’ vertices is 3n - 6.
A planar graph can have a dual graph, where each vertex of the dual graph corresponds to a face of the original graph and each edge in the dual graph corresponds to an edge in the original graph.
All Trees are planar graphs but not all planar graphs are trees.

The Four Colour Theorem states that any planar graph can be coloured using no more than four colours in such a way that adjacent vertices have different colours.
Kuratowski’s Theorem defines the necessary and sufficient condition for a graph to be non-planar. A graph is non-planar if it contains a subgraph that is a subdivision of K_5 (complete graph on five vertices) or K_{3,3} (complete bipartite graph with three vertices in each partition).
The Fáry’s Theorem asserts that if a graph is planar, then it can be drawn without crossings in such a way that all the edges are straight lines. This is known as a straight line embedding.