Počet sklonů grafu

Ve vizualizaci grafů a teorii geometrických grafů je počet sklonů grafu minimálním možným počtem různých sklonových koeficientů hran ve výkresu grafu, ve kterém jsou vrcholy reprezentovány body euklidovské roviny a hrany jsou segmenty . které neprocházejí vrcholy, které nejsou incidentní s těmito hranami.

Kompletní grafy

Přestože související problémy v kombinatorické geometrii byly studovány již dříve (Scott v roce 1970 a Jamison v roce 1984), problém stanovení počtu sklonů grafu nastolili Wade a Chu [1] , kteří ukázali, že počet sklonů grafu s n vrcholy úplného grafu K n je přesně n . Kreslení grafu s takovým počtem sklonů lze získat umístěním vrcholů grafu do rohů pravidelného mnohoúhelníku .

Vztah ke stupni grafu

Je zřejmé, že počet sklonů grafu s maximálním stupněm d je nejméně , protože nejvýše dvě dopadající hrany vrcholu stupně d mohou ležet na stejné přímce (mají jeden sklon). Přesněji řečeno, počet svahů není menší než lineární stromořadí grafu , protože okraje stejného svahu musí tvořit lineární les a lineární stromořadí zase nesmí být menší než .

Existují grafy s maximálním stupněm pět, které mají libovolně velký počet sklonů [2] . Každý graf s maximálním stupněm tři má však nejvýše čtyři sklony [3] . Výsledek Wadea a Chua (1994 ) pro úplný graf K4 ukazuje , že tato hranice je ostrá. Žádná sada čtyř sklonů není vhodná pro kreslení všech grafů stupně 3 - sada sklonů je vhodná pro kreslení pouze tehdy, jsou-li to sklony stran a úhlopříček rovnoběžníku . Zejména lze nakreslit libovolný graf stupně 3 tak, že jeho hrany jsou buď rovnoběžné s osami, nebo rovnoběžné s hlavními úhlopříčkami celočíselné mřížky [4] . Není známo, zda počet sklonů grafů s maximálním stupněm čtyři je nebo není omezený [5] .

Rovinné grafy

Jak ukázali Keszegh, Pach, Pálvölgyi (2011 ), každý rovinný graf má vzor ploché čáry-segmenty, ve kterém je počet různých sklonů funkcí stupně grafu. Jejich důkaz se řídí konstrukcí Maltze a Papakostase ( Malitz, Papakostas (1994 )) pro omezení úhlového rozlišení rovinných grafů jako funkce stupně. Omezení stupně se provádí rozšířením grafu na maximální rovinný graf bez zvýšení jeho stupně o více než konstantní faktor a následnou aplikací teorému o balení kruhu k reprezentaci tohoto rozšířeného grafu jako sady tečných kružnic. Pokud je stupeň počátečního grafu ohraničen, poměr poloměrů sousedních kružnic v obalu bude také omezen [7] , což zase znamená, že aplikace kvadrantového stromu na všechny vrcholy grafu v bodě uvnitř kružnice dává sklony, které jsou poměry malých celých čísel. Počet různých sklonů získaných v této konstrukci je exponentem stupně grafu.

Obtížnost

Problém určení, zda je počet svahů roven dvěma, je NP-úplný [8] [9] [10] . Z toho vyplývá, že je NP-těžký problém určit počet sklonů libovolného grafu nebo toto číslo aproximovat se zaručenou účinností lepší než 3/2.

Zda je rovinný graf rovinnou kresbou se dvěma sklony, je také NP-úplný problém [11] .

Poznámky

  1. ↑ Wade, Chu, 1994 .
  2. ↑ Nezávisle prokázáno Baratem, Matouškem, Woodem (2006 ) a Pachem, Pálvölgyim (2006 ), když řešili problém, který nastolili Dujmovic, Suderman a Sharir ( Dujmović, Suderman, Wood (2005) ). Viz věty 5.1 a 5.2 v Pach a Sharir ( Pach and Sharir (2009 )).
  3. ↑ Mukkamala , Szegedy (2009 ), kteří vylepšili dřívější výsledek Keszegh, Pálvölgyi, Tóth (2008 )). Viz Pach a Sharir's Theorem 5.3 ( Pach and Sharir (2009 )).
  4. ↑ Mukkamala, Pálvölgyi, 2012 .
  5. ↑ Pach, Sharir, 2009 .
  6. ↑ Keszegh, Pach, Pálvölgyi, 2011 .
  7. ↑ Hansen, 1988 .
  8. ↑ Formann, Hagerup, Haralambides, Kaufmann, 1993 .
  9. ↑ Eades, Hong, Poon, 2010 .
  10. ↑ Maňuch, Patterson, Poon, Thachuk, 2011 .
  11. ↑ Garg, Tamassia, 2001 .

Literatura