Skip to main content

Short note: Planar graph

Short answer

A planar graph can be drawn in the plane with no crossing edges. Example: K4 is planar. Euler's formula: v−e+f=2. For simple planar graphs with v≥3, e≤3v−6. Kuratowski's theorem: a graph is planar iff it contains no subdivision of K5 or K3,3.

Write a short note on planar graph (define planar graph with suitable example).

A graph is planar if it can be drawn in the plane so that no two edges cross except at their end vertices. Such a drawing is a planar embedding; it divides the plane into regions (faces), including the outer one.

Example: K₄ looks non-planar when drawn with two crossing diagonals of a square, but redrawing one diagonal outside the square (or placing a vertex inside a triangle) removes the crossing, so K₄ is planar. All trees and cycles are planar.

          a
         / \
        /   \
       /  d  \       d lies inside triangle abc and
      / /   \ \      is joined to a, b and c
     b --------- c

Results:

  • Euler's formula: for a connected planar graph with v vertices, e edges, f faces: v − e + f = 2.
  • For a simple connected planar graph with v ≥ 3: e ≤ 3v − 6. If it has no triangles, e ≤ 2v − 4.
  • Kuratowski's theorem: a graph is planar if and only if it has no subgraph that is a subdivision of K₅ or K₃,₃.
  • K₅ (e = 10 > 3·5 − 6 = 9) and K₃,₃ are non-planar.
  • Every planar graph can be colored with 4 colors.

Applications: circuit board and VLSI layout, road maps.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →