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

Нерешенная проблема в математике: Есть ли в плоских графах универсальные наборы точек субквадратичного размера? (больше нерешенных задач по математике)

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

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

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

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

Несколько авторов показали, что подмножества целочисленная решетка размера О(п) × О(п) универсальны. Особенно, де Фрейссе, Пах и Поллак (1988) показал, что сетка (2п − 3) × (п - 1) очки универсальны, а Шнайдер (1990) свел это к треугольному подмножеству (п − 1) × (п - 1) сетка, с п²/2 − О(п) точки. Изменяя метод de Fraysseix et al., Бранденбург (2008) нашли вложение любого плоского графа в треугольное подмножество сетки, состоящей из 4п²/ 9 баллов. Универсальный набор точек в виде прямоугольной сетки должен иметь размер не менее п/3 × п/3^[2] но это не исключает возможности меньших универсальных наборов точек других типов. Наименьшие известные универсальные точечные множества не основаны на сетках, а построены из суперпаттерны (перестановки которые содержат все шаблоны перестановок заданного размера); построенные таким образом универсальные точечные множества имеют размер п²/4 − О(п).^[3]

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

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

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

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

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

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

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

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

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

Примечания

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