1 min read

REGION: A plane representation of a graph divides the plane into regions (also called windows, faces, or meshes) as shown in figure below. A region is characterized by the set of edges (or the set of vertices) forming its boundary.
Note that a region is not defined in a non-planar graph or even in a planar graph not embedded in a plane.

For example, the geometric graph in figure below does not have regions.


A planar graph is maximal planar if no edge can be added without loosing planarity. Thus in any maximal planar graph with p ≥ 3 vertices, the boundary of every region of G is a triangle for this maximal planar graphs (or plane graphs) are also refer to as triangulated planar graph (or plane graph).