Úhlové rozlišení (kresba grafu) - Angular resolution (graph drawing)
v kreslení grafu, úhlové rozlišení kresby grafu je nejostřejší úhel tvořený dvěma hranami, které se setkávají ve společném vrcholu kresby.
Vlastnosti
Vztah k vrcholu
Formann a kol. (1993) si všiml, že každý přímý výkres grafu s maximálním stupněm d má maximální úhlové rozlišení 2π /d: pokud proti je vrchol stupně d, pak hrany dopadají na proti rozdělit prostor kolem proti do d klíny s celkovým úhlem 2πa nejmenší z těchto klínů musí mít úhel maximálně 2π /d. Silněji, pokud je graf d-pravidelný, musí mít úhlové rozlišení menší než , protože toto je nejlepší rozlišení, jaké lze dosáhnout pro vrchol na konvexní obal výkresu.
Vztah ke zbarvení grafu
Tak jako Formann a kol. (1993) ukázal, největší možné úhlové rozlišení grafu G úzce souvisí s chromatické číslo z náměstí G2, graf na stejném vrcholu, ve kterém jsou páry vrcholů spojeny hranou, kdykoli je jejich vzdálenost dovnitř G je maximálně dva. Li G2 lze obarvit pomocí χ tedy barvy G lze kreslit s úhlovým rozlišením π /χ - ε, pro všechny ε> 0, přiřazením odlišných barev k vrcholům a pravidelný χ-gon a umístění každého vrcholu G blízko vrcholu mnohoúhelníku se stejnou barvou. Pomocí této konstrukce ukázali, že každý graf s maximálním stupněm d má výkres s úhlovým rozlišením úměrným 1/d2. Tato vazba je téměř těsná: použili pravděpodobnostní metoda dokázat existenci grafů s maximálním stupněm d jejichž výkresy mají všechny úhlové rozlišení .
Existence optimálních výkresů
Formann a kol. (1993) poskytl příklad ukazující, že existují grafy, které nemají výkres dosahující maximálního možného úhlového rozlišení; místo toho mají tyto grafy rodinu výkresů, jejichž úhlová rozlišení mají sklon k určité mezní hodnotě, aniž by ji dosáhly. Konkrétně vystavovali 11-vertexový graf, který má výkresy úhlového rozlišení π / 3 - ε pro všechny ε> 0, ale to nemá přesně výkres úhlového rozlišení π / 3.
Speciální třídy grafů
Stromy
Každý strom může být nakreslen takovým způsobem, že okraje jsou rovnoměrně rozmístěny kolem každého vrcholu, což je vlastnost známá jako perfektní úhlové rozlišení. Kromě toho, pokud mohou být okraje volně permutovány kolem každého vrcholu, je takový výkres možný bez křížení, se všemi jednotkami délky hran nebo vyššími a s celým výkresem zapadajícím do ohraničující rámeček polynomu plocha. Pokud je však již cyklické uspořádání hran kolem každého vrcholu určeno jako součást vstupu do problému, pak dosažení dokonalého úhlového rozlišení bez křížení může někdy vyžadovat exponenciální oblast.[1]
Vnější rovinné grafy
Dokonalé úhlové rozlišení není vždy možné vnější rovinné grafy, protože vrcholy na konvexním trupu výkresu se stupněm větším než jeden nemohou mít své dopadající hrany rovnoměrně rozmístěné kolem sebe. Každý vnější rovinný graf maximálního stupně d má vnější rovinnou kresbu s úhlovým rozlišením úměrným 1/d.[2]
Rovinné grafy
Pro rovinné grafy s maximálním stupněm d, technika čtvercového barvení Formann a kol. (1993) poskytuje výkres s úhlovým rozlišením úměrným 1/d, protože čtverec rovinného grafu musí mít chromatické číslo úměrné d. Přesněji, Wegner se domníval v roce 1977, že chromatické číslo čtverce rovinného grafu je nanejvýš a je známo, že chromatické číslo je nanejvýš .[3] Výkresy vyplývající z této techniky však obecně nejsou rovinné.
U některých rovinných grafů je optimální úhlové rozlišení rovinného přímého výkresu O (1 /d3), kde d je stupeň grafu.[4] Navíc může být takový výkres nucen používat velmi dlouhé hrany, delší exponenciálním faktorem než nejkratší hrany ve výkresu.Malitz & Papakostas (1994) použil věta o kruhu a prstencové lemma ukázat, že každý rovinný graf s maximálním stupněm d má rovinný výkres, jehož úhlové rozlišení je přinejhorším exponenciální funkcí d, nezávisle na počtu vrcholů v grafu.
Výpočetní složitost
Je NP-těžké určit, zda daný graf maximálního stupně d má výkres s úhlovým rozlišením 2π /d, dokonce i ve zvláštním případě d = 4.[5] Avšak pro určité omezené třídy kreseb, včetně kreseb stromů, u nichž prodloužení listí do nekonečna vytváří konvexní dělení roviny, stejně jako kresby rovinných grafů, ve kterých je každá ohraničená plocha centrálně symetrický polygon, je kresba optimální úhlové rozlišení najdete v polynomiální čas.[6]
Dějiny
Úhlové rozlišení bylo poprvé definováno pomocí Formann a kol. (1993).
Ačkoli byly původně definovány pouze pro přímkové kresby grafů, pozdější autoři také zkoumali úhlové rozlišení výkresů, ve kterých jsou hrany polygonální řetězce,[7] kruhové oblouky,[8] nebo křivky spline.[9]
Úhlové rozlišení grafu úzce souvisí s jeho křížením, úhlem tvořeným přechody ve výkresu grafu. Zejména, RAC výkres snaží se zajistit, aby tyto úhly byly všechny správné úhly, největší možný úhel křížení.[10]
Poznámky
- ^ Duncan a kol. (2011); Halupczok & Schulz (2011).
- ^ Malitz & Papakostas (1994); Garg & Tamassia (1994).
- ^ Kramer & Kramer (2008); Molloy & Salavatipour (2005).
- ^ Garg & Tamassia (1994).
- ^ Formann a kol. (1993); Garg & Tamassia (1995).
- ^ Carlson & Eppstein (2007); Eppstein & Wortman (2011).
- ^ Kant (1996); Gutwenger & Mutzel (1998).
- ^ Cheng a kol. (1999); Duncan a kol. (2011).
- ^ Brandes, Shubina & Tamassia (2000); Finkel & Tamassia (2005).
- ^ Didimo, Eades a Liotta (2009).
Reference
- Brandes, Ulrik; Shubina, Galina; Tamassia, Roberto (2000), „Zlepšení úhlového rozlišení ve vizualizacích geografických sítí“, Data Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization in Amsterdam, The Netherlands, 29. - 31. května 2000.
- Carlson, Josiah; Eppstein, David (2007), „Stromy s konvexními plochami a optimálními úhly“, in Kaufmann, Michael; Wagner, Dorothea (eds.), Proc. 14. Int. Symp. Kreslení grafu (GD'06), LNCS, 4372, Springer-Verlag, str. 77–88, arXiv:cs.CG/0607113, doi:10.1007/978-3-540-70904-6_9, S2CID 12598338.
- Cheng, C. C .; Duncan, C. A .; Goodrich, M. T.; Kobourov, S. G. (1999), „Kreslení rovinných grafů s kruhovými oblouky“, Grafická kresba, 7. mezinárodní sympozium, GD'99, hrad Štirín, Česká republika 15. – 19. Září 1999, sborník, Přednášky z informatiky, 1731, Springer-Verlag, str. 117–126, doi:10.1007/3-540-46648-7_12.
- Didimo, Walter; Eades, Peter; Liotta, Giuseppe (2009), „Kreslení grafů s pravoúhlými přechody“, Algoritmy a datové struktury: 11. mezinárodní sympozium, WADS 2009, Banff, Kanada, 21. – 23. Srpna 2009. Sborník, Přednášky v informatice, 5664, str. 206–217, doi:10.1007/978-3-642-03367-4_19.
- Duncan, Christian A .; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G .; Nöllenburg, Martin (2011), „Kreslení stromů s dokonalým úhlovým rozlišením a polynomickou oblastí“, Brandes, Ulrik; Cornelsen, Sabine (eds.), Proc. 18. Int. Symp. Kreslení grafu, Přednášky v informatice, 6502, Springer-Verlag, str. 183–194, arXiv:1009.0581, doi:10.1007/978-3-642-18469-7_17.
- Eppstein, D.; Wortman, K. (2011), „Optimální úhlové rozlišení pro obličejově symetrické kresby“, Journal of Graph Algorithms and Applications, 15 (4): 551–564, arXiv:0907.5474, doi:10,7155 / jgaa.00238, S2CID 10356432.
- Finkel, Benjamin; Tamassia, Roberto (2005), „Křivočiary kresba grafu pomocí metody zaměřené na sílu“, Grafická kresba, 12. mezinárodní sympozium, GD 2004, New York, NY, USA, 29. září - 2. října 2004, revidované vybrané příspěvky, Přednášky v informatice, 3383, Springer-Verlag, str. 448–453, doi:10.1007/978-3-540-31843-9_46.
- Formann, M .; Hagerup, T .; Haralambides, J .; Kaufmann, M .; Leighton, F. T.; Symvonis, A .; Welzl, E.; Woeginger, G. (1993), „Kreslení grafů v rovině s vysokým rozlišením“, SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, PAN 1237161.
- Garg, Ashim; Tamassia, Roberto (1994), "Planární kresby a úhlové rozlišení: Algoritmy a meze", Algorithms, Second Annual European Symposium, Utrecht, The Netherlands, 26. – 28. Září 1994, sborník, Přednášky v informatice, 855, Springer-Verlag, s. 12–23, doi:10.1007 / BFb0049393.
- Garg, Ashim; Tamassia, Roberto (1995), „O výpočetní složitosti vzestupného a přímočarého testování rovinnosti“, Tamassia, Roberto; Tollis, Ioannis (eds.), Kreslení grafu, Přednášky v informatice, 894Springer Berlin / Heidelberg, s. 286–297, doi:10.1007/3-540-58950-3_384.
- Gutwenger, Carsten; Mutzel, Petra (1998), "Rovinné křivky s dobrým úhlovým rozlišením", Kresba grafu (Montréal, QC, 1998), Poznámky k přednášce ve Výpočtu. Sci., 1547, Berlín: Springer, s. 167–182, doi:10.1007/3-540-37623-2_13, PAN 1717450.
- Halupczok, Immanuel; Schulz, André (2011), „Přichytávání balónků s dokonalými úhly a optimální oblastí“, Sborník 19. mezinárodního sympozia o kreslení grafů.
- Kant, G. (1996), „Kreslení rovinných grafů pomocí kanonického uspořádání“, Algorithmica, 16 (1): 4–32, doi:10,1007 / s004539900035, hdl:1874/16676, PAN 1394492.
- Kramer, Florica; Kramer, Horst (2008), „An survey on the distance-colored of graphs“, Diskrétní matematika, 308 (2–3): 422–426, doi:10.1016 / j.disc.2006.11.059, PAN 2378044.
- Malitz, Seth; Papakostas, Achilleas (1994), „O úhlovém rozlišení rovinných grafů“, SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137 / S0895480193242931, PAN 1271989.
- Molloy, Michael; Salavatipour, Mohammad R. (2005), „Vazba na chromatické číslo čtverce rovinného grafu“, Journal of Combinatorial Theory, Řada B, 94 (2): 189–213, doi:10.1016 / j.jctb.2004.12.005, hdl:1807/9473, PAN 2145512.