Buediagram

Et buediagram er en grafisk repræsentation , hvor hjørnerne er arrangeret langs en lige linje på det euklidiske plan , og kanterne er tegnet som halvcirkler på en af ​​de to halvplaner eller som glatte kurver dannet af halvcirklerne. I nogle tilfælde bruges linjesegmenter også til at repræsentere grafkanter, hvis de forbinder tilstødende hjørner på linjen.

Navnet "buediagram" for denne repræsentation af grafer er en efterfølger til brugen af ​​en lignende type Wattenberg-diagram [1] , som han brugte til at visualisere gentagne fragmenter af linjer ved at forbinde par af identiske delstrenge. Selve graffremstillingens stil er dog meget ældre end navnet og stammer fra Saaty [2] og Nicholsons [3] værker , som brugte buediagrammer til at studere antallet af grafers skæringspunkt . Et ældre men mindre brugt navn for buediagrammer er linjeindlejring [4] .

Heer, Bostock og Ogiwetsky [5] skrev, at buediagrammer "ikke kan udtrykke den fulde struktur af en graf så effektivt som en todimensionel repræsentation gør," men det gør det lettere at repræsentere multidimensionelle data forbundet med grafens hjørnepunkter.

Plane grafer

Som Nicholson [3] bemærkede , kan enhver indlejring af en graf i et plan konverteres til et buediagram uden at ændre antallet af skæringspunkter. Især har enhver plan graf et plan buediagram. En sådan indlejring kan dog kræve brug af mere end én halvcirkel til at tegne nogle af grafens kanter.

Hvis en graf tegnes uden buekrydsninger som et buediagram, hvor hver kant er repræsenteret af en enkelt halvcirkel, er tegningen en to-siders bogindlejring , hvilket kun er muligt for sub-Hamiltonske grafer , en delmængde af plane grafer [6 ] . For eksempel har en maksimal plan graf en sådan indlejring, hvis og kun hvis den indeholder en Hamiltonsk cyklus . En ikke-Hamiltonsk maksimal plan graf, såsom Goldner-Harari grafen, kan således ikke have en plan indlejring med en halvcirkel pr. kant. At kontrollere om en given graf har et buediagram uden skæringspunkter af denne type (eller tilsvarende, grafens bogtykkelse er to) er et NP-komplet problem [7] .

Imidlertid har enhver plan graf et buediagram, hvor hver kant er repræsenteret som en bi -bue , bestående af højst to halvcirkler. Mere strengt har enhver st -plan rettet graf (plan rettet acyklisk graf med en kilde og en sænk, begge på ydersiden) et buediagram, hvor enhver kant danner en monoton kurve, alle kurver (kanter) er rettet i samme retning [8] . For urettede plane grafer er en måde at konstruere et buediagram med højst to halvcirkler pr. kant ved at opdele grafen og tilføje flere kanter for at få en Hamiltonsk cyklus (hvor kanterne er opdelt i højst to dele), og brug derefter rækkefølgen langs Hamiltons cyklus som rækkefølgen af ​​hjørnerne på en ret linje [9] .

Minimering af kryds

Da kontrol af om en given graf har et buediagram uden skæringer med en halvcirkel pr. kant er et NP-komplet problem, er det også et NP-svært problem at finde et buediagram, der minimerer antallet af skæringspunkter. Problemet med at minimere antallet af skæringspunkter forbliver NP-hårdt for ikke-plane grafer, selvom rækkefølgen af ​​hjørnerne langs linjen allerede er givet [4] . Men i tilfælde af en given toppunktsrækkefølge kan en skæringsfri indlejring (hvis en sådan findes) findes i polynomisk tid ved at konvertere problemet til et 2-tilfredshedsproblem , hvor variablerne repræsenterer hver bues placering , og begrænsninger forhindrer to skærende kanter i at blive placeret langs den ene side af linjen med hjørner [10] . Derudover, i tilfælde af en fast placering af toppunkter, kan indlejringen med minimering af antallet af krydsninger tilnærmes ved at løse det maksimale skæringsproblem i en hjælpegraf, der repræsenterer halvcirkler og deres potentielle skæringspunkter [11] .

Kimikowski, Shoup [12] [13] , He, Sikora og Wrto [14] diskuterede heuristiske algoritmer til at finde buediagrammer med flere skæringspunkter.

Orientering med uret

For at repræsentere rettede grafer er den generelle konvention at rette buerne med uret, således at venstre-til-højre-buer tegnes over linjen, og højre-til-venstre-buer tegnes under linjen. Denne retningsretning med uret blev udviklet som en del af en anden stil af grafrepræsentation af en gruppe, der omfattede Fekete, Wang, Dang og Aris [15] , og Pretorius og van Wijk [16] anvendte denne stil på buediagrammer .

Andre anvendelser

Buediagrammer blev brugt af Brandes [17] til at visualisere skifteregistertilstandsdiagrammer , og af Jijev og Wrto [18] for at bevise, at skæringstallet for enhver graf mindst er lig med kvadratet af dens skærebredde.

Noter

  1. ↑ Wattenberg, 2002 .
  2. ↑ Saaty, 1964 .
  3. ↑ 12 Nicholson , 1968 .
  4. ↑ 1 2 Masuda, Nakajima, Kashiwabara, Fujisawa, 1990 .
  5. ↑ Heer, Bostock, Ogievetsky, 2010 .
  6. ↑ Anvendelsen af ​​halvcirkler til at tegne kanter i bogindlejring blev allerede brugt af Bernhart og Kainen i 1979 ( Bernhart, Kainen 1979 ), men den eksplicitte association af buediagrammer med to-siders indlejringer synes at skyldes Masuda, Nakajima, Kashiwabara, og 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. ↑ He, Sykora, Vrt'o, 2005 .
  15. ↑ Fekete, Wang, Dang, Aris, 2003 .
  16. ↑ Pretorius, van Wijk, 2007 .
  17. ↑ Brandes, 1999 .
  18. ↑ Djidjev, Vrt'o, 2002 .

Litteratur