Planar graphs

Understanding Planar Graphs

  • A planar graph is a type of graph that can be drawn on a plane without any edges crossing each other.
  • The concept is fundamental in topological graph theory, a branch of mathematics that studies the embedding of graphs in a plane.

Characteristics of Planar Graphs

  • A planar graph remains planar even if it is redrawn without crossing edges, as planarity is a property of the graph, not of the particular drawing.
  • Faces in a planar graph are the areas bounded by edges. There’s always one unbounded face, often referred to as the “outer” face or infinity face.
  • The number of faces, vertices and edges in a connected planar graph are related by the Euler’s formula: Faces + Vertices - Edges = 2.

Classification of Planar Graphs

  • Planar graphs can be divided into different subclasses, such as outerplanar graph, a graph that can be drawn in a plane in such a way that all vertices belong to the outer face.
  • Plane graph is a particular embedding of a planar graph in the plane, where the embedding illustrates the faces.
  • Maximal planar graph, also known as a triangulation, is a planar graph that cannot have any more edges added without losing its planarity.

Kuratowski’s and Wagner’s Theorems on Planar Graphs

  • Kuratowski’s theorem states a necessary and sufficient condition for a graph to be planar, which is that it should not contain a subgraph that is a subdivision of K5 (complete graph on 5 vertices) or K3,3 (complete bipartite graph for partitions of size 3).
  • Wagner’s theorem provides another characterization of planar graphs, stating that a finite graph is planar if and only if it does not have K5 or K3,3 as a minor.

Planar Graph Colouring

  • The Four Colour Theorem states that, given any separation of a plane into contiguous regions, no more than four colours are required to colour the regions so that no two adjacent regions have the same colour.
  • This theorem was the first major theorem to be proved using a computer, and despite initial controversy, it has been accepted due to lack of a counterexample.

Applications of Planar Graphs

  • Planar graphs have various applications in fields such as computer science, operations research, and geography for problems like map colouring, circuit design, and network optimization.