Граф вложенных треугольников

Плоский граф, используемый в качестве контрпримера

В теории графов граф вложенных треугольников с n вершинами — это планарный граф , образованный из последовательности n /3 треугольников путем соединения пар соответствующих вершин на последовательных треугольниках в последовательности. Его также можно образовать геометрически, склеивая n /3 − 1 треугольных призм на их треугольных гранях. Этот граф и тесно связанные с ним графы часто использовались в рисовании графов для доказательства нижних границ требований к площади различных стилей рисунков.

Многогранное представление

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

Другое геометрическое представление этих графов может быть дано путем склеивания треугольных призм конец к концу на их треугольных гранях; число вложенных треугольников на один больше, чем число склеенных призм. Однако, используя прямые призмы, этот процесс склеивания приведет к тому, что прямоугольные грани соседних призм будут копланарными, поэтому результат не будет строго выпуклым.

Нижние границы площади для графических рисунков

Граф вложенных треугольников был назван Долевом, Лейтоном и Трики (1984), которые использовали его, чтобы показать, что рисование n -вершинного планарного графа в целочисленной решетке (с прямыми ребрами отрезков линий ) может потребовать ограничивающего прямоугольника размером не менее n /3 × n /3. ^[1] На таком рисунке, независимо от того, какая грань графа выбрана в качестве внешней грани, некоторая подпоследовательность из не менее n /6 треугольников должна быть нарисована вложенной друг в друга, и в этой части рисунка каждый треугольник должен использовать на две строки и два столбца больше, чем следующий внутренний треугольник. Если внешняя грань не может быть выбрана как часть алгоритма рисования, но указана как часть входных данных, тот же аргумент показывает, что необходим ограничивающий прямоугольник размером 2 n /3 × 2 n /3, и рисунок с этими размерами существует.

Для рисунков, в которых внешняя грань может быть выбрана свободно, нижняя граница области Долева, Лейтона и Трики (1984) может быть не жесткой. Фрати и Патриньяни (2008) показали, что этот граф и любой граф, образованный добавлением диагоналей к его четырехугольникам, можно нарисовать в пределах поля размерами n /3 × 2 n /3. Когда не добавляются дополнительные диагонали, сам граф вложенных треугольников можно нарисовать в еще меньшей области, приблизительно n /3 × n /2, как показано. Закрытие разрыва между верхней границей 2 n ² /9 и нижней границей n ² /9 на области рисования для завершений графа вложенных треугольников остается открытой проблемой. ^[2]

Нерешенная задача по математике :

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

(еще нерешенные проблемы по математике)

Варианты графика вложенных треугольников использовались для многих других конструкций нижних границ в рисовании графов, например, для площади прямоугольных представлений видимости, ^[3] площади рисунков с прямыми углами ^[4] или относительной площади плоских и неплоских рисунков. ^[5]

Ссылки

^ Долев, Дэнни ; Лейтон, Том ; Трики, Ховард ( 1984 ), «Планарное вложение планарных графов» (PDF) , Достижения в области вычислительных исследований , 2 : 147–161
^ Фрати, Фабрицио; Патриньяни, Маурицио (2008), «Заметка о прямолинейных рисунках минимальной площади планарных графов», Рисование графов: 15-й международный симпозиум, GD 2007 , Сидней, Австралия, 24-26 сентября 2007 г., Пересмотренные документы , Заметки лекций по информатике , т. 4875, Берлин: Springer, стр. 339–344 , doi : 10.1007/978-3-540-77537-9_33 , MR 2427831.
^ Фёсмайер, Ульрих; Кант, Гус; Кауфманн, Михаэль (1997), «2-видимые рисунки планарных графов», в North, Stephen (ред.), Graph Drawing: Symposium on Graph Drawing, GD '96 Беркли, Калифорния, США, 18–20 сентября 1996 г., Труды , Lecture Notes in Computer Science, т. 1190, стр. 155–168 , doi : 10.1007/3-540-62495-3_45.
^ Дидимо, Вальтер; Лиотта, Джузеппе (2013), «Разрешение угла пересечения при рисовании графов», в Pach, János (ред.), Thirty Essays on Geometric Graph Theory , Springer, стр. 167–184 , doi :10.1007/978-1-4614-0110-0_10.
^ ван Кревелд, Марк (2011), «Соотношение качества рисунков RAC и планарных рисунков планарных графов», в Брандес, Ульрик ; Корнельсен, Сабина (ред.), Рисование графов: 18-й международный симпозиум, GD 2010, Констанц, Германия, 21-24 сентября 2010 г., пересмотренные избранные статьи , заметки лекций по информатике, т. 6502, стр. 371–376 , doi : 10.1007/978-3-642-18469-7_34.

[1] Долев, Дэнни ; Лейтон, Том ; Трики, Ховард ( 1984 ), «Планарное вложение планарных графов» (PDF) , Достижения в области вычислительных исследований , 2 : 147–161

[2] Фрати, Фабрицио; Патриньяни, Маурицио (2008), «Заметка о прямолинейных рисунках минимальной площади планарных графов», Рисование графов: 15-й международный симпозиум, GD 2007 , Сидней, Австралия, 24-26 сентября 2007 г., Пересмотренные документы , Заметки лекций по информатике , т. 4875, Берлин: Springer, стр. 339–344 , doi : 10.1007/978-3-540-77537-9_33 , MR 2427831.

[3] Фёсмайер, Ульрих; Кант, Гус; Кауфманн, Михаэль (1997), «2-видимые рисунки планарных графов», в North, Stephen (ред.), Graph Drawing: Symposium on Graph Drawing, GD '96 Беркли, Калифорния, США, 18–20 сентября 1996 г., Труды , Lecture Notes in Computer Science, т. 1190, стр. 155–168 , doi : 10.1007/3-540-62495-3_45.

[4] Дидимо, Вальтер; Лиотта, Джузеппе (2013), «Разрешение угла пересечения при рисовании графов», в Pach, János (ред.), Thirty Essays on Geometric Graph Theory , Springer, стр. 167–184 , doi :10.1007/978-1-4614-0110-0_10.

[5] ван Кревелд, Марк (2011), «Соотношение качества рисунков RAC и планарных рисунков планарных графов», в Брандес, Ульрик ; Корнельсен, Сабина (ред.), Рисование графов: 18-й международный симпозиум, GD 2010, Констанц, Германия, 21-24 сентября 2010 г., пересмотренные избранные статьи , заметки лекций по информатике, т. 6502, стр. 371–376 , doi : 10.1007/978-3-642-18469-7_34.