Определение 1. Графом G называется конечное множество вершин V(G) и конечное множество ребер R(G), так что каждое ребро имеет своими концами две различные вершины. Граф называется плоским, если вершины являются точками плоскости, а ребра – ломаными линиями (составленными из отрезков) в этой же плоскости, имеющими своими концами вершины, не пересекающимися между собой и не включающими других вершин, кроме своих концов. Отметим, что в плоском графе не допускаются петли (ребра, имеющие началом и концом одну и ту же вершину). Плоский граф разрезает плоскость на совокупность D(G) неперекрывающихся многоугольных областей, необязательно конечных (рис. 21).