Об обобщенных плоских графах и обобщенных внешнепланарных графах

Любой плоский , соответственно, внешний планарный граф удовлетворяет условию | E ′ | ≤ 3 | V ′ | - 6 , соответственно, | E ′ | ≤ 2 | V ′ | - 3 , для каждого подграфа G ' = ( V ' , E ' ) в G .$G=(V,E)$$|E'|\le 3|V'|-6$
$|E'|\le 2|V'|-3$$G'=(V',E')$$G$
Кроме того, (внешние) плоские графы могут быть распознаны за полиномиальное время.

Что известно о графах таких, что | E ′ | ≤ 3 | V ′ | - 6 (соответственно | E ′ | ≤ 2 | V ′ | - 3 ) для каждого подграфа G ′ = ( V ′ , E ′ ) группы G ? Можно ли их распознать за полиномиальное время?$G=(V,E)$$|E'|\le 3|V'|-6$$|E'|\le 2|V'|-3$$G'=(V',E')$$G$

Изменить (после хорошего ответа Эппштейна): Любой планарный граф удовлетворяет | E ′ | ≤ 3 | V ′ | - 6 для каждого подграфа G ′ = ( V ′ , E ′ ) группы G с хотя бы тремя вершинами | V ′ | ≥ $G=(V,E)$$|E'|\le 3|V'|-6$$G'=(V',E')$$G$ $|V'|\ge 3$, Таким образом, «обобщенные плоские графы» - это те, которые удовлетворяют этому свойству, и их распознавание за полиномиальное время представляется (интересным) открытым вопросом.

В обозначениях Ли и Стрейну (цитата ниже) вторым классом, который вы перечисляете, являются (2,3)-разреженные графы. Они дают алгоритм для проверки того, является ли граф (k, l) -разделенным за полиномиальное время. Однако ситуация с плоскими графами и является немного более сложным, потому что неравенство не верно для всех множеств вершин (если бы это было правдой, никакие две вершины не могут быть соединены ребром, потому что 3 ⋅ 2 - 6 = $|E'|\le 3|V'|-6$$3\cdot 2-6=0$). Таким образом, класс (3,6)-разреженных графов (в их обозначениях) состоит только из пустых графов. Вероятно, их алгоритмы можно распространить на графы, для которых выполняется неравенство для всех множеств более двух вершин.

Ли, Одри; Стрейну, Илеана (2008), «Алгоритмы игры в гальку и разреженные графы», Discrete Matmatics 308 (8): 1425–1437, doi: 10.1016 / j.disc.2007.07.104 , arxiv: math / 0702129 .

Что известно об «обобщенных внешнепланарных графах» или (2,3)-разреженных графах? Некоторые дополнительные факты к ответу Дэвида Эппштейна:

В 1982 г. в этой статье (следствия 1 и 2) Ловас и Йемини охарактеризовали обобщенные внешнепланарные графы (в их обозначениях - общие независимые графы ) как эти графы.$G$ имея свойство, которое удваивает любой край $G$ приводит к графу, который является объединением двух лесов, не пересекающим края.

Еще в 1970 году Хеннеберг и Ламан доказали, что обобщенные внешнепланарные графы могут быть рекурсивно получены из $K_2$ тремя так называемыми движениями Хеннеберга (добавление вершины степени 1, добавление вершины степени 2 и определенный вид добавления вершины степени 3).

Эти характеристики дают первые полиномиальные определения для обобщенных внешнепланарных графов.

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