Grafikon meredekségeinek száma

A gráfvizualizációban és a geometriai gráfelméletben a gráf meredekségeinek száma az élek különböző meredekségi együtthatóinak minimális lehetséges száma egy olyan gráf rajzában, amelyben a csúcsokat az euklideszi sík pontjai, az éleket pedig szegmensek ábrázolják. amelyek nem mennek át olyan csúcsokon, amelyek nem esnek ezekre az élekre.

Teljes grafikonok

Bár a kombinatorikus geometriában kapcsolódó problémákat már korábban is tanulmányozták (Scott 1970-ben és Jamison 1984-ben), a gráf meredekségei számának meghatározásának problémáját Wade és Chu [1] vetette fel , megmutatva, hogy a gráf meredekségeinek száma. egy teljes gráf K n csúcsával n pontosan n . Ilyen számú meredekségű gráf rajzát úgy kaphatjuk meg, ha a gráf csúcsait egy szabályos sokszög sarkaira helyezzük .

Kapcsolat a grafikon fokával

Nyilvánvaló, hogy a maximális d fokú gráf meredekségeinek száma legalább , mivel egy d fokú csúcsnak legfeljebb két beeső éle lehet egy egyenesen (egy meredekséggel rendelkezhet). Pontosabban, a lejtők száma nem kisebb, mint a gráf lineáris arborealitása , mivel ugyanazon lejtő élei lineáris erdőt alkotnak, és a lineáris arboreszcencia viszont nem lehet kisebb, mint .

Léteznek legfeljebb ötös fokú gráfok, amelyeknek tetszőlegesen sok meredeksége van [2] . Azonban minden gráfnak, amelynek maximum három foka van, legfeljebb négy meredeksége van [3] . Wade és Chu (1994 ) eredménye a K 4 teljes gráfra azt mutatja, hogy ez a korlát éles. Egyetlen négyes meredekhalmaz sem alkalmas az összes 3. fokú gráf megrajzolására - egy meredekhalmaz akkor és csak akkor alkalmas a rajzolásra, ha a paralelogramma oldalainak és átlóinak meredekségei . Konkrétan bármely 3. fokú gráf megrajzolható úgy, hogy élei vagy párhuzamosak legyenek az egész rács tengelyeivel, vagy párhuzamosak az egész rács főátlóival [4] . Nem ismert, hogy a legfeljebb négyes fokú gráfok meredekségeinek száma korlátos-e [5] .

Síkgráfok

Amint azt Keszegh, Pach, Pálvölgyi (2011 ) kimutatta, minden sík gráfnak van egy sík vonalszakasz mintája , amelyben a különböző meredekségek száma a gráf fokának függvénye. Bizonyításuk Malitz és Papakostas ( Malitz, Papakostas (1994 )) konstrukcióját követi a síkgráfok szögfelbontásának fok függvényében történő korlátozására. A fokkorlátozás úgy történik, hogy a gráfot egy maximális síkgráfra bővítjük anélkül, hogy a fokát egy állandó tényezőnél nagyobb mértékben növelnénk, majd a körcsomagolás tételét alkalmazzuk , hogy ezt a kiterjesztett gráfot érintőkörök halmazaként ábrázoljuk. Ha a kezdeti gráf foka korlátos, akkor a szomszédos körök sugarainak aránya is korlátos lesz [7] , ami viszont azt jelenti, hogy ha egy négyfát alkalmazunk minden gráfcsúcsra a körön belüli pontban, akkor olyan meredekségeket kapunk, kis egész számok arányai. Az ebben a konstrukcióban kapott különböző meredekségek száma a grafikon fokának kitevője.

Nehézség

Az a probléma, hogy meghatározzuk, hogy a meredekségek száma egyenlő-e kettővel, NP-teljes [8] [9] [10] . Ez azt jelenti, hogy NP-nehéz probléma egy tetszőleges gráf meredekségeinek számának meghatározása, vagy ennek a számnak a 3/2- nél jobb garantált hatásfokkal való közelítése.

Az is NP-teljes probléma, hogy egy síkgráf két meredekségű síkrajz-e [11] .

Jegyzetek

  1. ↑ Wade, Chu, 1994 .
  2. ↑ Barat, Matoušek, Wood (2006 ) és Pach, Pálvölgyi (2006 ) egymástól függetlenül bizonyította, amikor megoldották a Dujmovic, Suderman és Sharir által felvetett problémát ( Dujmović, Suderman, Wood (2005) ). Lásd Pach és Sharir 5.1 és 5.2 tételét ( Pach és Sharir (2009 )).
  3. ↑ Mukkamala , Szegedy (2009 ), aki Keszegh, Pálvölgyi, Tóth korábbi eredményét javította (2008 )). Lásd Pach és Sharir 5.3. tételét ( Pach és 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 .

Irodalom