Универсальный набор точек

Точки, которые можно использовать для рисования любого плоского графа

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

Имеют ли планарные графы универсальные множества точек субквадратичного размера?

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

В рисовании графов универсальное множество точек порядка n — это множество S точек на евклидовой плоскости со следующим свойством: каждый планарный граф с n вершинами имеет прямолинейный рисунок , в котором все вершины расположены в точках S.

Границы размера универсальных точечных множеств

Рисунок сетки вложенного треугольника графа . На любом рисунке этого графа по крайней мере половина треугольников должна образовывать вложенную цепь, что требует ограничивающего прямоугольника размером по крайней мере n /3 ×  n /3. Показанная здесь компоновка близка к этому, используя размер приблизительно n /3 ×  n /2

Когда n равно десяти или меньше, существуют универсальные множества точек, содержащие ровно n точек, но для всех n  ≥ 15 требуются дополнительные точки. ^[1]

Несколько авторов показали, что подмножества целочисленной решетки размера O ( n ) ×  O ( n ) являются универсальными. В частности, de Fraysseix, Pach & Pollack (1988) показали, что сетка из (2 n  − 3) × ( n  − 1) точек является универсальной, а Schnyder (1990) свел ее к треугольному подмножеству сетки ( n  − 1) × ( n  − 1) с n ² /2 −  O ( n ) точками. Модифицируя метод de Fraysseix et al., Brandenburg (2008) нашел вложение любого планарного графа в треугольное подмножество сетки, состоящее из 4 n ² /9 точек. Универсальное множество точек в форме прямоугольной сетки должно иметь размер не менее n /3 ×  n /3 ^[2] , но это не исключает возможности меньших универсальных множеств точек других типов. Наименьшие известные универсальные множества точек не основаны на сетках, а вместо этого построены из супершаблонов ( перестановок , которые содержат все шаблоны перестановок заданного размера); универсальные множества точек, построенные таким образом, имеют размер n ² /4 −  Θ ( n ). ^[3]

de Fraysseix, Pach & Pollack (1988) доказали первую нетривиальную нижнюю границу размера универсального множества точек с границей вида n  + Ω(√ n ), а Chrobak & Karloff (1989) показали, что универсальные множества точек должны содержать не менее 1,098 n  −  o ( n ) точек. Куровски (2004) установил еще более сильную границу 1,235 n  −  o ( n ), ^[4] которая была дополнительно улучшена Шейхером, Шрезенмайером и Штайнером (2018) до 1,293 n  −  o ( n ).

Устранение разрыва между известными линейными нижними границами и квадратичными верхними границами остается открытой проблемой. ^[5]

Специальные классы графов

Подклассы планарных графов могут, в общем, иметь меньшие универсальные множества (множества точек, которые позволяют рисовать прямолинейные линии всех n -вершинных графов в подклассе), чем полный класс планарных графов, и во многих случаях возможны универсальные множества точек, состоящие ровно из n точек. Например, нетрудно увидеть, что каждое множество из n точек в выпуклом положении (образующее вершины выпуклого многоугольника) является универсальным для n -вершинных внешнепланарных графов , и в частности для деревьев . Менее очевидно, что каждое множество из n точек в общем положении (никаких трех коллинеарных) остается универсальным для внешнепланарных графов. ^[6]

Планарные графы, которые можно разбить на вложенные циклы, 2-внешнепланарные графы и планарные графы ограниченной ширины пути , имеют универсальные множества точек почти линейного размера. ^[7] Планарные 3-деревья имеют универсальные множества точек размера O ( n ^3/2 log n ); та же граница применима и к последовательно-параллельным графам . ^[8]

Другие стили рисования

Дуговая диаграмма

Как и для рисования прямолинейного графика, универсальные наборы точек изучались для других стилей рисования; во многих из этих случаев существуют универсальные наборы точек с ровно n точками, основанные на топологическом книжном вложении , в котором вершины располагаются вдоль линии на плоскости, а ребра рисуются как кривые, пересекающие эту линию не более одного раза. Например, каждый набор из n коллинеарных точек универсален для дуговой диаграммы , в которой каждое ребро представлено либо как один полукруг , либо как гладкая кривая, образованная двумя полукругами. ^[9]

Используя подобную схему, можно показать, что каждая строго выпуклая кривая на плоскости содержит n -точечное подмножество, которое является универсальным для рисования полилиний с максимум одним изгибом на ребро . ^[10] Этот набор содержит только вершины рисунка, а не изгибы; известны более крупные наборы, которые можно использовать для рисования полилиний со всеми вершинами и всеми изгибами, размещенными внутри набора. ^[11]

Примечания

1. Кардинал, Хоффманн и Кастерс (2015).
2. Dolev, Leighton & Trickey (1984); Chrobak & Karloff (1989); Demaine & O'Rourke (2002–2012). Более слабая квадратичная нижняя граница размера сетки, необходимая для рисования планарного графа, была ранее дана Valiant (1981).
3. Баннистер и др. (2013).
4. Мондал (2012) утверждал, что доказательство Куровски было ошибочным, но позже (после обсуждения с Джин Кардинал) отказался от этого утверждения; см. Explanation Supporting Kurowski's Proof, D. Mondal, обновлено 9 августа 2013 г.
5. Демейн и О'Рурк (2002–2012); Бранденбург и др. (2003); Мохар (2007).
6. Грицманн и др. (1991).
7. Анджелини и др. (2018); Баннистер и др. (2013).
8. Фулек и Тот (2015)
9. Джордано и др. (2007).
10. Эверетт и др. (2010).
11. Дуймович и др. (2013).

Ссылки

• Анджелини, Патрицио; Брукдорфер, Тилль; Ди Баттиста, Джузеппе; Кауфманн, Майкл; Мчедлидзе Тамара; Роселли, Винченцо; Скварселла, Клаудио (2018), «Малые универсальные наборы точек для k-внепланарных графов», Дискретная и вычислительная геометрия , 60 (2): 430–470, doi : 10.1007/s00454-018-0009-x , S2CID  51907835.
• Баннистер, Майкл Дж.; Ченг, Чжаньпэн; Деванни, Уильям Э.; Эппштейн, Дэвид (2013), «Суперпаттерны и универсальные точечные множества», Труды 21-го Международного симпозиума по рисованию графов (GD 2013) , arXiv : 1308.0403 , Bibcode : 2013arXiv1308.0403B, doi : 10.7155/jgaa.00318, S2CID  6229641.
• Бранденбург, Франц Дж. (2008), «Рисование планарных графов на площади», Международная конференция по топологической и геометрической теории графов , Электронные заметки по дискретной математике, т. 31, Elsevier, стр. 37–40, doi :10.1016/j.endm.2008.06.005, MR  2571101 ${\displaystyle {\tfrac {8}{9}}n^{2}}$.
• Бранденбург, Франц-Йозеф; Эппштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г.; Лиотта, Джузеппе; Мютцель, Петра (2003), «Избранные открытые проблемы в рисовании графов», в Liotta, Giuseppe (ред.), Рисование графов: 11-й международный симпозиум, GD 2003, Перуджа, Италия, 21–24 сентября 2003 г. Пересмотренные статьи , Конспект лекций по информатике, т. 2912, Springer-Verlag, стр. 515–539, doi : 10.1007/978-3-540-24595-7_55. См. в частности задачу 11 на стр. 520.
• Кардинал, Жан; Хоффманн, Майкл; Кустерс, Винсент (2015), «Об универсальных точечных множествах для планарных графов», Журнал графовых алгоритмов и приложений , 19 (1): 529–547, arXiv : 1209.3594 , doi : 10.7155/jgaa.00374, MR  3420760, S2CID  39043733
• Chrobak, M.; Karloff, H. (1989), «Нижняя граница размера универсальных множеств для планарных графов», SIGACT News , 20 (4): 83–86, doi :10.1145/74074.74088, S2CID  7188305.
• де Фрейссе, Хуберт; Пах, Янош ; Поллак, Ричард (1988), «Малые множества, поддерживающие вложения Фари планарных графов», Двадцатый ежегодный симпозиум ACM по теории вычислений , стр. 426–433, doi : 10.1145/62212.62254 , ISBN 0-89791-264-0, S2CID  15230919.
• Demaine, E. ; O'Rourke, J. (2002–2012), «Задача 45: Наименьший универсальный набор точек для планарных графов», The Open Problems Project , получено 19.03.2013.
• Долев, Дэнни ; ​​Лейтон, Том ; Трики, Ховард (1984), «Планарное вложение планарных графов» (PDF) , Достижения в области компьютерных исследований , 2 : 147–161.
• Dujmović, V. ; Evans, WS; Lazard, S.; Lenhart, W.; Liotta, G.; Rappaport, D.; Wismath, SK (2013), "О точечных множествах, поддерживающих планарные графы", Comput. Geom. Theory Appl. , 46 (1): 29–50, doi : 10.1016/j.comgeo.2012.03.003.
• Эверетт, Хейзел; Лазар, Сильвен; Лиотта, Джузеппе; Висмат, Стивен (2010), «Универсальные наборы из n точек для одноизгибных рисунков планарных графов с n вершинами», Дискретная и вычислительная геометрия , 43 (2): 272–288, doi : 10.1007/s00454-009-9149-3.
• Фулек, Радослав; Тот, Чаба Д. (2015), «Универсальные точечные множества для плоских трехмерных деревьев», Журнал дискретных алгоритмов , 30 : 101–112, arXiv : 1212.6148 , doi : 10.1016/j.jda.2014.12.005, MR  3305154, S2CID  1597229
• Джордано, Франческо; Лиотта, Джузеппе; Мчедлидзе, Тамара; Симвонис, Антониос (2007), «Вычисление восходящих топологических книжных вложений восходящих планарных орграфов», Алгоритмы и вычисления: 18-й международный симпозиум, ISAAC 2007, Сендай, Япония, 17–19 декабря 2007 г., Труды , Lecture Notes in Computer Science, т. 4835, Springer, стр. 172–183, doi :10.1007/978-3-540-77120-3_17.
• Gritzmann, P.; Mohar, B .; Pach, János ; Pollack, Richard (1991), «Вложение плоской триангуляции с вершинами в указанных положениях», American Mathematical Monthly , 98 (2): 165–166, doi :10.2307/2323956, JSTOR  2323956.
• Куровски, Мачей (2004), «Нижняя граница в 1,235 для числа точек, необходимых для рисования всех n -вершинных планарных графов», Information Processing Letters , 92 (2): 95–98, doi :10.1016/j.ipl.2004.06.009, MR  2085707.
• Mohar, Bojan (2007), "Универсальные множества точек для планарных графов", Open Problem Garden , получено 20.03.2013.
• Мондал, Дебайоти (2012), Вложение планарного графа в заданный набор точек , магистерская диссертация, кафедра компьютерных наук, Университет Манитобы , hdl :1993/8869.
• Шойхер, Манфред; Шрезенмайер, Хендрик; Штайнер, Рафаэль (2018), Примечание об универсальных наборах точек для планарных графов , arXiv : 1811.06482 , Bibcode : 2018arXiv181106482S.
• Шнайдер, Вальтер (1990), «Встраивание планарных графов в сетку», Труды 1-го симпозиума ACM/SIAM по дискретным алгоритмам (SODA), стр. 138–148, ISBN 9780898712513.
• Валиант, LG (1981), «Вопросы универсальности в схемах СБИС», IEEE Transactions on Computers , C-30 (2): 135–140, doi :10.1109/TC.1981.6312176, S2CID  1450313