Kink minimering

Ved visualisering af grafer , når grafens kanter er repræsenteret af stiplede linjer (en sekvens af segmenter forbundet ved brudpunkter ), er det ønskeligt at minimere antallet af brud pr. kant (nogle gange kaldet kurvekompleksitet ) [ 1] eller det samlede antal af brud i figuren [2] . Kink-minimering er en algoritmisk opgave med at finde et grafmønster, der minimerer de angivne værdier [3] [4] .

Udelukkelse af kinks

Et klassisk eksempel på kink-minimering er Fari-sætningen , som siger, at enhver plan graf kan tegnes uden kinks, det vil sige, at du kan finde en plan grafindlejring, hvor alle kanter vil være repræsenteret af segmenter [5] .

En grafrepræsentation, hvor kanterne ikke har nogen knæk og er parallelle med akserne, kaldes nogle gange en rektangulær repræsentation og er en af ​​varianterne af den ortogonale kantskæring repræsentation , hvor alle kantskæringer forekommer i rette vinkler [6] . Men at afgøre, om en plan graf har en rektangulær repræsentation, er et NP-komplet problem [7] . Det er også et NP-komplet problem at afgøre, om en vilkårlig graf har en rektangulær repræsentation givet kantskæringer [6] .

Kink minimering

Tamassia viste, at minimeringen af ​​knæk i et ortogonalt mønster af plane grafer, hvor knudepunkterne er placeret ved knudepunkterne i et heltalsgitter, og kanterne er tegnet som stiplede linjer bestående af segmenter parallelt med akserne, kan udføres i polynomium tid ved at overføre problemet til problemet med at finde minimumsomkostningsflowet [8 ] [9] . Men hvis vi ændrer måden, hvorpå den plane graf er indlejret, bliver kink-minimeringsproblemet NP-komplet og skal løses ved metoder som heltalsprogrammering , hvilket ikke garanterer både en nøjagtig løsning og hurtig drift [10] .

Flere knæk pr. kant

Mange graftegningsstile tillader knæk, men på en begrænset måde er kompleksiteten af ​​kurven for disse repræsentationer (det maksimale antal knæk pr. kant) begrænset til en konstant. At lade denne konstant vokse kan bruges til at forbedre andre karakteristika ved tegningen, såsom areal [1] . I nogle tilfælde er styling muligvis kun mulig, når løbeture er løst. For eksempel har ikke hver graf en repræsentation med ortogonal kantskæring uden knæk eller med kurvekompleksitet to, men enhver graf har et sådant mønster med kurvekompleksitet tre [11] .

Noter

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

Litteratur