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