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.