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.

Pin It on Pinterest

Share This