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

Материал из testwiki
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

  1. ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb. Более слабую квадратичную границу на размер решётки, требуемой для рисунки планарного графа, дал до этого Валиант Шаблон:Harvtxt.
  2. ↑ Мондал Шаблон:Harv утверждал, что доказательство Куровски ошибочно, но позднее (после дискуссии с Джином Кардиналом) отозвал своё утверждение. См. Объяснение доказательства Куровски Шаблон:Wayback.
  3. ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Универсальное_множество_точек&oldid=18345