Planar Graphs

tutorial and example
tutorial and example

What is a Planar Graph?

The graph that can be drawn on a plane such that no two edges cross each other or intersect each other, this type of graph is called planar graph. Such a drawing of a planar graph is called planar embedding of the graph. It divides the plane into regions like R1, R2 etc.

What is Non Planar Graph?

A graph that cannot be drawn on the plane without crossing the edges is called as non-planar graph.

Embedding: A drawing of geometric representation of a graph on any surface such that no edges intersect is called embedding.

Note:

  • The graph can be embedded in the surface of a sphere if and only if it is embedded in a plane by stereographic projection.
  • A connected part of a plane which does not contain any vertices and is surrounded by edges called a region of a planar embedding. The part outside the embedding is considered as a region, known as the exterior region.
  • The vertices surrounding a region “s” are called boundary vertices and the edges surrounding “s” are called boundary edges. Here, s is the region of the graph.
  • Two regions are adjacent if they share a boundary edge.

Maximal Planar Graph: If a graph is a planar graph and adding any edges to the graph would destroy its property, this type of simple graph is called maximal planar graph.

Every 3-vertex-connected graph is a maximal planar graph.

If a maximal planar graph has v vertices where v greater than 2 then it has 2v minus 4 faces and 3v minus 6 edges.

Apollonian Networks: When we repeatedly split triangular faces into triples of smaller triangles, the network is called apollonian networks.

This network is also called maximal planar graphs.