Просмотр кода страницы Planar graph

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

A crossing-free embedding of a graph in the plane is given by drawing
a graph <math>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>G</math> is a ''' planar graph''' if there is a crossing-free
embedding of <math>G</math> in the plane.

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