Pyöreä järjestely

Pyöreä järjestely on graafin visualisointityyli  , jossa graafin kärjet on järjestetty ympyrään , usein tasaisin välein siten, että ne muodostavat säännöllisen monikulmion kärjet .

Sovellus

Pyöreä järjestely soveltuu hyvin verkkoviestintätopologioihin , kuten tähti tai rengas [1] , sekä metabolisten verkkojen syklisiin osiin [2] . Graafeissa, joissa on tunnettu Hamiltonin sykli , ympyräjärjestely mahdollistaa syklin esittämisen ympyränä; tällainen ympyräjärjestely muodostaa perustan Hamiltonin kuutiograafien LCF-koodille [3] .

Ympyränmuotoista järjestelyä voidaan käyttää kokonaisen graafin visualisoimiseen, mutta sitä voidaan käyttää myös fragmenteille, kuten graafin kärkiklustereille, sen kaksoisliittyneille komponenteille [1] [4] , geeniklusteille geenivuorovaikutuskaaviossa [5] tai luonnollisille alaryhmille sosiaalinen verkosto [6] . Käyttämällä useita ympyröitä, joissa on graafin kärkipisteitä, voidaan soveltaa muita klusterointimenetelmiä, kuten voiman visualisointialgoritmeja [7] .

Pyöreän järjestelyn etu esimerkiksi bioinformatiikan tai sosiaalisten verkostojen visualisoinnin aloilla on sen visuaalinen neutraalisuus [8]  - kun kaikki kärjet sijaitsevat yhtä etäisyydellä toisistaan ​​ja kuvan keskustasta, mikään solmuista ei ole käytössä. etuoikeutettu keskitetty asema. Tämä on tärkeää, koska on olemassa psykologinen taipumus pitää keskustan lähellä olevat solmut tärkeämpinä [9] .

Reunatyyli

Graafisen kuvan reunat voivat olla ympyräjänteitä [10] , ympyräkaavia [ 11] (mahdollisesti kohtisuorassa ympyrään nähden jossakin pisteessä, jolloin mallin reunat on järjestetty suoriksi hyperbolisen geometrian Poincarén mallissa ) tai muun tyyppiset käyrät [12] .

Ympyrän sisä- ja ulkopuolen välistä visuaalista eroa pyöreässä järjestelyssä voidaan käyttää kahden tyyppisen reunakuvan erottamiseen. Esimerkiksi Gansnerin ja Corenin [12] ympyrän piirustusalgoritmi käyttää ympyrän sisällä olevien reunojen ryhmittelyä yhdessä joidenkin ympyrän ulkopuolella olevien ryhmittämättömien reunojen kanssa [12] .

Säännöllisten kuvaajien ympyrämäisessä järjestelyssä , jossa reunat on piirretty ympyrän sisä- ja ulkopuolelle kaareina , tulokulmat (kulma tangentin kanssa pisteessä) ovat samat kaaren molemmilla puolilla, mikä yksinkertaistaa kuvan kulmaresoluution optimointi [11] .

Ylitysten määrä

Jotkut kirjoittajat tutkivat ongelmaa löytää pyöreän järjestelyn kärkien permutaatio , joka minimoi leikkauspisteiden lukumäärän, kun kaikki reunat piirretään ympyrän sisään. Tämä leikkausnumero on nolla vain ulkotasokaavioissa [10] [13] . Muissa kaavioissa se voidaan optimoida tai pienentää erikseen jokaiselle kaksoiskytkentäiselle graafikomponentille ennen ratkaisun luomista, koska tällaiset komponentit voidaan piirtää ilman, että ne ovat vuorovaikutuksessa toistensa kanssa [13] .

Yleisesti ottaen leikkauspisteiden määrän minimointi on NP-täydellinen ongelma [14] , mutta se voidaan approksimoida kertoimella , jossa n on yhtä suuri kuin pisteiden lukumäärä [15] . Myös heuristisia menetelmiä on kehitetty vähentämään monimutkaisuutta, kuten sellaisia, jotka perustuvat hyvin harkittuun huippupisteiden lisäysjärjestykseen ja paikalliseen optimointiin [16] [1] [10] [17] [13] .

Myös ympyränmuotoista järjestelyä voidaan käyttää maksimoimaan risteysten lukumäärä. Erityisesti pisteiden satunnaisen permutoinnin valitseminen johtaa leikkauspisteeseen, jonka todennäköisyys on 1/3, joten odotettu leikkauspisteiden määrä voi olla kolme kertaa suurin leikkauspisteiden lukumäärä kaikkien mahdollisten huippupisteiden joukossa. Tämän menetelmän derandomisointi antaa deterministisen approksimaatioalgoritmin , jonka approksimaatiokerroin on kolme [18] .

Muut optimikriteerit

Myös ympyräjärjestelyn ongelmia ovat ympyränmuotoisen järjestelyn reunojen pituuden optimointi, leikkauspisteiden kulmaresoluutio tai leikkauksen leveys (maksimi määrä reunoja, jotka yhdistävät ympyräkaaret vastakkaisiin) [16] [12] [19] [20] ; monet näistä ongelmista ovat NP-täydellisiä [16] .

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 Doğrusöz, Madden, Madden, 1997 .
  2. ↑ Becker, Rojas, 2001 .
  3. ↑ Pisanski, Servatius, 2013 .
  4. ↑ Six, Tollis, 1999b .
  5. ↑ Symeonidis, Tollis, 2004 .
  6. ↑ Krebs, 1996 .
  7. ↑ Doğrusöz, Belviranli, Dilek, 2012 .
  8. ↑ Iragne, Nikolski, Mathieu, Auber, Sherman, 2005 .
  9. ↑ Huang, Hong, Eades, 2007 .
  10. ↑ 1 2 3 Six, Tollis, 1999a .
  11. ↑ 1 2 Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2012 .
  12. ↑ 1 2 3 4 Gansner, Koren, 2007 .
  13. ↑ 1 2 3 Baur, Brandes, 2005 .
  14. ↑ Masuda, Kashiwabara, Nakajima, Fujisawa, 1987 .
  15. ↑ Shahrokhi, Sýkora, Székely, Vrt'o, 1995 .
  16. ↑ 1 2 3 Mäkinen, 1988 .
  17. ↑ Hän, Sýkora, 2004 .
  18. ↑ Verbitsky, 2008 .
  19. ↑ Nguyen, Eades, Hong, Huang, 2011 .
  20. ↑ Dehkordi, Nguyen, Eades, Hong, 2013 .

Kirjallisuus