Универсальное множество точек

Нерешённые проблемы математики: Размер универсальных множеств точек планарных графов подквадратичен?

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

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

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

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

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

Фрейсикс, Пах и Поллак доказали первую нетривиальную нижнюю границу размера универсального множества точек в виде n + Ω(√n), а Хробак и Карлофф показали, что универсальное множество точек должно содержать по меньшей мере 1.098n − o(n) точек. Куровски предложил даже более сильную границу 1.235n − o(n), которая остаётся лучшей нижней границей .

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

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

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

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

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

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

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

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