RAC výkres - RAC drawing - Wikipedia

RAC výkresy kompletní graf K.5 a kompletní bipartitní graf K.3,4

v kreslení grafu, a RAC výkres a graf je kresba, ve které jsou vrcholy reprezentovány jako body, hrany jako přímé úsečky nebo křivky, nanejvýš dvě hrany se protínají v kterémkoli bodě, a když se dvě hrany protínají, dělají to v správné úhly navzájem. Název tohoto stylu kreslení znamená „RAC“ zkratku „pravý úhel křížení“.

Styl křížení v pravém úhlu a název „RAC drawing“ pro tento styl byly formulovány uživatelem Didimo, Eades a Liotta (2009),[1] motivováno předchozími uživatelskými studiemi, které ukazují, že přechody s velkými úhly jsou mnohem méně škodlivé pro čitelnost výkresů než mělké přechody.[2] Dokonce pro rovinné grafy, umožnění některých pravoúhlých křížení ve výkresu grafu může výrazně zlepšit měřítka kvality výkresu, jako je jeho plocha nebo úhlové rozlišení.[3]

Příklady

The kompletní graf K.5 má RAC výkres s rovnými hranami, ale K.6 ne. Každý výkres RAC se šesti vrcholy má maximálně 14 hran, ale K.6 má 15 hran, příliš mnoho na to, aby mohly mít výkres RAC.[1]

A kompletní bipartitní graf K.A,b má RAC výkres s rovnými hranami právě tehdy, když buď min (A,b) ≤ 2 nebo A + b ≤ 7. Pokud min (A,b) ≤ 2, pak je graf a rovinný graf, a (podle Fáryho věta ) každý rovinný graf má přímkový výkres bez křížení. Takový výkres je automaticky výkresem RAC. Zbývají pouze dva případy - grafy K.3,3 a K.3,4. Kresba K.3,4 je ukázáno; K.3,3 lze z něj vytvořit odstraněním jednoho vrcholu. Ani jeden z následujících dvou větších grafů, K.4,4 a K.3,5, má výkres RAC.[4]

Hrany a ohyby

Pokud n-vertexový graf má RAC výkres s rovnými hranami, může mít maximálně 4n - 10 hran. To je těsné: existují grafy, které lze nakreslit RAC s přesně 4n - 10 hran.[1] U výkresů s hranami křivky závisí vazba počtu hran v grafu na počet zatáček které jsou povoleny na hranu. Grafy, které mají výkresy RAC s jedním nebo dvěma ohyby na hranu, mají O (n) hrany; konkrétněji s jedním ohybem je maximálně 5,5n hrany[5] a se dvěma ohyby jsou maximálně 74,2n hrany.[6] Každý graf má RAC výkres se třemi ohyby na hranu.[1]

Vztah k 1-rovinnosti

Graf je 1-rovinný pokud má výkres s maximálně jedním křížením na hranu. Toto omezení intuitivně usnadňuje způsobit, že tento přechod bude v pravém úhlu, a 4n - 10 vázaných na počet okrajů přímých výkresů RAC se blíží hranici 4n - 8 o počtu hran v a 1-rovinný graf a ze 4n - 9 o počtu hran v přímém 1-rovinném grafu. Každý RAC výkres se 4n - 10 hran je 1-rovinná.[7][8] Navíc každý vnější 1-rovinný graf (tj. Graf nakreslený jedním křížením na hranu se všemi vrcholy na vnější straně výkresu) má výkres RAC.[9] Existují však 1-rovinné grafy se 4n - 10 hran, které nemají výkresy RAC.[7]

Výpočetní složitost

to je NP-tvrdé zjistit, zda daný graf má RAC výkres s rovnými hranami,[10] i když je vstupní graf 1-rovinný a výstupní RAC výkres musí být také 1-rovinný.[11] Problém kreslení RAC zůstává NP-těžký pro kreslení nahoru směrované acyklické grafy.[12] Ve zvláštním případě vnějších 1-rovinných grafů však lze RAC výkres sestrojit v lineárním čase.[13]

Reference

  1. ^ A b C d 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říspěvků, Přednášky z informatiky, 5664, str. 206–217, doi:10.1007/978-3-642-03367-4_19.
  2. ^ Huang, Weidong; Hong, Seok-Hee; Eades, Peter (2008), „Účinky křížení úhlů“, IEEE Pacific Visualization Symposium (PacificVIS '08), str. 41–46, doi:10.1109 / PACIFICVIS.2008.4475457.
  3. ^ van Kreveld, Marc (2011), „Poměr kvality výkresů RAC a rovinných výkresů rovinných grafů“, Kreslení grafu: 18. mezinárodní sympozium, GD 2010, Konstanz, Německo, 21. – 24. Září 2010, revidované vybrané příspěvky, Přednášky v informatice, 6502, str. 371–376, doi:10.1007/978-3-642-18469-7_34.
  4. ^ Didimo, Walter; Eades, Peter; Liotta, Giuseppe (2010), „Charakterizace kompletních bipartitních grafů RAC“, Dopisy o zpracování informací, 110 (16): 687–691, doi:10.1016 / j.ipl.2010.05.023, PAN  2676805.
  5. ^ Angelini, Patrizio; Bekos, Michael; Förster, Henry; Kaufmann, Michael (2018), Na výkresech grafů RAC s jedním ohybem na hranu, arXiv:1808.10470
  6. ^ Arikushi, Karin; Fulek, Radoslav; Keszegh, Balázs; Morić, Filip; Tóth, Csaba D. (2012), „Grafy, které připouštějí kresby křížení v pravém úhlu“, Teorie a aplikace výpočetní geometrie, 45 (4): 169–177, arXiv:1001.3117, doi:10.1016 / j.comgeo.2011.11.008, PAN  2876688.
  7. ^ A b Eades, Peter; Liotta, Giuseppe (2013), „Pravoúhlé grafy křížení a 1-rovinnost“, Diskrétní aplikovaná matematika, 161 (7–8): 961–969, doi:10.1016 / j.dam.2012.11.019, PAN  3030582.
  8. ^ Ackerman, Eyal (2014), „Poznámka k 1-rovinným grafům“, Diskrétní aplikovaná matematika, 175: 104–108, doi:10.1016 / j.dam.2014.05.025, PAN  3223912.
  9. ^ Dehkordi, Hooman Reisi; Eades, Peter (2012), „Každý graf vnější roviny má kresbu protínající pravý úhel“, International Journal of Computational Geometry & Applications, 22 (6): 543–557, doi:10.1142 / S021819591250015X, PAN  3042921.
  10. ^ Argyriou, Evmorfia N .; Bekos, Michael A .; Symvonis, Antonios (2011), „Problém přímého kreslení RAC je NP-těžký“, SOFSEM 2011: 37. konference o současných trendech v teorii a praxi informatiky, Nový Smokovec, Slovensko, 22. – 28. Ledna 2011, sborník, Přednášky v informatice, 6543, str. 74–85, arXiv:1009.5227, Bibcode:2011LNCS.6543 ... 74A, doi:10.1007/978-3-642-18381-2_6
  11. ^ Bekos, Michael A .; Didimo, Walter; Liotta, Giuseppe; Mehrabi, Saeed; Montecchiani, Fabrizio (2017), „On RAC drawing of 1-plaar graphs“, Teoretická informatika, 689: 48–57, arXiv:1608.08418, doi:10.1016 / j.tcs.2017.05.039
  12. ^ Angelini, Patrizio; Cittadini, Luca; Di Battista, Giuseppe; Didimo, Walter; Frati, Fabrizio; Kaufmann, Michael; Symvonis, Antonios (2010), „K perspektivám otevřeným kresbami kříženími v pravém úhlu“, Kreslení grafu: 17. mezinárodní sympozium, GD 2009, Chicago, IL, USA, 22. – 25. Září 2009, revidované práce, Přednášky v informatice, 5849, str. 21–32, doi:10.1007/978-3-642-11805-0_5.
  13. ^ Auer, Christopher; Bachmaier, Christian; Brandenburg, Franz J .; Hanauer, Kathrin; Gleißner, Andreas; Neuwirth, Daniel; Reislhuber, Josef (2013). "Rozpoznávání vnějších 1-planárních grafů v lineárním čase". Graf kreslení LNCS. 8284: 107–118. doi:10.1007/978-3-319-03841-4.