Вложенный график треугольников - Nested triangles graph

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

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

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

Двустворчатый треугольный

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

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

Нижние границы области для чертежей графиков

Сеточный рисунок графа вложенных треугольников. Этот макет занимает меньше площади, чем Фрати и Патриньяни (2008) но в отличие от их не обобщается на максимальные плоские суперграфы графа вложенных треугольников.

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

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Какова минимальная площадь ограничивающего прямоугольника сеточного чертежа графа вложенных треугольников или его максимальных планарных завершений?
(больше нерешенных задач по математике)

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

Рекомендации

  1. ^ Долев, Дэнни; Лейтон, Том; Трики, Ховард (1984), «Планарное вложение плоских графов» (PDF), Достижения в компьютерных исследованиях, 2: 147–161
  2. ^ Фрати, Фабрицио; Патриньяни, Маурицио (2008), «Заметка о прямолинейных чертежах плоских графов с минимальной площадью», Графический рисунок: 15-й Международный симпозиум, GD 2007, Сидней, Австралия, 24-26 сентября 2007 г., Исправленные статьи, Конспект лекций по информатике, 4875, Берлин: Springer, стр. 339–344, Дои:10.1007/978-3-540-77537-9_33, МИСТЕР  2427831.
  3. ^ Фессмайер, Ульрих; Кант, Гус; Кауфманн, Майкл (1997), «Рисунки 2-видимости плоских графов», в North, Stephen (ed.), Рисование графиков: симпозиум по рисованию графиков, GD '96, Беркли, Калифорния, США, 18–20 сентября 1996 г., Труды, Конспект лекций по информатике, 1190, стр. 155–168, Дои:10.1007/3-540-62495-3_45.
  4. ^ Дидимо, Уолтер; Лиотта, Джузеппе (2013), «Разрешение угла пересечения в графическом изображении», в Пах, Янош (ред.), Тридцать очерков по теории геометрических графов, Springer, стр. 167–184, Дои: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.