Gyűrődés minimalizálása

Grafikonok vizualizálása során, amikor a gráf éleit szaggatott vonalak ( szakadási pontokhoz kapcsolódó szegmensek sorozata ) ábrázolják , kívánatos minimalizálni az élenkénti törések számát (ezt néha görbe összetettségének nevezik ) [1] vagy a teljes számot. törések száma az ábrán [2] . A törés minimalizálása egy algoritmikus feladat egy olyan gráfminta megtalálására, amely minimalizálja a megadott értékeket [3] [4] .

A csavarodások kizárása

Klasszikus példája a törésminimalizálásnak a Fari-tétel , amely kimondja, hogy bármilyen síkgráf megrajzolható törés nélkül, vagyis találhatunk egy síkgráf beágyazást, amelyben minden él szegmensekkel lesz ábrázolva [5] .

Az olyan gráfábrázolást, amelyben az éleknek nincs törésük, és párhuzamosak a tengellyel, néha négyszögletes ábrázolásnak is nevezik, és az egyik változata a merőleges élmetszés ábrázolásnak , amelyben az összes élmetszés derékszögben fordul elő [6] . Azonban annak meghatározása, hogy egy síkgráfnak van-e téglalap alakú ábrázolása, NP-teljes probléma [7] . Szintén NP-teljes probléma annak meghatározása, hogy egy tetszőleges gráf téglalap alakú-e adott élmetszéspontokon [6] .

Gyűrődés minimalizálása

Tamassia megmutatta, hogy a törések minimalizálása síkgráfok ortogonális mintájában, ahol a csúcsok egy egész rács csomópontjainál helyezkednek el , az élek pedig szaggatott vonalakként vannak megrajzolva, amelyek tengelyekkel párhuzamos szegmensekből állnak, polinomiálisan is végrehajtható. időt úgy, hogy a problémát átvisszük a minimális költségáramlás megtalálásának problémájára [8 ] [9] . Ha azonban megváltoztatjuk a síkgráf beágyazási módját, a kink-minimalizálási probléma NP-teljessé válik, és olyan módszerekkel kell megoldani, mint az egészszámú programozás , ami nem garantálja a pontos megoldást és a gyors működést [10] .

Élenként több törés

Sok gráfrajz-stílus megengedi a csavarodást, de korlátozott módon ezen ábrázolások görbéjének összetettsége (az élenkénti csavarodások maximális száma) valamilyen állandóra korlátozódik. Ha hagyjuk, hogy ez az állandó növekedjen, az felhasználható a rajz egyéb jellemzőinek javítására, például a [1] területre . Egyes esetekben a stílus kialakítása csak akkor lehetséges, ha a kocogás megtörtént. Például nem minden gráfnak van ábrázolása merőleges élmetszésponttal törés nélkül, vagy kettős görbe bonyolultságú, de bármelyik gráfnak van ilyen mintája hármas görbe komplexitású [11] .

Jegyzetek

  1. ↑ 1 2 Di Giacomo, Didimo, Liotta, Meijer, 2011 , p. 565–575.
  2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 15–16.
  3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 145.
  4. ↑ Vásárlás, 1997 , p. 248–261.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 140.
  6. ↑ 1 2 Eades, Hong, Poon, 2010 , p. 232–243.
  7. ↑ Garg, Tamassia, 2001 , p. 601–625.
  8. ↑ Tamassia, 1987 , p. 421–444.
  9. ↑ Cornelsen, Karrenbauer, 2012 , p. 635–650.
  10. ↑ Mutzel, Weiskircher, 2002 , p. 484–493.
  11. ↑ Didimo, Eades, Liotta, 2009 , p. 206–217.

Irodalom