Planar graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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.