# Planar Graphs

## Definition and Characteristics

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

## Special Types of Planar Graphs

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

## Graph Properties

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

## Planar Graph Theorems

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