Univerzální sada bodů - Universal point set
![]() | Nevyřešený problém v matematice: Mají rovinné grafy univerzální množiny bodů subkvadratické velikosti? (více nevyřešených úloh z matematiky) |
v kreslení grafu, a univerzální bodová sada řádu n je sada S bodů v Euklidovské letadlo s majetkem, který každý n-vrchol rovinný graf má přímkový výkres ve kterém jsou všechny vrcholy umístěny v bodech S.
Meze velikosti univerzálních množin bodů

Když n je deset nebo méně, existují univerzální množiny bodů s přesně n body, ale pro všechny n ≥ Je zapotřebí dalších 15 bodů.[1]
Několik autorů ukázalo, že podmnožiny souboru celočíselná mřížka velikosti Ó(n) × Ó(n) jsou univerzální. Zejména, de Fraysseix, Pach & Pollack (1988) ukázal, že mřížka (2n − 3) × (n - 1) body jsou univerzální a Schnyder (1990) snížil to na trojúhelníkovou podmnožinu (n − 1) × (n - 1) mřížka, s n2/2 − Ó(n) body. Úpravou metody podle De Fraysseix et al., Brandenburg (2008) našel vložení jakéhokoli rovinného grafu do trojúhelníkové podmnožiny mřížky skládající se ze 4n2/ 9 bodů. Univerzální bod nastavený ve formě obdélníkové mřížky musí mít alespoň velikost n/3 × n/3[2] ale to nevylučuje možnost menších univerzálních bodových sad jiných typů. Nejmenší známé univerzální sady bodů nejsou založeny na mřížkách, ale jsou z nich konstruovány supervzorky (obměny které obsahují všechny permutační vzory dané velikosti); takto konstruované univerzální bodové sady mají velikost n2/4 − Ó(n).[3]
de Fraysseix, Pach & Pollack (1988) prokázal první netriviální dolní mez na velikosti univerzální množiny bodů s vázáním formy n + Ω (√n), a Chrobak & Karloff (1989) ukázal, že univerzální bodové sady musí obsahovat alespoň 1,098n − Ó(n) body. Kurowski (2004) uvedl ještě silnější hranici 1,235n − Ó(n),[4] který byl dále vylepšen o Scheucher, Schrezenmaier & Steiner (2018) až 1,293n − Ó(n).
Otevřeným problémem zůstává překlenutí mezery mezi známými lineárními dolními mezemi a kvadratickými horními mezemi.[5]
Speciální třídy grafů
Podtřídy rovinných grafů mohou obecně mít menší univerzální množiny (množiny bodů, které umožňují přímé kreslení všech n-vertexové grafy v podtřídě) než celá třída rovinných grafů a v mnoha případech univerzální bodové sady přesně n body jsou možné. Například není těžké vidět, že každá sada n body v konvexní pozice (formování vrcholů konvexního mnohoúhelníku) je pro n-vrchol vnější rovinné grafy, a zejména pro stromy. Méně zjevně každá sada n body v obecná pozice (žádné tři kolineární) zůstává univerzální pro vnější rovinné grafy.[6]
Rovinné grafy, které lze rozdělit na vnořené cykly, 2-vnější rovinné grafy a rovinné grafy ohraničených šířka cesty, mají univerzální bodové sady téměř lineární velikosti.[7] Rovinné 3-stromy mít univerzální bodové sady velikosti Ó(n5/3); stejná vazba platí i pro sériově paralelní grafy.[8]
Další styly kreslení

Stejně jako u přímého kreslení grafu byly studovány univerzální sady bodů pro jiné styly kreslení; v mnoha z těchto případů univerzální bodové sady s přesně n body existují na základě topologie vkládání knih ve kterém jsou vrcholy umístěny podél čáry v rovině a hrany jsou nakresleny jako křivky, které tuto čáru protínají maximálně jednou. Například každá sada n kolineární body jsou univerzální pro obloukový diagram ve kterém je každá hrana reprezentována buď jako jedna půlkruh nebo hladká křivka vytvořená ze dvou půlkruhů.[9]
Použitím podobného rozložení lze ukázat, že každá konvexní křivka v rovině obsahuje znak npodmnožina bodů, která je univerzální pro křivka kreslení maximálně jeden ohyb na hranu.[10] Tato sada obsahuje pouze vrcholy výkresu, nikoli ohyby; jsou známy větší sady, které lze použít pro kreslení křivky se všemi vrcholy a všemi ohyby umístěnými v sadě.[11]
Poznámky
- ^ Cardinal, Hoffmann & Kusters (2015).
- ^ Dolev, Leighton & Trickey (1984); Chrobak & Karloff (1989); Demaine & O'Rourke (2002–2012). Slabší kvadratická spodní hranice velikosti mřížky potřebná pro kreslení rovinného grafu byla dána dříve Valiant (1981).
- ^ Bannister a kol. (2013).
- ^ Mondal (2012) tvrdil, že Kurowského důkaz byl chybný, ale později (po diskusi s Jean Cardinal) toto tvrzení odvolal; vidět Vysvětlení Podpora Kurowského důkazu, D. Mondal, aktualizováno 9. srpna 2013.
- ^ Demaine & O'Rourke (2002–2012); Brandenburg a kol. (2003); Mohar (2007).
- ^ Gritzmann a kol. (1991).
- ^ Angelini a kol. (2018); Bannister a kol. (2013).
- ^ Fulek & Tóth (2015)
- ^ Giordano a kol. (2007).
- ^ Everett a kol. (2010).
- ^ Dujmović a kol. (2013).
Reference
- Angelini, Patrizio; Bruckdorfer, Till; Di Battista, Giuseppe; Kaufmann, Michael; Mchedlidze, Tamara; Roselli, Vincenzo; Squarcella, Claudio (2018), „Small Universal Point Sets for k-Outerplanar Graphs“, Diskrétní a výpočetní geometrie, 60 (2): 430–470, doi:10.1007 / s00454-018-0009-x, S2CID 51907835.
- Bannister, Michael J .; Cheng, Zhanpeng; Devanny, William E .; Eppstein, David (2013), „Supervzorky a univerzální sady bodů“, Proc. 21. mezinárodní sympozium o kreslení grafů (GD 2013), arXiv:1308.0403, Bibcode:2013arXiv1308.0403B, doi:10,7155 / jgaa.00318, S2CID 6229641.
- Brandenburg, Franz J. (2008), „Kreslení rovinných grafů na plocha", Mezinárodní konference o topologické a geometrické teorii grafů, Elektronické poznámky v diskrétní matematice, 31, Elsevier, s. 37–40, doi:10.1016 / j.endm.2008.06.005, PAN 2571101.
- Brandenburg, Franz-Josef; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G .; Liotta, Giuseppe; Mutzel, Petra (2003), „Selected open problems in graph drawing“, v Liotta, Giuseppe (ed.), Kresba grafu: 11. mezinárodní sympozium, GD 2003, Perugia, Itálie, 21. – 24. Září, revidované příspěvky 2003, Přednášky v informatice, 2912, Springer-Verlag, str. 515–539, doi:10.1007/978-3-540-24595-7_55. Viz zejména problém 11 na str. 520.
- Cardinal, Jean; Hoffmann, Michael; Kusters, Vincent (2015), „O univerzálních bodových sadách pro rovinné grafy“, Journal of Graph Algorithms and Applications, 19 (1): 529–547, arXiv:1209.3594, doi:10,7155 / jgaa.00374, PAN 3420760, S2CID 39043733
- Chrobak, M .; Karloff, H. (1989), „Dolní mez velikosti univerzálních sad pro rovinné grafy“, Novinky SIGACT, 20 (4): 83–86, doi:10.1145/74074.74088, S2CID 7188305.
- de Fraysseix, Hubert; Pach, János; Pollack, Richarde (1988), „Malé sady podporující Faryho vkládání rovinných grafů“, Dvacáté výroční sympozium ACM o teorii práce s počítačem, str. 426–433, doi:10.1145/62212.62254, ISBN 0-89791-264-0, S2CID 15230919.
- Demaine, E.; O'Rourke, J. (2002–2012), „Problém 45: Nejmenší univerzální sada bodů pro rovinné grafy“, Projekt Otevřené problémy, vyvoláno 2013-03-19.
- Dolev, Danny; Leighton, Tom; Trickey, Howard (1984), "Rovinné vkládání rovinných grafů" (PDF), Pokroky ve výzkumu výpočetní techniky, 2: 147–161.
- Dujmović, V .; Evans, W. S .; Lazard, S .; Lenhart, W .; Liotta, G .; Rappaport, D .; Wismath, S. K. (2013), „On point-sets that support planar graphs“, Comput. Geom. Teorie Appl., 46 (1): 29–50, doi:10.1016 / j.comgeo.2012.03.003.
- Everett, Hazel; Lazard, Sylvain; Liotta, Giuseppe; Wismath, Stephen (2010), "Univerzální sady n Body za jednorázové výkresy rovinných grafů s n Vrcholy ", Diskrétní a výpočetní geometrie, 43 (2): 272–288, doi:10.1007 / s00454-009-9149-3.
- Fulek, Radoslav; Tóth, Csaba D. (2015), „Univerzální bodové sady pro rovinné tři stromy“, Journal of Discrete Algorithms, 30: 101–112, arXiv:1212.6148, doi:10.1016 / j.jda.2014.12.005, PAN 3305154
- Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), „Výpočet vzestupné topologické knižní vložky vzestupných planárních digrafů“, Algoritmy a výpočet: 18. mezinárodní sympozium, ISAAC 2007, Sendai, Japonsko, 17. – 19. Prosince 2007, sborník, Přednášky v informatice, 4835, Springer, str. 172–183, doi:10.1007/978-3-540-77120-3_17.
- Gritzmann, P .; Mohar, B.; Pach, János; Pollack, Richarde (1991), „Vložení planární triangulace s vrcholy na určených pozicích“, Americký matematický měsíčník, 98 (2): 165–166, doi:10.2307/2323956, JSTOR 2323956.
- Kurowski, Maciej (2004), „Dolní hranice 1,235 počtu bodů potřebných k losování všech n-vertex planární grafy ", Dopisy o zpracování informací, 92 (2): 95–98, doi:10.1016 / j.ipl.2004.06.009, PAN 2085707.
- Mohar, Bojan (2007), „Univerzální množiny bodů pro rovinné grafy“, Otevřete problémovou zahradu, vyvoláno 2013-03-20.
- Mondal, Debajyoti (2012), Vložení rovinného grafu na danou množinu bodů (PDF), Diplomová práce, Katedra výpočetní techniky, University of Manitoba[trvalý mrtvý odkaz ].
- Scheucher, Manfred; Schrezenmaier, Hendrik; Steiner, Raphael (2018), Poznámka k univerzálním bodovým sadám pro rovinné grafy, arXiv:1811.06482, Bibcode:2018arXiv181106482S.
- Schnyder, Walter (1990), „Vkládání rovinných grafů do mřížky“, Proc. 1. ACM / SIAM Symposium on Discrete Algorithms (SODA), str. 138–148.
- Valiant, L. G. (1981), "Úvahy o univerzálnosti v obvodech VLSI", Transakce IEEE na počítačích, C-30 (2): 135–140, doi:10.1109 / TC.1981.6312176, S2CID 1450313