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

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

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

(еще нерешенные задачи по математике)

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

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

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

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

Несколько авторов показали, что подмножества целочисленной решетки размера O ( n ) × O ( n ) универсальны. В частности, де Фрейссе, Пач и Поллак (1988) показали, что сетка из (2 n - 3) × ( n - 1) точек является универсальной, а Шнайдер (1990) свел ее к треугольному подмножеству из ( n - 1) точек. ) × ( n − 1) сетка, с n ² /2 − O ( n ) баллов. Модифицировав метод де Фрессейкса и др., Бранденбург (2008) обнаружил вложение любого плоского графа в треугольное подмножество сетки, состоящее из 4 n ² /9 баллов. Универсальное множество точек в виде прямоугольной сетки должно иметь размер не менее n /3× n /3. но это не исключает возможности существования меньших универсальных множеств других типов. Наименьшие известные универсальные наборы точек не основаны на сетках, а вместо этого состоят из супершаблонов ( перестановок , которые содержат все шаблоны перестановок заданного размера); построенные таким образом универсальные множества точек имеют размер n ² /4 - Θ ( п ).

де Фрейссе, Пач и Поллак (1988) доказали первую нетривиальную нижнюю оценку размера универсального множества точек с оценкой вида n + Ω(√ n ), а Хробак и Карлофф (1989) показали, что универсальные множества точек должно содержать не менее 1,098 n − o ( n ) точек. Куровский (2004) установил еще более строгую оценку 1,235 n - o ( n ), которое было дополнительно улучшено Шойхером, Шрезенмайером и Штайнером (2018) до 1,293 n - o ( n ).

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

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

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

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

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

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

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

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

Ссылки

• Анджелини, Патрицио; Брукдорфер, Тилль; Ди Баттиста, Джузеппе; Кауфманн, Майкл; Мчедлидзе Тамара; Роселли, Винченцо; Скварселла, Клаудио (2018), «Малые универсальные наборы точек для k-внепланарных графов», Discrete & Computational Geometry , 60 (2): 430–470, doi : 10.1007/s00454-018-0009-x , S2CID   51907835 .
• Баннистер, Майкл Дж.; Ченг, Чжанпэн; Девэнни, Уильям Э.; Эппштейн, Дэвид (2013), «Суперпаттерны и универсальные множества точек», Proc. 21-й Международный симпозиум по рисованию графов (GD 2013) , arXiv : 1308.0403 , Bibcode : 2013arXiv1308.0403B , doi : 10.7155/jgaa.00318 , S2CID   6229641 .
• Бранденбург, Франц Дж. (2008), «Рисование плоских графов на ${\tfrac {8}{9}}n^{2}$ область», Международная конференция по топологической и геометрической теории графов , Электронные заметки по дискретной математике, том 31, Elsevier, стр. 37–40, doi : 10.1016/j.endm.2008.06.005 , MR   2571101 .
• Бранденбург, Франц-Иосиф; Эппштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г.; Лиотта, Джузеппе; Мутцель, Петра (2003), «Избранные открытые проблемы рисования графов», Лиотта, Джузеппе (редактор), Рисование графов: 11-й Международный симпозиум, GD 2003, Перуджа, Италия, 21–24 сентября 2003 г. Переработанные статьи , конспекты лекций в области компьютерных наук, вып. 2912, Springer-Verlag, стр. 515–539, номер документа : 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
• Хробак, М.; Карлофф, Х. (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 .
• Демейн, Э .; О'Рурк, Дж. (2002–2012), «Проблема 45: Наименьший универсальный набор точек для плоских графов», Проект открытых проблем , получено 19 марта 2013 г.
• Долев, Дэнни ; Лейтон, Том ; Трики, Ховард (1984), «Планарное встраивание планарных графов» (PDF) , «Достижения в области компьютерных исследований» , 2 : 147–161 .
• Дуймович, В. ; Эванс, штат Вашингтон; Лазард, С.; Ленхарт, В.; Лиотта, Г.; Раппапорт, Д.; Висмат, С.К. (2013), «О множествах точек, поддерживающих плоские графы», Comput. Геом. Теория Прикл. , 46 (1): 29–50, номер документа : 10.1016/j.comgeo.2012.03.003 .
• Эверетт, Хейзел; Лазар, Сильвен; Лиотта, Джузеппе; Висмат, Стивен (2010), «Универсальные наборы n точек для одноизгибных рисунков плоских графов с n вершинами» , Discrete and Computational Geometry , 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 г., Труды , Конспекты лекций по информатике, том . 4835, Springer, стр. 172–183, номер документа : 10.1007/978-3-540-77120-3_17 .
• Грицманн, П.; Мохар, Б. ; Пах, Янош ; Поллак, Ричард (1991), «Вложение плоской триангуляции с вершинами в заданных положениях», American Mathematical Monthly , 98 (2): 165–166, doi : 10.2307/2323956 , JSTOR   2323956 .
• Куровски, Мачей (2004), «Нижняя граница количества точек, необходимых для рисования всех с n планарных графов -вершинами, 1,235», Information Processing Letters , 92 (2): 95–98, doi : 10.1016/j.ipl.2004.06 .009 , МР   2085707 .
• Мохар, Боян (2007), «Универсальные множества точек для плоских графов», Open Issue Garden , получено 20 марта 2013 г.
• Мондал, Дебаджьоти (2012), Встраивание плоского графа в заданный набор точек , магистерская диссертация, факультет компьютерных наук, Университет Манитобы , hdl : 1993/8869 .
• Шойхер, Манфред; Шрезенмайер, Хендрик; Штайнер, Рафаэль (2018), Заметка об универсальных наборах точек для планарных графов , arXiv : 1811.06482 , Bibcode : 2018arXiv181106482S .
• Шнайдер, Уолтер (1990), «Вложение плоских графов в сетку», Proc. 1-й симпозиум ACM/SIAM по дискретным алгоритмам (SODA) , стр. 138–148, ISBN  9780898712513 .
• Валиант, Л.Г. (1981), «Соображения универсальности в схемах СБИС», IEEE Transactions on Computers , C-30 (2): 135–140, doi : 10.1109/TC.1981.6312176 , S2CID   1450313