k -внепланарный граф

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

Определение

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

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

Свойства и применение

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

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

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

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

Признание

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

Ссылки

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

[1] Бодлендер, Ханс Л. (1998), "Частичное $k$ -дендрарий графов с ограниченной шириной дерева», Theoretical Computer Science , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4 , hdl : 1874/18312 , MR 1647486

[2] Бейкер, Б. (1994), «Алгоритмы аппроксимации NP-полных задач на плоских графах», Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID 9706753 .

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

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

[5] Каммер, Франк (2007), "Определение наименьшего $k$ такой, что $G$ является $k$ -outerplanar», в Арге, Ларс; Хоффманн, Михаэль; Вельцль, Эмо (ред.), Алгоритмы: ESA 2007, 15-й ежегодный европейский симпозиум, Эйлат, Израиль, 8-10 октября 2007 г., Труды , конспекты лекций по информатике, том 4698, Springer, стр. 359–370, doi : 10.1007/978-3-540-75520-3_33

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]