Как определить, является ли граф планарным?

1. Граф является планарным, если его можно изобразить на плоскости без пересечений рёбер. Чтобы определить, является ли граф планарным, можно визуально нарисовать его на плоскости и проверить, есть ли пересечения рёбер.

2. Для доказательства планарности графа можно применить теоремы Понтрягина-Куратовского. Эти теоремы утверждают, что граф не является планарным, если в нем содержатся подграфы, изоморфные полному графу К5 (пятивершинный полный граф) или графу К3,3 (трехвершинный двудольный граф). Таким образом, если в графе нет таких подграфов, то он является планарным.

Если вы уверены, что он планарный, то его надо нарисовать без пересечений ребер. Подвигайте вершины туда-сюда. 
 
 А теоремы эти используют как раз, чтобы доказать, что граф не планарный. Тогда вы берете как-то стягиваете его вершины и получаете K33 или K5. Значит не планарный. 
 
 Доказать отсутствие таких стягиваний очень муторно. Надо перебирать все варианты. Типа, что будет если мы вот эти 2 вершины стягиваем в одну? А если нет? В первом случае, а стягиваем ли мы туда вот эту третью? А если нет? И так у вас 100500 случаев. Если очень граматно выбрать вершины, то есть шанс, что количество вариантов будет не слишком большое. Если видите, что стянутый граф можно нарисовать без самопересечений, дальше стягивать не надо.