Ív diagram

Az ívdiagram a gráfábrázolás olyan stílusa, amelyben a csúcsok az euklideszi síkon egy egyenes mentén vannak elrendezve , és az élek félkörként vannak megrajzolva a két félsík egyikén, vagy a félkörök által alkotott sima görbékként . Egyes esetekben a vonalszakaszokat a gráf éleinek ábrázolására is használják, ha a vonal szomszédos csúcsait kötik össze.

A gráfok ezen ábrázolására szolgáló "ívdiagram" elnevezés egy hasonló típusú Wattenberg-diagram használatának utódja [1] , amelyet az ismétlődő vonaltöredékek megjelenítésére használt azonos részláncpárok összekapcsolásával. Maga a gráfábrázolás stílusa azonban sokkal régebbi, mint a név, és Saaty [2] és Nicholson [3] munkáiból származik , akik ívdiagramokat használtak a gráfok metszéspontszámának tanulmányozására . Az ívdiagramok régebbi, de kevésbé használt neve a vonalbeágyazás [4] .

Heer, Bostock és Ogiwetsky [5] azt írta, hogy az ívdiagramok "nem tudják olyan hatékonyan kifejezni a gráf teljes szerkezetét, mint egy kétdimenziós ábrázolás", de megkönnyíti a gráf csúcsaihoz társított többdimenziós adatok ábrázolását.

Síkgráfok

Ahogy Nicholson [3] megjegyezte , a gráf bármely síkba ágyazása ívdiagrammá alakítható a metszéspontok számának megváltoztatása nélkül. Különösen minden síkgráfnak van síkív diagramja. Azonban egy ilyen egymásba ágyazás megkövetelheti egynél több félkör használatát a gráf egyes éleinek megrajzolásához.

Ha egy gráfot ívkeresztezések nélkül rajzolunk meg ívdiagramként, amelyben minden élt egyetlen félkör ábrázol, akkor a rajz egy kétoldalas könyvbeágyazás , ami csak a Hamilton alatti gráfoknál lehetséges , a síkgráfok egy részhalmaza [6 ] . Például egy maximális síkgráf akkor és csak akkor rendelkezik ilyen beágyazással, ha tartalmaz egy Hamilton-ciklust . Így egy nem Hamilton-féle maximális síkgráf, mint például a Goldner–Harari gráf , nem tartalmazhat síkbeli beágyazást élenként egy félkörrel. Annak ellenőrzése, hogy egy adott gráfnak van-e ívdiagramja ilyen típusú metszéspontok nélkül (vagy ennek megfelelően a gráf könyvvastagsága kettő), NP-teljes probléma [7] .

Azonban minden síkgráfnak van egy ívdiagramja, amelyben minden él bi -ívként van ábrázolva , amely legfeljebb két félkörből áll. Pontosabban, minden st -síkú irányított gráf (síkirányított aciklikus gráf egy forrással és egy nyelővel, mindkettő a külső felületen) rendelkezik egy ívdiagrammal, amelyben bármely él monoton görbét alkot, minden görbe (él) ugyanabban az irányban van irányítva. irány [8] . Irányítatlan síkgráfok esetén élenként legfeljebb két félkörből álló ívdiagram megalkotásának egyik módja az, hogy felosztjuk a gráfot, és további éleket adunk hozzá, hogy Hamilton-ciklust kapjunk (ahol az éleket legfeljebb két részre osztjuk), majd a sorrendet használjuk. a Hamilton-ciklus mentén, mint az egyenes csúcsainak sorrendje [9] .

A kereszteződések minimalizálása

Mivel annak ellenőrzése, hogy egy adott gráfnak van-e metszéspontok nélküli ívdiagramja élenként egy félkörrel, NP-teljes probléma, NP-nehéz feladat olyan ívdiagramot találni, amely minimalizálja a metszéspontok számát. A metszéspontok számának minimalizálásának problémája továbbra is NP-nehéz a nem síkbeli gráfok esetében, még akkor is, ha a csúcsok sorrendje az egyenes mentén már adott [4] . Adott csúcsrend esetén azonban találhatunk egy metszéspont nélküli beágyazást (ha van ilyen) polinomiális időben, ha a feladatot 2-es kielégítési problémává alakítjuk , ahol a változók az egyes ívek helyét reprezentálják. , és a megszorítások megakadályozzák, hogy két egymást metsző él a csúcsokkal rendelkező egyenes egyik oldalán legyen [10] . Ezen túlmenően a csúcsok rögzített elhelyezkedése esetén a metszéspontok számának minimalizálásával való egymásba ágyazás közelíthető a maximális vágási feladat megoldásával egy segédgráfban, amely félköröket és potenciális metszéspontjaikat ábrázolja [11] .

Kimikowski, Shoup [12] [13] , He, Sikora és Wrto [14] heurisztikus algoritmusokat tárgyalt több metszésponttal rendelkező ívdiagramok megtalálására.

Az óramutató járásával megegyező irányban

Az irányított gráfok ábrázolásához az általános konvenció az, hogy az íveket az óramutató járásával megegyező irányba irányítjuk, így a balról jobbra ívek a vonal fölé, a jobbról balra ívek pedig a vonal alá. Ezt az óramutató járásával megegyező irányú tájolási konvenciót egy másik gráfábrázolási stílus részeként dolgozta ki egy olyan csoport, amelynek tagjai Fekete, Wang, Dang és Aris [15] voltak , Pretorius és van Wijk [16] pedig ezt a stílust alkalmazta az ívdiagramokra .

Egyéb felhasználások

Az ívdiagramokat Brandes [17] használta az eltolási regiszter állapotdiagramjainak megjelenítésére , Jijev és Wrto [18] pedig annak bizonyítására, hogy bármely gráf metszéspontszáma legalább egyenlő a vágásszélesség négyzetével.

Jegyzetek

  1. ↑ Wattenberg, 2002 .
  2. ↑ Saaty, 1964 .
  3. ↑ 12 Nicholson , 1968 .
  4. ↑ 1 2 Masuda, Nakajima, Kashiwabara, Fujisawa, 1990 .
  5. ↑ Heer, Bostock, Ogievetsky, 2010 .
  6. ↑ A félkörök alkalmazását élek rajzolására a könyvbeágyazásban már Bernhart és Kainen is alkalmazta 1979-ben ( Bernhart, Kainen 1979 ), de az ívdiagramok explicit társítása kétoldalas egymásba ágyazással úgy tűnik, hogy Masuda, Nakajima, Kashiwabara, és Fujisawa ( Masuda, Nakajima, Kashiwabara, Fujisawa 1990 ).
  7. ↑ Chung, Leighton, Rosenberg, 1987 .
  8. ↑ Giordano, Liotta, Mchedlidze, Symvonis, 2007 .
  9. ↑ Bekos, Kaufmann, Kobourov, Symvonis, 2013 .
  10. ↑ Efrat, Erten, Kobourov, 2007 .
  11. ↑ Cimikowski, Mumey, 2007 .
  12. ↑ Cimikowski, Shope, 1996 .
  13. ↑ Cimikowski, 2002 .
  14. ↑ Ő, Sýkora, Vrt'o, 2005 .
  15. ↑ Fekete, Wang, Dang, Aris, 2003 .
  16. ↑ Pretorius, van Wijk, 2007 .
  17. ↑ Brandes, 1999 .
  18. ↑ Djidjev, Vrt'o, 2002 .

Irodalom