Граф вложенных треугольников
Граф вложенных треугольников с n вершинами — это планарный граф, образованный последовательностью n/3 треугольников, соответствующие пары вершин которых соединяются рёбрами. Он может быть образован также геометрически путём склеивания вместе треугольных призм по их треугольным граням. Этот граф и тесно связанные графы часто используются в области визуализации графов для доказательства нижних границ требующейся площади при различных стилях рисования.
Полиэдральное представление
Граф вложенных треугольников с двумя треугольниками является графом треугольной призмы, а граф вложенных треугольников с тремя треугольниками — это граф Шаблон:Не переведено 5. Более обще, поскольку графы встроенных треугольников планарны и вершинно 3-связны, из теоремы Штайница следует, что все они могут быть представлены как выпуклые многогранники.
Альтернативное геометрическое представление этих графов может быть задано путём склеивания треугольных призм по треугольным граням. Число вложенных треугольников на единицу больше числа склеенных призм. Однако при использовании прямоугольных призм процесс их склеивания приводит к тому, что смежные прямоугольные грани компланарны, так что в результате не получим строго выпуклое тело. Шаблон:-
Нижние границы площади для рисунков графов
Название «граф вложенных треугольников» предложили Долев, Лейтон и ТрикиШаблон:Sfn, которые использовали его, чтобы показать, что рисунок планарного графа с n вершинами на целочисленной решётке (с рёбрами в виде отрезков) может потребовать ограничивающий прямоугольник размера по меньшей мере Шаблон:Sfn. В таком рисунке не имеет значения, какая грань выбрана в качестве внешнего ребра, некоторая подпоследовательность по меньшей мере в n/6 треугольников должна быть нарисована вложенными друг в друга и в этой части рисунка каждый треугольник должен использовать на две строки и на два столбца больше, чем следующий внутренний треугольник. Если выбор внешней грани не позволен как часть алгоритма рисования, но задан как часть входа, те же доводы показывают, что необходим ограничивающий прямоугольник размера и рисунок с такими размерами существует.
Для рисунков, в которых внешняя грань может свободно выбираться, нижняя граница площади Долева, Лейтона и ТрикиШаблон:Sfn может не быть жёсткой. Фрати и ПатригнаниШаблон:Sfn показали, что этот граф и любой граф, образованный добавлением диагоналей к его четырёхугольникам, может быть нарисован в прямоугольнике размером . Если никаких дополнительных диагоналей не добавлено, граф вложенных треугольников может быть нарисован даже с меньшей площадью, примерно как на рисунке. Закрытие промежутка между верхней границей и нижней границей площади максимального планарного дополнения вложенного треугольного графа остаётся открытой проблемойШаблон:Sfn.
Шаблон:Unsolved Варианты вложенных треугольных графов использовались для многих других построениях нижних границ при рисовании графов, например по площади прямоугольного представления (когда вершины представлены прямоугольниками, а рёбра рисуются как ломаные с параллельными осям частями)Шаблон:Sfn, площади рисунков с перпендикулярными пересечениямиШаблон:Sfn или относительной площади планарного представления по сравнению с непланарнымШаблон:Sfn.