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

Универсальное множество точек порядка 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], но это не исключает возможность существования меньшего универсального множества точек других типов. Наименьшие известные универсальные множества точек не основаны на решётках, а строятся из суперсхем (перестановок, содержащих все образы перестановок заданного размера). Универсальные множества точек, построенные таким образом, имеют размер n2/4  O(n)[6].

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

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

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

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

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

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

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

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

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

Примечания

  1. Cardinal, Hoffmann, Kusters, 2015.
  2. de Fraysseix, Pach, Pollack, 1988.
  3. Schnyder, 1990.
  4. Brandenburg, 2008.
  5. Dolev, Leighton, Trickey, 1984; Chrobak, Karloff, 1989; Demaine, O'Rourke, 2002–2012. Более слабую квадратичную границу на размер решётки, требуемой для рисунки планарного графа, дал до этого Валиант Valiant (1981).
  6. Bannister, Cheng, Devanny, Eppstein, 2013.
  7. Chrobak, Karloff, 1989.
  8. Kurowski, 2004.
  9. Мондал (Mondal 2012) утверждал, что доказательство Куровски ошибочно, но позднее (после дискуссии с Джином Кардиналом) отозвал своё утверждение. См. Объяснение доказательства Куровски.
  10. Demaine, O'Rourke, 2002–2012; Brandenburg, Eppstein, Goodrich, Kobourov, 2003; Mohar, 2007.
  11. Gritzmann, Mohar, Pach, Pollack, 1991.
  12. Angelini, Di Battista, Kaufmann, Mchedlidze, 2012.
  13. Fulek, Toth, 2013.
  14. Giordano, Liotta, Mchedlidze, Symvonis, 2007.
  15. Everett, Lazard, Liotta, Wismath, 2010.
  16. Dujmović, Evans, Lazard, Lenhart, 2013.

Литература

  • 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.
  • Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, David Eppstein. Proc. 21st International Symposium on Graph Drawing (GD 2013). — 2013.
  • 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.
  • Jean Cardinal, Michael Hoffmann, Vincent Kusters. On universal point sets for planar graphs // Journal of Graph Algorithms and Applications. — 2015. Т. 19. С. 529–547. doi:10.7155/jgaa.00374.
  • 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.
  • Hubert de Fraysseix, János Pach, Richard Pollack. Twentieth Annual ACM Symposium on Theory of Computing. — 1988. — С. 426–433. — ISBN 0-89791-264-0. doi:10.1145/62212.62254.
  • 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.
  • Radoslav Fulek, Csaba Toth. Algorithms & Data Structures Symposium (WADS). — 2013.
  • 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.
  • P. Gritzmann, B. Mohar, János Pach, Richard Pollack. Embedding a planar triangulation with vertices at specified positions // American Mathematical Monthly. — 1991. Т. 98, вып. 2. С. 165–166.
  • Maciej Kurowski. A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs // Information Processing Letters. — 2004. Т. 92, вып. 2. С. 95–98. doi:10.1016/j.ipl.2004.06.009.
  • Bojan Mohar. Open Problem Garden. — 2007.
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.