Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.
Границы размеров универсального множества точекПравить
Рисунок графа вложенных треугольников на решётке. В любом рисунке этого графа по меньшей мере половина треугольников должна иметь образовывать вложенную цепочку, так что потребуется ограничивающий прямоугольник размером по меньшей мере n/3 × n/3. Показанное на рисунке представление графа имеет близкое к этому значение n/3 × n/2
Если n не превосходит десяти, существует универсальное множество точек, имеющее в точности n точек, но для всех n ≥ 15 требуются дополнительные точки [1].
Некоторые авторы показали, что подмножество целочисленной решётки размера O(n) × O(n) является универсальным. В частности, Фрейсикс, Пах и Поллак[2] показали, что решётка (2n − 3) × (n − 1) является универсальной, а Шнайдер[3] уменьшил до треугольного подмножества решётки (n − 1) × (n − 1) с n2/2 − O(n) точками. Модифицируя метод Фрейсикса, Паха и Шнайдера, Бранденбург[4] нашёл вложение любого планарного графа в треугольное подмножество решётки, содержащей 4n2/9 точек. Универсальное множество точек в виде прямоугольной решётки должно иметь размер по меньшей мере n/3 × n/3 [5], но это не исключает возможность существования меньшего универсального множества точек других типов. Наименьшие известные универсальные множества точек не основаны на решётках, а строятся из суперсхем[en] (перестановок, содержащих все образы перестановок[en] заданного размера). Универсальные множества точек, построенные таким образом, имеют размер n2/4 − O(n)[6].
Фрейсикс, Пах и Поллак[2] доказали первую нетривиальную нижнюю границу размера универсального множества точек в виде n + Ω(√n), а Хробак и Карлофф[7] показали, что универсальное множество точек должно содержать по меньшей мере 1.098n − o(n) точек. Куровски[8] предложил даже более сильную границу 1.235n − o(n), которая остаётся лучшей нижней границей [9].
Закрытие промежутка между известными линейными границами и квадратичными верхними границами остаётся открытой проблемой[10].
Подклассы планарных графов могут, в общем случае, иметь меньшие универсальные множества (множества точек, которые позволяют рисование всех графов с n вершинами с прямыми рёбрами в подклассе), чем полный класс всех планарных графов, и во многих случаях существуют универсальные множества точек, имеющие в точности n точек. Например, несложно видеть, что любое множество из n точек в выпуклой позиции[en] (которые служат вершинами выпуклого многоугольника), является универсальным для n вершинных внешнепланарных графов, и, в частности, для деревьев. Менее очевидно, что любое множество из n точек в общем положении (никакие три не лежат на одной прямой) остаётся универсальным для внешнепланарных графов[11].
Планарные графы, которые могут быть разбиты на вложенные циклы, и планарные графы с ограниченной путевой шириной имеют универсальное множество точек почти линейного размера[12][6]. Планарные 3-деревья имеют универсальные множества точек размера O(n5/3). Та же самая граница имеет место для параллельно-последовательных графов[13].
Как и в случае рисования графов с прямыми рёбрами, универсальные множества точек изучались для других стилей. В большинстве этих случаев существуют универсальные множества точек, имеющие в точности n точек, и основываются они на топологическом книжном вложении, в котором вершины располагаются на прямой на плоскости, а рёбра рисуются как кривые, которые пересекают эту линию максимум один раз. Например, любое множество n коллинеарных точек является универсальным для дуговой диаграммы, в которой каждое ребро представлено либо как одна полуокружность, либо как гладкая кривая, образованная двумя полуокружностями[14].
Можно показать, что при использовании подобного расположения любая выпуклая кривая на плоскости содержит подмножество из n точек, которое является универсальным для рисунков в виде ломаных с максимум одним изломом на ребро[15]. Это множество содержит только вершины рисунка, но не точки излома. Известны бо́льшие множества, которые можно использовать для рисунков с помощью ломаных, в которых вершины и все точки излома являются точками множества[16].
Patrizio Angelini, Giuseppe Di Battista, Michael Kaufmann, Tamara Mchedlidze, Vincenzo Roselli, Claudio Squarcella.Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21–23, 2011, Revised Selected Papers / Marc van Kreveld, Bettina Speckmann. — Berlin, Heidelberg: Springer-Verlag, 2012. — Т. 7034. — С. 75–85. — (LNCS). — doi:10.1007/978-3-642-25878-7_8.
Franz J. Brandenburg. The International Conference on Topological and Geometric Graph Theory. — Elsevier, 2008. — Т. 31. — С. 37–40. — (Electronic Notes in Discrete Mathematics). — doi:10.1016/j.endm.2008.06.005.
Franz-Josef Brandenburg, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Giuseppe Liotta, Petra Mutzel.Graph Drawing: 11th International Symposium, GD 2003, Perugia, Italy, September 21–24, 2003 Revised Papers / Giuseppe Liotta. — Springer-Verlag, 2003. — Т. 2912. — С. 515–539. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-24595-7_55.. См., в частности задачу 11 на стр. 520.
M. Chrobak, H. Karloff. A lower bound on the size of universal sets for planar graphs // SIGACT News. — 1989. — Т. 20. — С. 83–86. — doi:10.1145/74074.74088.
E. Demaine, J. O'Rourke. The Open Problems Project. — 2002–2012.
Danny Dolev, Tom Leighton, Howard Trickey. Planar embedding of planar graphs // Advances in Computing Research. — 1984. — Т. 2. — С. 147–161.
V. Dujmović, W. S. Evans, S. Lazard, W. Lenhart, G. Liotta, D. Rappaport, S. K. Wismath. On point-sets that support planar graphs // Comput. Geom. Theory Appl.. — 2013. — Т. 46, вып. 1. — С. 29–50.
Hazel Everett, Sylvain Lazard, Giuseppe Liotta, Stephen Wismath. Universal Sets of n Points for One-Bend Drawings of Planar Graphs with n Vertices // Discrete and Computational Geometry. — 2010. — Т. 43, вып. 2. — С. 272–288. — doi:10.1007/s00454-009-9149-3.
Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings. — Springer, 2007. — Т. 4835. — С. 172–183. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-77120-3_17.
Debajyoti Mondal. Embedding a Planar Graph on a Given Point Set. — Department of Computer Science, University of Manitoba, 2012. — (Masters thesis).
Walter Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
L. G. Valiant. Universality considerations in VLSI circuits // IEEE Transactions on Computers. — 1981. — Т. C-30, вып. 2. — С. 135–140. — doi:10.1109/TC.1981.6312176.
