Outer Planer Graph

1 min read

OUTER PLANAR GRAPHS: A planar graph is said to be outer planar if i(G) = 0. For example, cycles, trees, K4 – x.

(a) Maximal outer planar graph: An outer planar graph G is maximal outer planar if no edge can be added without losing outer planarity.
For example,

(b) Minimally non-outer planar graphs: A planar graph G is said to be minimally non outer planar if i(G) = 1

CROSSING NUMBER: The crossing number C(G) of a graph G is the minimum number of crossing of its edges among all drawings of G in the plane. A graph is planar if and only if C(G) = 0. Since K4 is planar C(K4) = 0 for p ≤ 4. On the other hand C(K5) = 1. Also K3, 3 is non planar and can be drawn with one crossing.