Číslo svahu - Slope number
v kreslení grafu a teorie geometrických grafů, číslo svahu grafu je minimální možný počet odlišných svahy hran ve výkresu grafu, ve kterém jsou vrcholy reprezentovány jako body v Euklidovské letadlo a hrany jsou znázorněny jako úsečky které neprocházejí žádným vrcholem bez incidentů.
Kompletní grafy
Ačkoli úzce související problémy v diskrétní geometrie byly studovány dříve, např. podle Scott (1970) a Jamison (1984), problém stanovení čísla sklonu grafu zavedl Wade & Chu (1994), který ukázal, že číslo svahu an n-vrchol kompletní graf K.n je přesněn. Výkres s tímto číslem sklonu lze vytvořit umístěním vrcholů grafu na a pravidelný mnohoúhelník.
Vztah k titulu
Číslo sklonu grafu maximálního stupně d je jasně přinejmenším , protože maximálně dva dopadající okrajed vrchol může sdílet sklon. Přesněji řečeno, číslo svahu se rovná alespoň lineární arboricita grafu, protože hrany jednoho svahu musí tvořit a lineární les a lineární arboricita je zase minimálně .
 | Nevyřešený problém v matematice: Mají grafy maximálního stupně čtyři ohraničené číslo sklonu? (více nevyřešených úloh z matematiky) |
Existují grafy s maximem stupeň pět, které mají libovolně velké číslo svahu.[1] Každý graf maximálního stupně tři má však číslo sklonu nejvýše čtyři;[2] výsledek Wade & Chu (1994) pro celý graf K.4 ukazuje, že je to těsné. Ne každá sada čtyř svahů je vhodná pro kreslení všech grafů stupně 3: sada svahů je pro tento účel vhodná, pokud tvoří svahy stran a úhlopříček rovnoběžník. Zejména lze nakreslit libovolný graf stupně 3 tak, aby jeho okraje byly buď osově rovnoběžné nebo rovnoběžné s hlavními úhlopříčkami celočíselná mřížka.[3] Není známo, zda grafy maximálního stupně čtyři mají hraniční nebo neomezené číslo sklonu.[4]
Rovinné grafy
Tak jako Keszegh, Pach & Pálvölgyi (2011) ukázal, každý rovinný graf má rovinný přímkový výkres ve kterém je počet odlišných svahů funkcí stupně grafu. Jejich důkaz navazuje na konstrukci Malitz & Papakostas (1994) za ohraničení úhlové rozlišení rovinných grafů jako funkce stupně, doplněním grafu k a maximální rovinný graf aniž by se zvýšil jeho stupeň o více než konstantní faktor, a použití věta o kruhu reprezentovat tento rozšířený graf jako soubor tečných kruhů. Pokud je stupeň počátečního grafu omezen, poměr mezi poloměry sousedních kruhů v balení bude také omezen prstencové lemma,[5] což zase znamená, že použití a čtyřstrom umístit každý vrchol grafu na bod v jeho kruhu vytvoří svahy, které jsou poměry malých celých čísel. Počet odlišných sklonů produkovaných touto konstrukcí je exponenciální ve stupni grafu.
Složitost
to je NP-kompletní k určení, zda má graf sklon číslo dvě.[6] Z toho vyplývá, že je NP-těžké určit číslo sklonu libovolného grafu nebo jej aproximovat pomocí přibližný poměr lepší než 3/2.
Je také NP-úplné určit, zda má rovinný graf rovinný výkres se sklonem číslo dva,[7]a těžké pro existenciální teorie skutečností k určení minimálního čísla sklonu rovinného výkresu.[8]
Poznámky
- ^ Nezávisle prokázáno Barát, Matoušek & Wood (2006) a Pach & Pálvölgyi (2006), řešení problému, který představuje Dujmović, Suderman & Wood (2005). Viz věty 5.1 a 5.2 z Pach & Sharir (2009).
- ^ Mukkamala & Szegedy (2009), zlepšení dřívějšího výsledku z Keszegh a kol. (2008); věta 5.3 z Pach & Sharir (2009).
- ^ Mukkamala & Pálvölgyi (2012).
- ^ Pach & Sharir (2009).
- ^ Hansen (1988).
- ^ Formann a kol. (1993); Eades, Hong & Poon (2010); Maňuch a kol. (2011).
- ^ Garg & Tamassia (2001).
- ^ Hoffmann (2016).
Reference
- Barát, János; Matoušek, Jiří; Wood, David R. (2006), „Grafy ohraničeného stupně mají libovolně velkou geometrickou tloušťku“, Electronic Journal of Combinatorics, 13 (1): R3, PAN 2200531.
- Dujmović, Vida; Suderman, Matthew; Wood, David R. (2005), "Really straight graph drawing", in Pach, János (vyd.), Kresba grafu: 12. mezinárodní sympozium, GD 2004, New York, NY, USA, 29. září - 2. října 2004, revidované vybrané příspěvky, Přednášky z informatiky, 3383, Berlín: Springer-Verlag, s. 122–132, arXiv:cs / 0405112, doi:10.1007/978-3-540-31843-9_14.
- Eades, Peter; Hong, Seok-Hee; Poon, Sheung-Hung (2010), „O přímém kreslení grafů“, in Eppstein, David; Gansner, Emden R. (eds.), Kreslení grafu: 17. mezinárodní sympozium, GD 2009, Chicago, IL, USA, 22. – 25. Září 2009, revidované příspěvky, Přednášky v informatice, 5849, Berlín: Springer, s. 232–243, doi:10.1007/978-3-642-11805-0_23, PAN 2680455.
- 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 (2001), „O výpočetní složitosti vzestupného a přímočarého testování rovinnosti“, SIAM Journal on Computing, 31 (2): 601–625, doi:10.1137 / S0097539794277123, PAN 1861292.
- Hansen, Lowell J. (1988), „On the Rodin and Sullivan ring lemma“, Složité proměnné, teorie a aplikace, 10 (1): 23–30, doi:10.1080/17476938808814284, PAN 0946096.
- Hoffmann, Udo (2016), „Číslo rovinného svahu“, Sborník příspěvků z 28. kanadské konference o výpočetní geometrii (CCCG 2016).
- Jamison, Robert E. (1984), "Rovinné konfigurace, které určují několik svahů", Geometriae Dedicata, 16 (1): 17–34, doi:10.1007 / BF00147419, PAN 0757792.
- Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör (2011), „Kreslení rovinných grafů ohraničeného stupně s několika svahy“, Brandes, Ulrik; Cornelsen, Sabine (eds.), 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, Heidelberg: Springer, str. 293–304, arXiv:1009.1315, doi:10.1007/978-3-642-18469-7_27, PAN 2781274.
- Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör; Tóth, Géza (2008), „Kreslení kubických grafů s maximálně pěti svahy“, Výpočetní geometrie: Teorie a aplikace, 40 (2): 138–147, doi:10.1016 / j.comgeo.2007.05.003, PAN 2400539.
- 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.
- Maňuch, Ján; Patterson, Murray; Poon, Sheung-Hung; Thachuk, Chris (2011), „Složitost hledání nerovinných přímých kreseb grafů“, Brandes, Ulrik; Cornelsen, Sabine (eds.), 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, Heidelberg: Springer, str. 305–316, doi:10.1007/978-3-642-18469-7_28, hdl:10281/217381, PAN 2781275.
- Mukkamala, Padmini; Szegedy, Mario (2009), „Geometrické znázornění kubických grafů se čtyřmi směry“, Výpočetní geometrie: Teorie a aplikace, 42 (9): 842–851, doi:10.1016 / j.comgeo.2009.01.005, PAN 2543806.
- Mukkamala, Padmini; Pálvölgyi, Dömötör (2012), „Kreslení kubických grafů se čtyřmi základními svahy“, van Kreveld, Marc; Speckmann, Bettina (eds.), Kresba grafu: 19. mezinárodní sympozium, GD 2011, Eindhoven, Nizozemsko, 21. – 23. Září 2011, revidované vybrané příspěvky, Přednášky v informatice, 7034, Springer, str. 254–265, arXiv:1106.1973, doi:10.1007/978-3-642-25878-7_25.
- Pach, János; Pálvölgyi, Dömötör (2006), „Grafy ohraničeného stupně mohou mít libovolně velká čísla sklonu“, Electronic Journal of Combinatorics, 13 (1): N1, PAN 2200545.
- Pach, János; Sharir, Micha (2009), „5.5 Úhlové rozlišení a sklony“, Kombinatorická geometrie a její algoritmické aplikace: Alcalá přednáškyMatematické průzkumy a monografie 152, Americká matematická společnost, str. 126–127.
- Scott, P. R. (1970), „O sadách směrů určených n body ", Americký matematický měsíčník, 77: 502–505, doi:10.2307/2317384, PAN 0262933.
- Wade, G. A .; Chu, J.-H. (1994), „Drawability of complete graphs using a minimal sklon set“, Počítačový deník, 37 (2): 139–142, doi:10.1093 / comjnl / 37.2.139.