Planar graph

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

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

In other words, a graph (digraph) $G$ is called a planar graph, if there is a projection $\Pi$ of the vertices and edges of $G$ into the plane such that the intersections of the projections of edges occur at the projections of vertices, and $\Pi((u,v))$ is a Jordan-curve from $\Pi(u)$ to $\Pi(v)$. The projection $\Pi$ is called a planar embedding of $G$. 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.