Úhlové rozlišení (teorie grafů)

Úhlové rozlišení výkresu grafu se vztahuje k nejostřejšímu úhlu, který tvoří jakékoli dvě hrany, které se setkávají ve stejném vrcholu výkresu.

Vlastnosti

Vztah se stupněm vrcholu

Foreman et al [1] si všimli, že jakýkoli výkres grafu s hranami segmentů s maximálním stupněm d má úhlové rozlišení nepřesahující — pokud v je vrchol se stupněm d , pak hrany spadající do v rozdělují prostor kolem vrcholu v do d klínů s celkovým úhlem a nejmenší z těchto klínů musí mít úhel nepřesahující . Přesněji řečeno, pokud je graf d - regulární , musí mít úhlové rozlišení menší než , protože to je nejlepší rozlišení, které lze získat pro vrchol na konvexním obalu obrázku.

Vztah s vybarvováním grafu

Jak ukázali Foreman et al [1] , největší možné úhlové rozlišení grafu G úzce souvisí s chromatickým číslem druhé mocniny grafu G 2 , tedy grafu se stejnou množinou vrcholů, ve kterých každý dvojice vrcholů je spojena hranou, pokud vzdálenost mezi nimi v grafu G není větší než dva. Pokud lze graf G 2 obarvit barvami, pak G lze nakreslit s úhlovým rozlišením pro libovolné , a to přiřazením různých barev k vrcholům pravidelného -gonu a umístěním každého vrcholu G vedle 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á vzor s úhlovým rozlišením úměrným 1/ d 2 . Tato hranice je blízká přesné - použili pravděpodobnostní metodu k prokázání existence grafů s maximálním stupněm d , jejichž všechny kresby mají úhlové rozlišení .

Existence optimálních vzorů

Forman et al [1] uvedl příklad ukazující, že existují grafy, které nemají vzory s maximálním možným úhlovým rozlišením. Naopak, tyto grafy mají rodinu kreseb, jejichž úhlová rozlišení mají tendenci k nějaké omezené hodnotě, ale nedosahují jí. Konkrétně představili 11-vertexový graf, který má vzor s úhlovým rozlišením libovolného , ale nemá vzor s úhlovým rozlišením přesně .

Speciální třídy grafů

Stromy

Jakýkoli strom lze nakreslit takovým způsobem, že okraje jsou rovnoměrně rozmístěny kolem každého vrcholu, což je vlastnost známá jako dokonalé úhlové rozlišení . Navíc, pokud mohou být hrany volně permutovány kolem každého vrcholu, pak je takový vzor možný bez průsečíků s hranami délky jedné nebo více a celý vzor je umístěn do polynomického obdélníku oblasti . Pokud je však kruhové uspořádání hran kolem každého vrcholu již specifikováno jako součást zadání problému, pak získání úhlového rozlišení bez křížení může někdy vyžadovat exponenciální oblast [2] [3] .

Nadrovinné grafy

Dokonalé úhlové rozlišení není vždy možné pro vnější rovinné grafy , protože vrcholy na konvexním obalu vzoru se stupněm větším než jedna nemohou mít okraje, které k němu přiléhají, rovnoměrně rozložené kolem vrcholu. Avšak jakýkoli vnější rovinný graf s maximálním stupněm d má vnější rovinnou kresbu s úhlovým rozlišením úměrným 1/ d [4] [5] .

Rovinné grafy

Pro rovinné grafy s maximálním stupněm d Foremanova (et al.) technika vybarvování čtverců grafu [1] vytváří kresbu 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 . Wegner v roce 1977 předpokládal, že chromatické číslo druhé mocniny rovinného grafu nepřesahuje a je známo, že chromatické číslo nepřesahuje [6] [7] . Vzor získaný touto technikou však obecně není rovinný.

Pro některé rovinné grafy je optimální úhlové rozlišení rovinného výkresu s úsečkami O(1/ d 3 ) , kde d je stupeň grafu [5] . Navíc mohou být takové vzory nuceny mít velmi dlouhé okraje, delší než je exponenciální faktor od nejkratšího okraje vzoru. Malitz a Papakostas [4] použili teorém o balení kruhu , aby ukázali, že každý rovinný graf s maximálním stupněm d má rovinný obrazec, jehož úhlové rozlišení v nejhorším případě je exponenciální funkcí d a je nezávislé na počtu vrcholů grafu.

Výpočetní složitost

Problém určení, zda daný graf s maximálním stupněm d má vzor s úhlovým rozlišením , je NP-těžký i ve speciálním případě d =4 [1] [8] . U některých omezených tříd kreseb, včetně kreseb stromů, ve kterých prodloužení listů do nekonečna poskytuje konvexní rozdělení roviny, stejně jako u kreseb rovinných grafů, ve kterých je každá ohraničená plocha středově symetrický mnohoúhelník, kresbu s optimálním úhlovým rozlišením lze nalézt v polynomiálním čase [ 9] [10] .

Historie

Úhlové rozlišení bylo stanoveno Formanem a kol ., [1] .

Přestože byl původně definován pro kreslení grafů s rovnými hranami, později autoři zkoumali úhlové rozlišení výkresů, ve kterých jsou hrany polygonální [11] [12] , kruhové oblouky [13] [2] nebo spline [14] [15]. .

Úhlové rozlišení grafu úzce souvisí s jeho průsečíkovým rozlišením, úhly, které tvoří průsečíky v kresbě grafu. Zejména kreslení grafů v pravých úhlech hledá zobrazení, které zajišťuje, že všechny tyto úhly jsou pravé úhly , což je největší možný úhel průsečíku [16]

Poznámky

  1. ↑ 1 2 3 4 5 6 Formann, Hagerup, Haralambides a kol., 1993 .
  2. ↑ 1 2 Duncan, Eppstein, Goodrich et al., 2011 .
  3. ↑ Halupczok, Schulz, 2011 .
  4. ↑ 1 2 Malitz, Papakostas, 1994 .
  5. ↑ 1 2 Garg, Tamassia, 1994 .
  6. ↑ Kramer, Kramer, 2008 .
  7. ↑ Molloy, Salavatipour, 2005 .
  8. ↑ Garg, Tamassia, 1995 .
  9. ↑ Carlson, Eppstein, 2007 .
  10. ↑ Eppstein, Wortman, 2011 .
  11. ↑ Kant, 1996 .
  12. ↑ Gutwenger, Mutzel, 1998 .
  13. ↑ Cheng, Duncan, Goodrich, Kobourov, 1999 .
  14. ↑ Brandes, Shubina, Tamassia, 2000 .
  15. ↑ Finkel, Tamassia, 2005 .
  16. ↑ Didimo, Eades, Liotta, 2009 .

Literatura