Uniwersalny zestaw punktowy

Nierozwiązany problem z matematyki :

Czy grafy planarne mają uniwersalne zbiory punktów o rozmiarze subkwadratowym?

(więcej nierozwiązanych problemów z matematyki)

W rysowaniu grafów uniwersalny zbiór punktów rzędu n jest zbiorem S punktów na płaszczyźnie euklidesowej z tą właściwością, że każdy płaski wykres n -wierzchołków ma rysunek liniowy , w którym wszystkie wierzchołki są umieszczone w punktach S .

Granice wielkości uniwersalnych zbiorów punktowych

Rysunek siatkowy wykresu zagnieżdżonych trójkątów . Na każdym rysunku tego wykresu co najmniej połowa trójkątów musi tworzyć zagnieżdżony łańcuch, co wymaga ramki ograniczającej o rozmiarze co najmniej n /3 × n /3. Pokazany tutaj układ jest zbliżony do tego, wykorzystując rozmiar w przybliżeniu n /3 × n /2

Gdy n wynosi dziesięć lub mniej, istnieją uniwersalne zbiory punktów zawierające dokładnie n punktów, ale dla wszystkich n ≥ 15 wymaganych jest dodatkowych punktów.

Kilku autorów wykazało, że podzbiory sieci liczb całkowitych o rozmiarze O ( n ) × O ( n ) są uniwersalne. W szczególności de Fraysseix, Pach i Pollack (1988) wykazali, że siatka (2 n - 3) × ( n - 1) punktów jest uniwersalna, a Schnyder (1990) zredukował to do trójkątnego podzbioru an ( n - 1) ) × ( n - 1) siatka, gdzie n ² /2 - O ( n ) punktów. Modyfikując metodę de Fraysseix i in., Brandenburg (2008) odkrył osadzenie dowolnego wykresu planarnego w trójkątnym podzbiorze siatki składającym się z 4 n ² /9 punktów. Uniwersalny zbiór punktów w postaci prostokątnej siatki musi mieć rozmiar co najmniej n /3 × n /3, ale nie wyklucza to możliwości mniejszych uniwersalnych zbiorów punktów innych typów. Najmniejsze znane uniwersalne zestawy punktów nie są oparte na siatkach, ale zamiast tego są zbudowane z superwzorców ( permutacji zawierających wszystkie wzorce permutacji o zadanym rozmiarze); skonstruowane w ten sposób zbiory punktów uniwersalnych mają rozmiar n ² /4 − Θ ( n ).

de Fraysseix, Pach i Pollack (1988) udowodnili pierwszą nietrywialną dolną granicę rozmiaru uniwersalnego zbioru punktów, z granicą postaci n + Ω(√ n ), a Chrobak i Karloff (1989) wykazali, że uniwersalne zbiory punktów musi zawierać co najmniej 1,098 n − o ( n ) punktów. Kurowski (2004) stwierdził jeszcze silniejszą granicę 1,235 n - o ( n ), która została dodatkowo poprawiona przez Scheuchera, Schrezenmaiera i Steinera (2018) do 1,293 n - o ( n ).

Zamknięcie luki między znanymi liniowymi dolnymi granicami a kwadratowymi górnymi granicami pozostaje otwartym problemem.

Specjalne klasy grafów

Podklasy grafów planarnych mogą na ogół mieć mniejsze zbiory uniwersalne (zbiory punktów umożliwiające rysowanie w linii prostej wszystkich n -wierzchołków w podklasie) niż pełna klasa grafów planarnych, a w wielu przypadkach uniwersalne zbiory punktowe dokładnie n punktów jest możliwych. Na przykład nietrudno zauważyć, że każdy zbiór n punktów w położeniu wypukłym (tworzących wierzchołki wielokąta wypukłego) jest uniwersalny dla n- wierzchołków grafów płaszczyzny zewnętrznej , aw szczególności dla drzew . Mniej oczywiście, każdy zestaw n punktów w ogólnej pozycji (bez trzech współliniowych) pozostaje uniwersalnych dla grafów na płaszczyźnie zewnętrznej.

Grafy planarne, które można podzielić na zagnieżdżone cykle, grafy 2-płaszczyznowe i grafy planarne o ograniczonej szerokości ścieżki , mają uniwersalne zbiory punktów o prawie liniowym rozmiarze. Planarne 3-drzewa mają uniwersalne zestawy punktów o rozmiarze O ( n ^3/2 log n ); ta sama granica dotyczy również wykresów szeregowo-równoległych .

Inne style rysowania

Diagram łuku

Oprócz rysowania wykresów w linii prostej, zbadano uniwersalne zestawy punktów dla innych stylów rysowania; w wielu z tych przypadków istnieją uniwersalne zbiory punktów z dokładnie n punktami, oparte na osadzeniu księgi topologicznej , w której wierzchołki są umieszczane wzdłuż linii na płaszczyźnie, a krawędzie są rysowane jako krzywe przecinające tę linię co najwyżej raz. Na przykład każdy zestaw n współliniowych punktów jest uniwersalny dla diagramu łukowego , w którym każda krawędź jest reprezentowana jako pojedynczy półokrąg lub gładka krzywa utworzona z dwóch półokręgów.

Używając podobnego układu, można pokazać, że każda ściśle wypukła krzywa na płaszczyźnie zawiera podzbiór n -punktowy, który jest uniwersalny dla rysowania polilinii z co najwyżej jednym zagięciem na krawędź . Ten zestaw zawiera tylko wierzchołki rysunku, bez zagięć; znane są większe zestawy, których można użyć do rysowania polilinii ze wszystkimi wierzchołkami i wszystkimi zagięciami umieszczonymi w zestawie.

Notatki

•   Angelini Patrizio; Bruckdorfer, Till; Di Battista, Giuseppe; Kaufmann, Michael; Miedzidze, Tamara; Roselli, Vincenzo; Squarcella, Claudio (2018), „Małe uniwersalne zestawy punktów dla k-Outerplanar Graphs”, Discrete & Computational Geometry , 60 (2): 430–470, doi : 10.1007 / s00454-018-0009-x , S2CID 51907835 .
•   Bannister, Michael J.; Cheng, Zhanpeng; Devanny, William E.; Eppstein, David (2013), „Superpatterns i uniwersalne zestawy punktów”, Proc. 21. Międzynarodowe Sympozjum Rysowania Grafów ( GD 2013 ) _ _ _ _ _ _ _ _
•   Brandenburg, Franz J. (2008), „Rysowanie grafów planarnych na $grafów$ Międzynarodowa konferencja na temat topologicznej i geometrycznej , Notatki elektroniczne w matematyce dyskretnej, tom. 31, Elsevier, s. 37–40, doi : 10.1016/j.endm.2008.06.005 , MR 2571101 .
• Brandenburg, Franz-Josef; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Liotta, Giuseppe; Mutzel, Petra (2003), „Wybrane otwarte problemy w rysowaniu wykresów”, w: Liotta, Giuseppe (red.), Graph Drawing: 11th International Symposium, GD 2003, Perugia, Włochy, 21–24 września 2003 Revised Papers , Lecture Notes w informatyce, tom. 2912, Springer-Verlag, s. 515–539, doi : 10.1007/978-3-540-24595-7_55 . Patrz w szczególności problem 11 na str. 520.
•    kardynał Jean; Hoffmann, Michael; Kusters, Vincent (2015), „O uniwersalnych zestawach punktów dla grafów planarnych”, Journal of Graph Algorithms and Applications , 19 (1): 529–547, arXiv : 1209,3594 , doi : 10,7155/jgaa.00374 , MR 3420760 , S2CID 39043733
•   Chrobak, M.; Karloff, H. (1989), „Dolna granica rozmiaru uniwersalnych zestawów dla grafów planarnych” , SIGACT News , 20 (4): 83–86, doi : 10.1145/74074.74088 , S2CID 7188305 .
•    de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1988), „Małe zestawy wspierające osadzanie grafów planarnych przez Fary'ego”, Twentieth Annual ACM Symposium on Theory of Computing , s. 426–433, doi : 10.1145 / 62212.62254 , ISBN 0-89791-264-0 , S2CID 15230919 .
• Demaine, E .; O'Rourke, J. (2002–2012), „Problem 45: najmniejszy uniwersalny zestaw punktów dla grafów planarnych” , The Open Problems Project , dostęp 2013-03-19 .
• Dolew, Danny ; Leighton, Tom ; Trickey, Howard (1984), „Planarne osadzanie grafów planarnych” (PDF) , Advances in Computing Research , 2 : 147–161 .
• Dujmović, W. ; Evans, WS; Lazard S.; Lenhart, W.; Liotta, G.; Rappaport, D.; Wismath, SK (2013), „O zestawach punktów obsługujących wykresy planarne”, Comput. Geom. aplikacja teoretyczna , 46 (1): 29–50, doi : 10.1016/j.comgeo.2012.03.003 .
• Everett, Hazel; Lazard, Sylvain; Liotta, Giuseppe; Wismath, Stephen (2010), „Universal Sets of n Points for One-Bend Drawings of Planar Graphs with n Vertices” , Discrete and Computational Geometry , 43 (2): 272–288, doi : 10.1007 / s00454-009-9149- 3 .
•   Fulek, Radosław; Tóth, Csaba D. (2015), „Universal point set for planar three-trees”, Journal of Discrete Algorithms , 30 : 101–112, arXiv : 1212,6148 , doi : 10,1016/j.jda.2014.12.005 , MR 3305154
• Giordano, Francesco; Liotta, Giuseppe; Miedzidze, Tamara; Symvonis, Antonios (2007), „Computing up topological book embeddings of up planar digraphs”, Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japonia, 17-19 grudnia 2007, Proceedings , Lecture Notes in Computer Science, tom . 4835, Springer, s. 172–183, doi : 10.1007/978-3-540-77120-3_17 .
•   Gritzmann, P.; Mohar, B .; Pach, János ; Pollack, Richard (1991), „Osadzanie płaskiej triangulacji z wierzchołkami w określonych pozycjach”, American Mathematical Monthly , 98 (2): 165–166, doi : 10,2307/2323956 , JSTOR 2323956 .
•   Kurowski, Maciej (2004), „Dolna granica 1,235 liczby punktów potrzebnych do narysowania wszystkich płaskich wykresów n -wierzchołków”, Information Processing Letters , 92 (2): 95–98, doi : 10.1016 / j.ipl.2004.06 .009 , MR 2085707 .
• Mohar, Bojan (2007), „Uniwersalne zestawy punktów dla grafów planarnych” , Open Problem Garden , dostęp 2013-03-20 .
• Mondal, Debajyoti (2012), Osadzanie planarnego wykresu na zadanym zbiorze punktów (PDF) , praca magisterska, Wydział Informatyki, University of Manitoba .
• Scheucher, Manfred; Schrezenmaier, Hendrik; Steiner, Raphael (2018), Uwaga na temat uniwersalnych zestawów punktów dla wykresów planarnych , arXiv : 1811,06482 , Bibcode : 2018arXiv181106482S .
• Schnyder, Walter (1990), „Osadzanie grafów planarnych na siatce”, Proc. 1. Sympozjum ACM / SIAM na temat algorytmów dyskretnych (SODA) , s. 138–148 .
•   Valiant, LG (1981), „Uwagi uniwersalne w obwodach VLSI”, IEEE Transactions on Computers , C-30 (2): 135–140, doi : 10.1109 / TC.1981.6312176 , S2CID 1450313