Minimalizace kink

Při vizualizaci grafů , kdy jsou okraje grafu reprezentovány přerušovanými čarami (sekvence segmentů spojených v bodech přerušení ), je žádoucí minimalizovat počet zlomů na hraně (někdy nazývané složitost křivky ) [1] nebo celkový počet přestávek na obrázku [2] . Minimalizace Kink je algoritmický úkol najít vzor grafu, který minimalizuje zadané hodnoty [3] [4] .

Vyloučení zlomů

Klasickým příkladem minimalizace zalomení je Fariho teorém , který říká, že jakýkoli rovinný graf lze nakreslit bez zalomení, to znamená, že můžete najít vložení rovinného grafu, ve kterém budou všechny hrany reprezentovány segmenty [5] .

Znázornění grafu, ve kterém hrany nemají žádné zlomy a jsou rovnoběžné s osami, se někdy nazývá pravoúhlé zobrazení a je jednou z variant zobrazení ortogonálního průniku hran , ve kterém se všechny průsečíky hran vyskytují v pravém úhlu [6] . Určení, zda má rovinný graf pravoúhlé zobrazení, je však NP-úplný problém [7] . To je také NP-úplný problém určit zda libovolný graf má pravoúhlou reprezentaci daný okrajové průsečíky [6] .

Minimalizace kink

Tamassia ukázal, že minimalizaci zlomů v ortogonálním vzoru rovinných grafů, ve kterých jsou vrcholy umístěny v uzlech celočíselné mřížky a hrany jsou nakresleny jako přerušované čáry sestávající ze segmentů rovnoběžných s osami, lze provést v polynomu . času přenesením problému do problému hledání toku minimálních nákladů [8 ] [9] . Pokud však změníme způsob vkládání rovinného grafu, problém minimalizace zalomení se stane NP-úplným a musí být řešen metodami jako celočíselné programování , které nezaručuje jak přesné řešení, tak rychlou operaci [10] .

Několik zalomení na hraně

Mnoho stylů kreslení grafů umožňuje zlomy, ale v omezené míře je složitost křivky těchto zobrazení (maximální počet zlomů na hranu) omezena na určitou konstantu. Umožnění růstu této konstanty lze využít ke zlepšení dalších charakteristik kresby, jako je plocha [1] . V některých případech může být styling možný pouze v případě, že jsou odstraněny posuny. Například ne každý graf má zobrazení s ortogonálním průsečíkem hran bez zalomení nebo se složitostí křivky dva, ale každý graf má takový vzor se složitostí křivky tři [11] .

Poznámky

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

Literatura