# Graphs and Networks: Planar graphs

## Graphs and Networks: Planar graphs

# 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**.