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

Первые два класса задач относятся к вложениям в плоскость. Граф является планарным, если он может быть изображен на плоскости или сфере без пересечения дуг. Граф имеет (эйлеров) род не более g, если он может быть изображен на плоскости с эйлеровой характеристикой g. Класс графов имеет ограниченный род, если каждый граф класса имеет род не более g при фиксированном g.

Следующие три класса задач касаются исключения миноров. Пусть дано ребро e = {v, w} в графе G. Сжатие ребра e в графе G заключается в определении вершин v и w в G и удалении всех циклов и дублирующихся ребер. Граф H, полученный в результате последовательности таких операций сжатия ребер в исходном графе G, называется сжатием графа G. Граф H называется минором графа G, если H является подграфом некоторого сжатия G. Класс графов C является замкнутым относительно операции взятия минора, если любой минор любого графа из C также является членом C. Класс графов C, замкнутый относительно операции взятия минора, является свободным от H-миноров, если H … C. В более общем смысле, термин «свободный от H-миноров» относится к любому классу графов, замкнутому относительно операции взятия минора, который не включает некоторый фиксированный граф H. Граф с однократным пересечением представляет собой минор графа, который может быть изображен на плоскости так, что в нем будет пересекаться не более одной пары ребер. Класс графов, замкнутый относительно операции взятия минора, является свободным от миноров с однократным пересечением, если из него исключен фиксированный граф с однократным пересечением. Апексным графом называется граф, который становится планарным при удалении из него некоторой вершины. Класс графов является свободным от апексных миноров, если из него исключен некоторый фиксированный апексный граф.