K-внешнепланарный граф - K-outerplanar graph

3-внешнепланарный граф, граф ромбический додекаэдр. Есть четыре вершины на внешней грани, восемь вершин на втором слое (светло-желтый) и две вершины на третьем слое (темно-желтый). Из-за симметрии графа ни одно другое вложение не имеет меньшего количества слоев.

В теория графов, а k-аплоскостной граф это планарный граф который имеет планарное вложение, в котором вершины принадлежат не более чем ${ displaystyle k}$ концентрические слои. В индекс внешней планарности планарного графа - это минимальное значение ${ displaystyle k}$ для чего это ${ displaystyle k}$ -аплоскостной.

Определение

An внешнепланарный граф (или 1-внешнепланарный граф) имеет все вершины на неограниченной (внешней) грани графа. 2-внешнепланарный граф - это планарный граф, обладающий тем свойством, что при удалении вершин на неограниченной грани все оставшиеся вершины лежат на вновь сформированной неограниченной грани. И так далее.

Более формально график ${ displaystyle k}$ -outerplanar, если он имеет такое плоское вложение, что для каждой вершины существует чередующаяся последовательность не более ${ displaystyle k}$ лица и ${ displaystyle k}$ вершины вложения, начиная с неограниченной грани и заканчивая вершиной, в которой каждая последующая грань и вершина инцидентны друг другу.

Свойства и приложения

В ${ displaystyle k}$ -непланарные графы имеют ширина дерева в большинстве ${ displaystyle 3k-1}$ .^[1] Однако некоторые планарные графы с ограниченной шириной, такие как граф вложенных треугольников может быть ${ displaystyle k}$ - внешнепланарный только для очень больших ${ displaystyle k}$ , линейная по количеству вершин.

Техника Бейкера покрывает планарный граф с постоянным числом ${ displaystyle k}$ -outerplanar графики и использует их малую ширину дерева, чтобы быстро аппроксимировать несколько задач оптимизации жесткого графа.^[2]

В связи с Гипотеза GNRS о метрическом вложении семейств минно-замкнутых графов ${ displaystyle k}$ -Внешнепланарные графы - один из самых общих классов графов, для которых гипотеза доказана.^[3]

Предполагаемое обращение Теорема Курселя, согласно которому каждое свойство графа, распознаваемое на графах ограниченной ширины дерева автоматами конечного дерева, определимо в монадическом порядке второго порядка. логика графиков, было доказано для ${ displaystyle k}$ -аплоские графы.^[4]

Признание

Наименьшее значение ${ displaystyle k}$ для которого данный граф ${ displaystyle k}$ -outerplanar (его индекс внешней планарности) может быть вычислен за квадратичное время.^[5]

использованная литература

^ Бодландер, Ханс Л. (1998), "Частичный ${ displaystyle k}$ -арборетум графов с ограниченной шириной дерева », Теоретическая информатика, 209 (1–2): 1–45, Дои:10.1016 / S0304-3975 (97) 00228-4, HDL:1874/18312, Г-Н 1647486
^ Бейкер, Б. (1994), "Алгоритмы приближения для NP-полных задач на плоских графах", Журнал ACM, 41 (1): 153–180, Дои:10.1145/174644.174650, S2CID 9706753.
^ Чекури, Чандра; Гупта, Анупам; Ньюман, Илан; Рабинович, Юрий; Синклер, Алистер (2006), «Встраивание ${ displaystyle k}$ -непланарные графы в ${ displaystyle ell _ {1}}$ ", Журнал SIAM по дискретной математике, 20 (1): 119–136, Дои:10.1137 / S0895480102417379, Г-Н 2257250, S2CID 13925350
^ Джаффке, Ларс; Бодландер, Ханс Л.; Хеггернес, Пинар; Телле, Ян Арне (2017), "Определимость означает узнаваемость ${ displaystyle k}$ -непланарные графы и ${ displaystyle ell}$ -хордальная частичная ${ displaystyle k}$ -деревья ", Европейский журнал комбинаторики, 66: 191–234, Дои:10.1016 / j.ejc.2017.06.025, Г-Н 3692146
^ Каммер, Франк (2007), «Определение самого маленького ${ displaystyle k}$ такой, что ${ displaystyle G}$ является ${ displaystyle k}$ -outerplanar », в Arge, Lars; Hoffmann, Michael; Welzl, Emo (ред.), Алгоритмы: ESA 2007, 15-й ежегодный европейский симпозиум, Эйлат, Израиль, 8-10 октября 2007 г., Материалы, Конспект лекций по информатике, 4698, Springer, стр. 359–370, Дои:10.1007/978-3-540-75520-3_33

[1] Бодландер, Ханс Л. (1998), "Частичный ${ displaystyle k}$ -арборетум графов с ограниченной шириной дерева », Теоретическая информатика, 209 (1–2): 1–45, Дои:10.1016 / S0304-3975 (97) 00228-4, HDL:1874/18312, Г-Н 1647486

[2] Бейкер, Б. (1994), "Алгоритмы приближения для NP-полных задач на плоских графах", Журнал ACM, 41 (1): 153–180, Дои:10.1145/174644.174650, S2CID 9706753.

[3] Чекури, Чандра; Гупта, Анупам; Ньюман, Илан; Рабинович, Юрий; Синклер, Алистер (2006), «Встраивание ${ displaystyle k}$ -непланарные графы в ${ displaystyle ell _ {1}}$ ", Журнал SIAM по дискретной математике, 20 (1): 119–136, Дои:10.1137 / S0895480102417379, Г-Н 2257250, S2CID 13925350

[4] Джаффке, Ларс; Бодландер, Ханс Л.; Хеггернес, Пинар; Телле, Ян Арне (2017), "Определимость означает узнаваемость ${ displaystyle k}$ -непланарные графы и ${ displaystyle ell}$ -хордальная частичная ${ displaystyle k}$ -деревья ", Европейский журнал комбинаторики, 66: 191–234, Дои:10.1016 / j.ejc.2017.06.025, Г-Н 3692146

[5] Каммер, Франк (2007), «Определение самого маленького ${ displaystyle k}$ такой, что ${ displaystyle G}$ является ${ displaystyle k}$ -outerplanar », в Arge, Lars; Hoffmann, Michael; Welzl, Emo (ред.), Алгоритмы: ESA 2007, 15-й ежегодный европейский симпозиум, Эйлат, Израиль, 8-10 октября 2007 г., Материалы, Конспект лекций по информатике, 4698, Springer, стр. 359–370, Дои:10.1007/978-3-540-75520-3_33

[1]

[2]

[3]

[4]

[5]