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

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

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

Полиэдральное представление

Двуусечённая бипирамида

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

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

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

Рисунок графа вложенных треугольников на решётке. Это представление использует меньшую площадь, чем представление Фрати и Патригнани[1], но, в отличие от их представления, не обобщается до максимального планарного суперграфа графа вложенных треугольников.

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

Для рисунков, в которых внешняя грань может свободно выбираться, нижняя граница площади Долева, Лейтона и Трики[2] может не быть жёсткой. Фрати и Патригнани[1] показали, что этот граф и любой граф, образованный добавлением диагоналей к его четырёхугольникам, может быть нарисован в прямоугольнике размером . Если никаких дополнительных диагоналей не добавлено, граф вложенных треугольников может быть нарисован даже с меньшей площадью, примерно как на рисунке. Закрытие промежутка между верхней границей и нижней границей площади максимального планарного дополнения вложенного треугольного графа остаётся открытой проблемой[4].

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

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

Примечания

Литература

  • Danny Dolev, F. Thomson Leighton, Howard Trickey. Planar embedding of planar graphs // Advances in Computing Research. — 1984. Т. 2. С. 147–161.
  • Fabrizio Frati, Maurizio Patrignani. A note on minimum-area straight-line drawings of planar graphs // Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers. — Berlin: Springer, 2008. — Т. 4875. — С. 339–344. — (Lecture Notes in Computer Science). doi:10.1007/978-3-540-77537-9_33.
  • Ulrich Fößmeier, Goos Kant, Michael Kaufmann. 2-visibility drawings of planar graphs // Graph Drawing: Symposium on Graph Drawing, GD '96 Berkeley, California, USA, September 18–20, 1996, Proceedings. — 1997. — Т. 1190. — С. 155–168. — (Lecture Notes in Computer Science). doi:10.1007/3-540-62495-3_45.
  • Walter Didimo, Giuseppe Liotta. The crossing-angle resolution in graph drawing // Thirty Essays on Geometric Graph Theory / János Pach. — Springer, 2013. — С. 167–184. doi:10.1007/978-1-4614-0110-0_10.
  • Marc van Kreveld. The quality ratio of RAC drawings and planar drawings of planar graphs // Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. — 2011. — Т. 6502. — С. 371–376. — (Lecture Notes in Computer Science). doi:10.1007/978-3-642-18469-7_34.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.