Планарный граф

Для любого связного плоского графа соотношение между числом вершин (В), рёбер (Р) и граней (Г) остаётся постоянным и выражается формулой Эйлера:

В − Р + Г = 2^[3].

Из этой формулы вытекают важные следствия, которые используются, в частности, при разработке алгоритмов проверки графа на планарность^[3]. Например, для простого планарного графа с числом вершин В > 2 число рёбер Р не может превышать 3В − 6^[3]. Другим следствием является то, что в любом планарном графе существует вершина со степенью не более 5^[4].

После 1900 года формула Эйлера получила значительное развитие, превратившись из частного случая для многогранников в фундаментальный принцип топологии^[3].

Обобщение на высшие размерности

Наиболее важным развитием стало обобщение, предложенное Анри Пуанкаре. Он показал, что это соотношение является частным случаем более общего топологического инварианта — характеристики Эйлера-Пуанкаре^[5]. Для n-мерного комплекса она определяется как знакопеременная сумма числа его элементов разной размерности:

χ = k₀ − k₁ + k₂ − k₃ + ..., где kᵢ — число элементов размерности i (вершин, рёбер, граней и т.д.)^[5].

Это обобщение стало краеугольным камнем алгебраической топологии^[5].

Формула для различных поверхностей

Формула была также распространена на графы, расположенные на поверхностях, отличных от плоскости или сферы, например, на торе. Было установлено, что значение выражения В − Р + Г зависит от топологической структуры самой поверхности и равно её эйлеровой характеристике χ(S)^[6].

• Для сферы и плоскости χ = 2.
• Для тора χ = 0.
• Для поверхности с g «ручками» (кренделя) χ = 2 − 2g.

Таким образом, характеристика Эйлера стала мощным инструментом для классификации поверхностей^[6]. Концепция эйлеровой характеристики как топологического инварианта лежит в основе идей, которые привели к решению гипотезы Пуанкаре Григорием Перельманом^[6].

Казимеж Куратовский дал характеристику планарных графов в терминах запрещённых графов, ныне известную как теорема Куратовского:

Конечный граф планарен тогда и только тогда, когда он не содержит подграфа, являющегося разбиением полного графа K₅ или полного двудольного графа K_3,3 (граф коммунальной службы).

Разбиение графа получается путём вставки вершин в рёбра (например, превращая ребро • —— • в • — • — •) ноль или более раз.

Вместо разбиений теорема Вагнера использует понятие минора:

Конечный граф планарен тогда и только тогда, когда в нём нет миноров K₅ или K_3,3.

Минор графа получается путём взятия подграфа и последовательной свёртки рёбер в вершины: все соседи исходных вершин становятся соседями новой вершины.

Клаус Вагнер в более общем виде спросил, определяются ли любые минор-замкнутые классы графов конечным набором запрещённых миноров. Это ныне теорема Робертсона — Сеймура, доказанная в серии работ. В рамках этой теоремы K₅ и K_3,3 — запрещённые миноры для класса конечных планарных графов.

На практике критерий Куратовского трудоёмок для алгоритмического определения планарности произвольного графа. Однако существуют быстрые алгоритмы: для графа с n вершинами проверка планарности возможна за время O(n) (линейное время). Одним из наиболее современных и эффективных последовательных методов является алгоритм Бойера и Мирвольд (2004), который упростил предыдущие подходы^[7]. В 2024 году на его основе были разработаны параллельные алгоритмы, показавшие значительное ускорение на многоядерных системах^[7]. Для более сложной динамической задачи (проверки сохранения планарности при добавлении рёбер) прорывной результат был получен Якобом Хольмом и Евой Ротенберг в 2020 году^[8]. В 2025 году был представлен алгоритм для решения обобщённой задачи синхронизированной планарности, который также позволил ускорить решение других задач с ограничениями, например, кластерной планарности^[9].

Для простого связного планарного графа с v вершинами, e рёбрами и f гранями выполнены:

• Теорема 1. e ≤ 3v − 6;
• Теорема 2. Если в графе нет циклов длиной 3, то e ≤ 2v − 4.
• Теорема 3. f ≤ 2v − 4.

Таким образом, планарные графы — разрежённые, так как число рёбер O(v), что асимптотически меньше максимального O(v^2). Например, в графе K_3,3 шесть вершин, девять рёбер и нет циклов длиной 3, поэтому, согласно второй теореме, он не может быть планарным. Эти условия являются необходимыми, но не достаточными, и могут использоваться только для доказательства непланарности графа. Если теоремы 1 и 2 не применимы, используют другие методы.

• Критерий планарности Уитни основан на существовании алгебраического двойственного графа;
• Критерий планарности Мак-Лейна даёт алгебраическую характеристику конечных планарных графов через их пространство циклов графа;
• Критерий планарности де Фрайссе — Розенштиля строится на существовании бипартитного разбиения рёбер вне дерева поиска в глубину — используется в левостороннем тестировании планарности;
• Теорема Шнайдера даёт характеристику планарности через размерность частичного порядка;
• Критерий планарности Колена де Вердьера использует максимальную кратность второго собственного значения определённых операторов Шрёдингера, задаваемых графом;
• Теорема Ханани — Тутте: граф планарен тогда и только тогда, когда существует его изображение, в котором каждая независимая пара рёбер пересекается чётное число раз; даёт систему уравнений по модулю 2.
• Комбинаторный критерий (2012): связный граф планарен тогда и только тогда, когда все его коциклы с четырьмя и более рёбрами являются «заземлёнными» (grounded). Хотя формулировка является новой, сам критерий выводится из теоремы Куратовского^[10][11].
• Структурная характеризация (2015): любой планарный граф является графом пересечения одного хордального графа, четырёх ко-двудольных графов и одного единичного интервального графа. Это не практический критерий, а описание структуры планарных графов через их связь с другими классами^[12].

Простой граф называют максимально планарным, если он планарен, но добавление любого ребра (между существующими вершинами) разрушает эту свойство. Тогда все грани (в том числе внешняя) ограничены тремя рёбрами — поэтому такой граф также называют плоской триангуляцией (на самом деле это изображение графа). Также встречаются термины «треугольный граф»^[13] и «триангулированный граф»^[14], однако эти понятия неоднозначны, так как чаще относятся к линейным графам полных графов и к хордальным графам, соответственно. Каждый максимально планарный граф с более чем 3 вершинами является как минимум 3-связным^[15].

Для максимально планарного графа с v вершинами, если v>2, то он имеет точно 3v−6 рёбер и 2v−4 граней.

В 1980-е годы были заложены многие алгоритмические основы для работы с максимально планарными графами. В конце десятилетия был предложен канонический порядок (англ. canonical ordering) — специальная нумерация вершин, позволившая разработать первые алгоритмы для изображения любого максимально планарного графа на целочисленной сетке размером O(n) × O(n) с прямыми рёбрами за линейное время^[16][17]. В 1983 году Дэвид Киркпатрик разработал оптимальный алгоритм для решения задачи локализации точки в триангуляциях, который после предобработки находит грань, содержащую заданную точку, за время O(log n)^[18].

К другим важным структурным результатам относятся доказательство того, что любой максимально планарный граф можно преобразовать в любой другой с помощью последовательности «диагональных операций» (замены ребра в четырёхугольнике на другую диагональ)^[19], и доказательство того, что эти графы являются реконструируемыми^[20]. В 2024 году была предложена характеризация максимальных планарных графов, которые могут быть центром некоторого другого планарного графа^[21].

Понятие максимальной планарности было обобщено на k-планарные графы (графы, где каждое ребро пересекается не более чем с k другими). Однако их свойства могут отличаться от классического случая (k=0). Например, максимальные 2-планарные графы с n ≥ 5 вершинами имеют не менее 2n рёбер (результат 2023 года)^[22]. В отличие от 1- и 2-планарных аналогов, максимальные 3-планарные графы не всегда являются 2-связными и могут содержать шарниры (результат 2024 года)^[23].

К связанным классам графов относятся:

• Аполлониевы сети — максимально планарные графы, получающиеся путём многократного деления треугольных граней на три малых треугольника. Эквивалентно, это планарные 3-деревья.
• Странгулированные графы — графы, где каждый периферийный цикл является треугольником. В максимально планарных графах периферийные циклы — это грани, так что все они странгулированы. Странгулированные графы включают и хордальные; это в точности графы, представимые в виде клика-сумм (без удаления рёбер) из полных графов и максимально планарных графов^[24].

Странгулированные графы, также известные как сильно хордальные графы (англ. strongly chordal graphs), являются подклассом хордальных графов, обладающим сильным совершенным исключающим упорядочением (англ. strong elimination ordering). Этот класс графов включает максимально планарные графы и может быть охарактеризован как графы, представимые в виде клика-сумм (без удаления рёбер) из полных графов и максимально планарных графов^[24].

Исследования 1990-х годов были сосредоточены на разработке эффективных алгоритмов распознавания. В 1993 году Дж. Спинрад представил алгоритм со временем выполнения O(n²), который также позволял построить сильное совершенное исключающее упорядочение^[25]. В этот же период были созданы параллельные алгоритмы, способные решать задачу распознавания за полилогарифмическое время (O(log² n)) с использованием полиномиального числа процессоров, что отнесло её к классу сложности NC^[26].

После 1999 года исследования продолжились в области динамических алгоритмов. В 2020 году были предложены полудинамические алгоритмы для вставки и удаления рёбер в строго хордальных графах. Алгоритм вставки имеет сложность O(n²), а удаления — O(d²ᵤd²ᵥ(n+m))^[27]. К другим современным результатам относятся точная характеризация центров хордальных графов (2022)^[28] и введение обобщающего понятия «локально хордальных графов» (2025)^[29].

Благодаря наличию сильного совершенного исключающего упорядочения, многие NP-трудные задачи, такие как нахождение минимального доминирующего множества, решаются для сильно хордальных графов за полиномиальное время^[27].

Внешнепланарные графы — это графы, которые можно изобразить на плоскости так, что все их вершины лежат на внешней (неограниченной) грани вложения. Каждый внешнепланарный граф — планарный, но не наоборот: K₄ — планарный, но не внешнепланарный. Аналог теоремы Куратовского утверждает: конечный граф является внешнепланарным тогда и только тогда, когда не содержит разбиения K₄ или K_2,3. Это вытекает из того, что граф G — внешнепланарный, если добавив в него новую вершину, соединённую со всеми остальными, получим планарный граф.

Вложение графа называется 1-внешнепланарным, если оно внешнепланарное. Для k>1 вложение графа называется k-внешнепланарным, если после удаления вершин внешней грани вложение становится (k−1)-внешнепланарным; граф называется k-внешнепланарным, если у него есть такое вложение.

Исследования после 2007 года позволили охарактеризовать внешнепланарные графы с помощью новых свойств, в частности, в спектральной теории, в исследованиях, связанных с доминированием, и в применении концепций из других областей математики.

• Спектральные характеристики. В 2023 году была представлена полная идентификация всех связных внешнепланарных графов, у которых второе по величине собственное значение (λ₂) не превышает 1^[30]. Ранее, в 2017 году, была подтверждена гипотеза, согласно которой граф K₁ ∨ Pₙ₋₁ (колесо без одного ребра) имеет максимальный спектральный радиус среди всех внешнепланарных графов с n вершинами для достаточно больших n^[30].

• Характеристики, основанные на кривизне. С использованием понятия кривизны Риччи, адаптированного для графов, было показано, что простые внешнепланарные графы с минимальной степенью вершин не менее 2 и положительной кривизной Лин-Лу-Яу на каждом ребре имеют максимальную степень не более 9. Если такой граф является максимально внешнепланарным, то он содержит не более 10 вершин, причём эти оценки являются точными^[31].

• Характеристики, связанные с доминированием. В 2022 году была решена открытая проблема и дана характеризация внешнепланарных графов, у которых число 2-доминирования (γ₂) равно числу доминирования (γ)^[32]. Как следствие, было доказано, что для любого максимального внешнепланарного графа с числом вершин не менее 3, число 2-доминирования строго больше числа доминирования^[32].

Граф Халина строится из неориентированного плоского дерева (без вершин степени две) обхватом его листьев циклом в порядке обхода дерева. Эквивалентно это многогранный граф, в котором одна грань граничит со всеми остальными. Каждый граф Халина — планарен. Как и внешнепланарные графы, графы Халина имеют малую древесную ширину^[33].

Исследования после 1983 года уточнили и расширили знания об этом классе графов. В 1988 году было установлено, что их древесная ширина в точности равна 3^[34], что объясняет, почему многие NP-трудные задачи, такие как задача о гамильтоновом цикле и задача Штейнера, решаются на них за полиномиальное (часто линейное) время^[35]. Были разработаны и алгоритмы для распознавания графов Халина за линейное время^[36].

Графы Халина обладают сильными циклическими свойствами. Было подтверждено, что любой граф Халина является гамильтоновым, причём он остаётся таковым даже после удаления любой одной вершины^[37]. В 1985 году было доказано, что они являются «почти панциклическими», то есть содержат циклы всех длин от 3 до n (число вершин), за возможным исключением одной длины чётного порядка^[37].

К другим установленным свойствам относится то, что боксицитность графа Халина (не являющегося K₄) равна 2^[36]. Исследовались и обобщения, например, «обобщённые графы Халина», в которых допускаются вершины степени 2^[38]. В недавних работах, вплоть до 2025 года, графы Халина изучаются в контексте дискретной кривизны, в частности, кривизны Линя-Лу-Яу^[38].

Восходящий планарный граф — это ориентированный ациклический граф, который можно изобразить на плоскости так, что все рёбра являются монотонно возрастающими кривыми в вертикальном направлении и не пересекаются друг с другом^[39]. Не каждый планарный ориентированный ациклический граф является восходящим; задача проверки восходящей планарности в общем случае NP-полна^[40].

Хотя общая проблема NP-полна, для важных подклассов графов существуют полиномиальные алгоритмы^[40]. Наиболее значимым является результат для графов с одним источником, для которых проверка на восходящую планарность может быть выполнена за линейное время^[40]. Полиномиальные алгоритмы также существуют для внешнепланарных и последовательно-параллельных графов^[40].

Исследования после 2000 года сосредоточились на специализированных видах отрисовки, в частности:

• Восходящие планарные L-отрисовки, где каждое ребро состоит из одного вертикального и одного горизонтального отрезка. В 2024 году было установлено, что граф допускает такую отрисовку, если он является подграфом плоского st-графа с определёнными свойствами, что позволило разработать алгоритмы с линейным временем работы для частных случаев^[41].
• Отрисовки с ограниченным числом наклонов — прямолинейные отрисовки, использующие небольшое фиксированное количество наклонов для рёбер. Задача NP-трудна даже для внешнепланарных графов, но решена для деревьев и кактусовых графов^[42].
• Прямолинейно-восходящая планарность (англ. Rectilinear-Upward Planarity), где рёбра могут быть только горизонтальными или вертикальными. Проблема NP-полна, но решается за линейное время, если вложение графа зафиксировано (результат 2023 года)^[43].

К другим современным направлениям относятся:

• Проблема расширения (англ. Upward Planarity Extension): задача определения, можно ли расширить заданную восходящую планарную отрисовку подграфа до отрисовки всего графа. В общем случае она NP-полна (2019)^[44], но для st-графов существует эффективный алгоритм со сложностью O(n log n)^[44].
• Динамические структуры данных: В 2024 году была представлена структура данных для поддержания восходящего планарного вложения графа с одним источником. Она позволяет выполнять операции добавления и удаления рёбер, проверяя сохранение свойства за время O(log² n)^[40].

Планарный граф называется выпуклым, если все его грани (в том числе внешняя) — выпуклые многоугольники. Не каждый планарный граф допускает выпуклое вложение (например, двудольный граф K_2,4). Достаточным условием для выпуклого вложения служит то, что граф является разбиением 3-связного планарного графа. Теорема Татта о пружинах (1963), также известная как теорема о барицентрическом вложении, предоставляет конструктивный метод для таких графов. Согласно теореме, для простого 3-связного планарного графа можно построить плоское представление без пересечения рёбер, если зафиксировать вершины его внешней грани в виде выпуклого многоугольника, а каждую внутреннюю вершину расположить в точке, являющейся средним арифметическим (барицентром) координат её соседей^[45]. Такое расположение, эквивалентное решению системы линейных уравнений, гарантирует, что все грани в полученном изображении будут выпуклыми^[45].

Идеи Татта получили развитие в современных исследованиях. Теорема была обобщена на графы, расположенные на более сложных поверхностях. Колен де Вердьер в 1991 году расширил её на графы на поверхностях с неположительной кривизной, а в 2005—2006 годах были получены аналогичные результаты для графов, вложенных в тор^[45]. В 2025 году был предложен чисто дискретный аналог теоремы для поверхностей с неположительной кривизной, что, в отличие от предыдущих непрерывных обобщений, позволяет разрабатывать эффективные алгоритмы для построения таких вложений^[46].

Оригинальная теорема не указывала, как оптимально располагать вершины внешней грани. В 2020 году Джон Уршель и Людмил Зикатанов рассмотрели задачу минимизации суммы квадратов длин рёбер для всего графа путём оптимального размещения вершин внешней грани, установив связь этой задачи с дополнением Шура для лапласиана графа^[47]. На практике, помимо метода Татта, для визуализации графов широко применяются эвристические силовые алгоритмы, а также методы, основанные на каноническом упорядочении^[48].

Класс слово-представимых планарных графов содержит беспетлевые треугольники и более широко — 3-раскрашиваемые планарные графы^[49], а также некоторые разбиения граней треугольной решетки^[50] и некоторые триангуляции цилиндрических графов^[51].

Исследования после 2016 года уточнили границы этого класса графов. В 2017 году был получен важный отрицательный результат: не все графы, у которых степень каждой вершины не превышает 4, являются слово-представимыми^[52]. Это имеет прямое отношение к планарным графам, так как среди них существуют графы с такой максимальной степенью, что ставит открытым вопрос о поиске не-слово-представимых планарных графов^[52].

Значительный прогресс был достигнут в разработке аналитических инструментов. В 2024 году для изучения слово-представимых графов были применены методы из теории частичных порядков, теории Рамсея и вероятностные методы, что позволило решить ряд открытых проблем^[53]. В конце того же года была предложена новая структурная характеризация с использованием модульной декомпозиции, которая, в частности, решила проблему слово-представимости лексикографического произведения графов^[54].

Концепция слово-представимости также получила несколько обобщений. К ним относятся k-11-представимые графы^[55], языково-представимые графы, где класс графов сопоставляется формальному языку^[56], и слово-представимые временные графы, где рёбра существуют в определённые моменты времени^[57].

Основополагающий результат в асимптотическом перечислении планарных графов был получен Омером Хименесом и Марком Ноем в 2009 году^[58]. Они вывели точные асимптотические формулы для числа как маркированных, так и немаркированных планарных графов.

Число маркированных планарных графов с ${\displaystyle n}$ вершинами имеет вид:

${\displaystyle g_{n}\sim g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!}$,

где ${\displaystyle \gamma \approx 27.22687}$ — константа роста, а ${\displaystyle g\approx 0.42609\times 10^{-5}}$ — другая константа^[59][60].

Для немаркированных (неизоморфных) планарных графов асимптотика выводится из формулы для маркированных. Поскольку большинство планарных графов асимметричны (имеют тривиальную группу автоморфизмов), их число ${\displaystyle u_{n}}$ оценивается как ${\displaystyle u_{n}\sim g_{n}/n!}$^[59], что даёт:

${\displaystyle u_{n}\sim g\cdot n^{-7/2}\cdot \gamma ^{n}}$.

Последующие исследования расширили эти результаты:

• Обобщение на другие поверхности. Было показано, что число помеченных графов с ${\displaystyle n}$ вершинами, вложимых в ориентируемую поверхность рода ${\displaystyle g}$, асимптотически растёт как ${\displaystyle c(g)\cdot n^{5(g-1)/2-1}\cdot \gamma ^{n}\cdot n!}$. Примечательно, что экспоненциальная константа роста ${\displaystyle \gamma }$ остаётся той же, что и для планарного случая (${\displaystyle g=0}$)^[61][62].
• Асимптотика для подклассов. Были получены точные асимптотические оценки для различных семейств планарных графов, включая 4-регулярные (2023)^[62], а также тетрациклические и пентациклические графы^[63].

После 2005 года был достигнут значительный прогресс в структурной характеристике групп автоморфизмов планарных графов. Ключевым результатом стала работа Павла Клавика (Pavel Klavík) и его соавторов, которые представили полное рекурсивное описание всех абстрактных групп, которые могут быть реализованы как группы автоморфизмов планарных графов. Эта работа значительно развивает и уточняет более раннюю характеристику, данную Ласло Бабаи в 1975 году^[64].

Новая характеристика является индуктивной и основана на редукции графа к его 3-связным компонентам. Группы автоморфизмов 3-связных планарных графов, известные как сферические группы, соответствуют конечным подгруппам группы изометрий сферы. Группы автоморфизмов для произвольных планарных графов строятся из этих базовых блоков с помощью таких операций, как прямое и сплетение произведений циклических, симметрических и знакопеременных групп^[64].

В алгоритмическом плане задача нахождения группы автоморфизмов тесно связана с задачей изоморфизма графов. В этой области также произошёл важный прорыв: в 2022 году было доказано, что задача проверки изоморфизма планарных графов принадлежит классу сложности Log-Space (то есть решаема с использованием логарифмического объёма памяти), что является фундаментальным результатом в теории сложности вычислений^[65]. Наряду с теоретическими исследованиями, существуют и алгоритмы, ориентированные на практическое применение, хотя их сложность может быть выше, например, O(n²)^[66].

Теорема, опубликованная Вальтером Шнайдером в 1989—1990 годах, стала фундаментальным результатом в теории планарных графов^[67]. В основе её доказательства лежит специальная структура, известная как «лес Шнайдера» (англ. Schnyder wood) — разбиение рёбер триангулированного планарного графа на три остовных дерева^[68]. Теорема устанавливает два ключевых факта:

• Критерий планарности: Граф является планарным тогда и только тогда, когда размерность его частично упорядоченного множества инцидентности не превышает трёх^[68].
• Вложение в сетку: Любой планарный граф с n вершинами допускает изображение в виде прямолинейного графа на целочисленной сетке размером (n−2)×(n−2)^[68].

В 1990-е годы на основе этой теоремы были получены важные обобщения. В 1993 году Грэм Брайтвелл и Уильям Троттер расширили результат на трёхмерные объекты, доказав, что для частично упорядоченного множества, образованного вершинами, рёбрами и гранями выпуклого трёхмерного многогранника, порядковая размерность не превышает четырёх^[69]. Практически одновременно с работой Шнайдера, в 1990 году, де Фрейсе, Пах и Поллак представили алгоритм, позволяющий получить прямолинейное вложение на сетке размером (2n−4)×(n−2)^[70]. В 1999 году Патрис Оссона де Мендез обобщил теорему на симплициальные комплексы, а также были установлены связи между методами Шнайдера и другими задачами комбинаторики, в частности, с числом Алона — Тарси, относящимся к раскраске графов^[71].

Теорема о четырёх красках утверждает: любой планарный граф четырёхраскрашиваемый (может быть окрашен максимум в 4 цвета, причём соседние вершины имеют разные цвета).

Теорема Фари утверждает: любой простой планарный граф допускает изображение как плоский граф с рёбрами — отрезками. Универсальное множество точек — набор точек, позволяющий вложить любой планарный граф на n вершинах так, чтобы все вершины соответствовали этим точкам; существуют такие множества квадратичного размера — например, прямоугольная подрешётка целой решётки. Любой простой внешнепланарный граф допускает вложение так, что все вершины находятся на окружности, все рёбра — отрезки прямых внутри круга и не пересекаются, поэтому правильные n-угольники универсальны для внешнепланарных графов.

Гипотеза Шайнермана, доказанная в 2009 году Жереми Шалопеном и Даниелем Гонсалвисом^[72], утверждает: любой планарный граф может быть представлен как граф пересечений отрезков на плоскости.

Теорема о планарном разделителе: любой планарный граф на n вершинах можно разбить на два подграфа размером не более 2n/3 путём удаления ${\displaystyle O({\sqrt {n}})}$ вершин. Как следствие, планарные графы имеют ширину дерева и ширину ветвления не больше O(√n).

Теорема о структуре произведения утверждает, что любой планарный граф является подграфом сильного произведения графов графа с простой древесной шириной не более 6 и пути^[73]. Этот результат, улучшивший более раннюю версию с древесной шириной 8^[74], позволяет доказать, что для планарных графов ограничены номер очереди и нерепетитивное хроматическое число. Также это используется в задаче ранжирования вершин^[75] и p-центрированного раскрашивания^[76].

Задача проверки изоморфизма для планарных графов решается за линейное время^[77]. Более сильным результатом является то, что эта задача принадлежит классу сложности Log-space, то есть решаема с использованием логарифмического объёма памяти^[65].

Размер максимальной клики в планарном графе не превышает 4. Любой планарный граф на n вершинах содержит не более 8(n−2) максимальных клик, в том числе не более 3n−8 треугольников (3-клик) и не более n−3 4-клик^[78]. Задача поиска максимальной клики для планарных графов решается за линейное время^[79].

По теореме Тутте (1956), любой 4-связный планарный граф содержит гамильтонов цикл^[80]. Этот результат был значительно усилен Карстеном Томассеном в 1983 году, который доказал, что любой 4-связный планарный граф является гамильтоново-связным (то есть для любых двух вершин существует гамильтонов путь между ними)^[81].

Апекс-граф — граф, который становится планарным после удаления одной вершины, а k-апекс-граф — после удаления не более k вершин.

1-планарный граф — граф, который можно нарисовать на плоскости с не более чем одним простым пересечением на каждое ребро; k-планарный — максимум k пересечений на ребро. Свойства максимальных k-планарных графов могут отличаться от классического случая (k=0). Например, было установлено, что максимальные 2-планарные графы с n ≥ 5 вершинами имеют не менее 2n рёбер (результат 2023 года)^[22]. В отличие от 1- и 2-планарных аналогов, максимальные 3-планарные графы не всегда являются 2-связными и могут содержать шарниры (результат 2024 года)^[23].

Граф карты — граф, построенный по конечному семейству попарно непересекающихся (по внутренности) областей на плоскости: точки соответствуют областям, рёбра — парам областей, граничащих по крайней мере в одной точке. Если в одной точке встречаются максимум три области, граф планарен; если четыре и более — возможна непланарность (например, деление круга на сектора: все области граничат в центре, что даёт полный граф).

Тороидальный граф — граф, допускающий вложение без пересечений на тор. Более общее понятие — род графа: минимальный род двумерной поверхности, в которую граф может быть вложен без пересечений. Планарные графы имеют род ноль, непланарные тороидальные — род один. Каждую поверхностную карту можно вложить без пересечений в некоторую (ориентируемую, связанную) замкнутую поверхность, в частности, в сферу с ручками, так что род определён всегда. Если граф вложим в поверхность рода g без пересечений, то и во всякую поверхность большего рода он также вложим. Термин «род» с определяющим словом (например, неориентируемый род) иногда означает иную величину.

Любой граф можно вложить в трёхмерное пространство без пересечений. Точнее, любой граф можно нарисовать на двух слоях: два плана наложены друг на друга, рёбра могут «перепрыгивать» между ними в произвольных точках (не только в вершинах), чтобы обойти пересечения. Это эквивалентно тому, что любую электрическую схему можно реализовать на двухсторонней плате с переходами между слоями; или любая дорожная сеть может быть построена только с мостами или только с туннелями (двух уровней достаточно). В трёхмерном случае проблема пересечений рёбер тривиальна, но аналогами планарных графов служат графы с вложением без зацеплений — те, что разрешают вложение в трёхмерное пространство так, чтобы никакие два цикла не образовывали топологически неразвязанных связей. Аналогично теоремам Куратовского и Вагнера, такие графы характеризуются отсутствием в качестве минора семи графов семейства Петерсена. Эта характеризация является частным случаем теоремы Робертсона — Сеймура (также известной как теорема о минорах графа), монументальное доказательство которой было завершено в 2004 году. Теорема утверждает, что для любого семейства графов, замкнутого относительно операции взятия минора, существует конечный набор запрещённых миноров^[82]. После 2004 года фокус исследований сместился на использование её мощной структурной части. Структурная теорема описывает строение любого графа, не содержащего некоторый фиксированный граф H в качестве минора: такой граф может быть разложен древовидным образом на части, которые «почти» вкладываются в некоторую поверхность ограниченного рода^[83]. Теорема имеет важные алгоритмические следствия и является одним из столпов теории фиксированно-параметрической разрешимости. В частности, из неё следует, что для любого класса графов, не содержащего фиксированный планарный граф в качестве минора, древесная ширина ограничена^[84], что позволяет решать многие NP-трудные задачи на таких графах за полиномиальное время^[85]. Также аналогично, графы с инвариантом Колена де Вердьера не выше четырёх — именно графы с вложением без зацеплений.