Minimizarea îndoirii

La vizualizarea graficelor , când marginile graficului sunt reprezentate prin linii întrerupte (o succesiune de segmente conectate la puncte de întrerupere ), este de dorit să se minimizeze numărul de întreruperi pe muchie (uneori numită complexitatea curbei ) [1] sau numărul total de pauze în figura [2] . Minimizarea Kink este o sarcină algoritmică de găsire a unui model grafic care minimizează valorile specificate [3] [4] .

Excluderea îndoielilor

Un exemplu clasic de minimizare a îndoirii este teorema Fari , care afirmă că orice graf plan poate fi desenat fără îndoituri, adică puteți găsi un graf planar încorporat în care toate muchiile vor fi reprezentate prin segmente [5] .

O reprezentare grafică în care muchiile nu au îndoituri și sunt paralele cu axele este uneori numită reprezentare dreptunghiulară și este una dintre variantele reprezentării intersecției ortogonale a marginilor , în care toate intersecțiile marginilor apar în unghi drept [6] . Totuși, determinarea dacă un graf plan are o reprezentare dreptunghiulară este o problemă NP-completă [7] . Este, de asemenea, o problemă NP-complet să se determine dacă un graf arbitrar are o reprezentare dreptunghiulară dată intersecțiilor muchiilor [6] .

Minimizare Kink

Tamassia a arătat că reducerea la minimum a îndoiurilor într-un model ortogonal de grafice plane, în care vârfurile sunt situate la nodurile unei rețele întregi, iar marginile sunt desenate ca linii întrerupte constând din segmente paralele cu axele, poate fi realizată în polinomi. timp prin transferarea problemei la problema găsirii fluxului minim de cost [8 ] [9] . Totuși, dacă schimbăm modul în care este încorporat graficul plan, problema de minimizare a kink-ului devine NP-completă și trebuie rezolvată prin metode precum programarea cu numere întregi , care nu garantează atât o soluție precisă, cât și o funcționare rapidă [10] .

Mai multe îndoituri pe muchie

Multe stiluri de desenare grafică permit îndoituri, dar într-un mod limitat, complexitatea curbei acestor reprezentări (numărul maxim de îndoituri pe muchie) este limitată la o constantă. Permiterea acestei constante să crească poate fi folosită pentru a îmbunătăți alte caracteristici ale desenului, cum ar fi zona [1] . În unele cazuri, stilul poate fi posibil numai atunci când alergările sunt rezolvate. De exemplu, nu orice graf are o reprezentare cu intersecția marginilor ortogonale fără îndoituri sau cu complexitatea curbei doi, dar orice graf are un astfel de model cu complexitatea curbei trei [11] .

Note

  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. ↑ Cumpărare, 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.

Literatură