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

Нерозв'язана проблема математики

Розмір універсальних множин точок планарних графів підквадратичний?

Універсальна множина точок порядку n — це множина S точок евклідової площини з властивістю, що будь-який планарний граф з n вершинами має малюнок із прямими ребрами, в якому всі вершини розташовуються в точках множини S.

Межі розмірів універсальної множини точок

Малюнок графа вкладених трикутників на ґратці. У будь-якому малюнку цього графа принаймні половина трикутників повинна утворювати вкладений ланцюжок, так що знадобиться обмежувальний прямокутник розміром щонайменше n/3 × n/3. Наведене на малюнку подання графа має близьке до цього значення n/3 × n/2

Якщо n не перевищує 10, існує універсальна множина точок, що має рівно 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 точок, що є універсальною для малюнків у вигляді ламаних із максимум одним зламом на ребро. Ця множина містить тільки вершини малюнка, але не точки зламу. Відомі великі множини, які можна використовувати для малюнків за допомогою ламаних, у яких вершини і всі точки зламу є точками множини.

Література

• 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.