Kreslení grafů v pravém úhlu

Kreslení v pravém úhlu (RAC=pravoúhlé křížení, RAC) grafu je kresba, ve které jsou vrcholy reprezentovány body a hrany jsou reprezentovány úsečkami nebo křivkami , v jednom bodě se neprotínají více než dvě hrany, a pokud se dvě hrany protínají, musí se protínat pod pravými úhly .

Styl kresby v pravém úhlu a název „kresba RAC“ pro tento styl navrhli Didimo, Eides a Liotta [1] , přičemž tento styl vznikl po zjištění, že kreslení grafu s velkým průsečíkem ve vysokých úhlech se čte lépe než kresby s malé úhly [2] . I u rovinných grafů může křížení některých hran v pravém úhlu výrazně zlepšit některé charakteristiky kresby, jako je plošné nebo úhlové rozlišení [3] .

Příklady

Kompletní graf K 5 má vzor RPU s rovnými hranami, ale K 6 nikoli. Jakýkoli výkres RPC se 6 vrcholy má maximálně 14 hran a K 6 má 15 hran, což je příliš mnoho na výkres RPU [1] .

Úplný bipartitní graf Ka , b má vzor RPC s úsečkami právě tehdy, když min( a , b ) ≤ 2 nebo a  +  b  ≤ 7. Jestliže min( a , b ) ≤ 2, pak je graf rovinný , a (podle Fariho teorému ) každý rovinný graf má vzor ve formě úseček bez průsečíků. Takové kresby automaticky spadají do třídy RAC. Zbývají pouze dva případy, grafy K 3,3 a K 3,4 . Obrázek K 3.4 je uveden na obrázku. K 3,3 lze získat z K 3,4 odstraněním jednoho vrcholu. Žádný z grafů K 4.4 a K 3.5 nemá vzor RPU [4] .

Žebra a zlomy

Pokud má graf s n vrcholy RPC reprezentaci s hranami segmentů, může mít maximálně 4n  − 10 hran. Omezení je těsné – existují grafy s RPC reprezentací, které mají přesně 4n  − 10 hran [1] . U kreseb s přerušenými hranami závisí počet hran v grafu na počtu povolených přerušení na hranu. Grafy, které mají RPC reprezentace s jedním nebo dvěma zlomy na hraně, mají O( n ) hran. Přesněji řečeno, u jednoho zalomení nemůže počet hran překročit 6,5 n a u dvou zalomení 74,2 n [5] . Každý graf má reprezentaci RPC, pokud jsou povoleny tři zlomy na hraně [1] .

Vztah k 1-rovinnosti

Graf je 1-rovinný , pokud má vzorek s nejvýše jedním průsečíkem na hraně. Je intuitivně jasné, že toto omezení usnadňuje znázornění grafu s hranami křižujícími se v pravém úhlu a omezení 4 n  − 10 počtu hran RPC reprezentace s hranami jako segmenty se blíží hranici 4 n  − 8 počet hran 1-rovinných grafů a blízko k hranici 4 n  − 9 počet hran v reprezentaci 1-rovinných grafů s hranami jako segmenty. Jakákoli RPC reprezentace se 4n  − 10 hranami je 1-rovinná [6] [7] . Navíc každý 1-mimorovinný graf (tj. graf s jedním průsečíkem na hranu, ve kterém všechny vrcholy leží na vnější ploše výkresu) má RPC reprezentaci [8] . Existují však 1-rovinné grafy se 4 n  − 10 hranami, které nemají RPC reprezentaci [6] .

Výpočetní složitost

Problém určení, zda má RPC graf reprezentaci úsečkou, je NP-těžký [9] a konstrukce RPC výkresu je podobná jako u plošného výkresu zdola nahoru [10] . Ve speciálním případě 1-mimorovinných grafů však lze RPC reprezentaci sestavit v lineárním čase [11] .

Poznámky

  1. ↑ 1 2 3 4 Didimo, Eades, Liotta, 2009 , str. 206–217.
  2. ↑ Huang, Hong, Eades, 2008 , str. 41–46.
  3. ↑ van Kreveld, 2011 , str. 371–376.
  4. ↑ Didimo, Eades, Liotta, 2010 , str. 687–691.
  5. ↑ Arikushi, Fulek, Keszegh et al., 2012 , str. 169–177.
  6. ↑ 1 2 Eades, Liotta, 2013 , str. 961–969.
  7. ↑ Ackerman, 2014 , str. 104–108.
  8. ↑ Dehkordi, Eades, 2012 , str. 543–557.
  9. ↑ Argyriou, Bekos, Symvonis, 2011 , str. 74–85.
  10. ↑ Angelini, Cittadini, Di Battista et al., 2010 , s. 21–32.
  11. ↑ Auer, Bachmaier, Brandenburg et al., 2013 , str. 107-118.

Literatura