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

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

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

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

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

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

Граф вложенных треугольников был назван Долевым, Лейтоном и Трики (1984) , которые использовали его, чтобы показать, что для рисования планарного графа с n вершинами в целочисленной решетке (с ребрами из прямых отрезков ) может потребоваться ограничивающий прямоугольник размером не менее п /3 × п /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-видимостью», Норт, Стивен (редактор), Рисование графиков: Симпозиум по рисованию графов, GD '96, Беркли, Калифорния, США, 18–20 сентября 1996 г., Труды , Конспекты лекций по информатике, вып. 1190, стр. 155–168, doi : 10.1007/3-540-62495-3_45 .
^ Дидимо, Уолтер; Лиотта, Джузеппе (2013), «Разрешение угла пересечения при рисовании графиков», в Пач, Янош (ред.), « Тридцать эссе по геометрической теории графов » , Springer, стр. 167–184, doi : 10.1007/978-1- 4614-0110-0_10 .
^ ван Кревелд, Марк (2011), «Соотношение качества рисунков RAC и плоских рисунков плоских графов», в Брандесе, Ульрике ; Корнельсен, Сабина (ред.), Рисование графиков: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 6502, стр. 371–376, номер документа : 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-видимостью», Норт, Стивен (редактор), Рисование графиков: Симпозиум по рисованию графов, GD '96, Беркли, Калифорния, США, 18–20 сентября 1996 г., Труды , Конспекты лекций по информатике, вып. 1190, стр. 155–168, doi : 10.1007/3-540-62495-3_45 .

[4] Дидимо, Уолтер; Лиотта, Джузеппе (2013), «Разрешение угла пересечения при рисовании графиков», в Пач, Янош (ред.), « Тридцать эссе по геометрической теории графов » , Springer, стр. 167–184, doi : 10.1007/978-1- 4614-0110-0_10 .

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]