Проверка на планарность: различия между версиями

Задача заключается в установлении факта, является ли входной граф G [[планарный граф|планарным]]. Определение, наиболее подходящее для алгоритмов проверки на планарность, звучит так: граф G является планарным, если существует его [[вложение]] в плоскость (вершины G отображаются на различные точки, ребра G отображаются на кривые, соединяющие соответствующие конечные точки), такое, что ребра графа не пересекаются. Алгоритмы, проводящие проверку графа на планарность, можно модифицировать для получения подобного вложения.