Planar graph

Planar graph --- планарный граф, плоский граф.

A crossing-free embedding of a graph in the plane is given by drawing a graph [math]\displaystyle{ G }[/math] in the plane with points representing vertices and curves representing edges such that no two curves for edges intersect except at common endvertices. [math]\displaystyle{ G }[/math] is a planar graph if there is a crossing-free embedding of [math]\displaystyle{ G }[/math] in the plane.

In other words, a graph (digraph) [math]\displaystyle{ G }[/math] is called a planar graph, if there is a projection [math]\displaystyle{ \Pi }[/math] of the vertices and edges of [math]\displaystyle{ G }[/math] into the plane such that the intersections of the projections of edges occur at the projections of vertices, and [math]\displaystyle{ \Pi((u,v)) }[/math] is a Jordan-curve from [math]\displaystyle{ \Pi(u) }[/math] to [math]\displaystyle{ \Pi(v) }[/math]. The projection [math]\displaystyle{ \Pi }[/math] is called a planar embedding of [math]\displaystyle{ G }[/math]. It divides the plane into a number of connected regions, called faces, each bounded by the projection of edges of the graph. There is always a face with an infinite area, which is called the exterior face.

See also

• Plane graph.