Graafisten piirtäminen suorassa kulmassa

Graafin suorassa kulmassa piirtäminen (RAC=right angle crossing, RAC) on piirustus, jossa kärjet esitetään pisteillä ja reunat viivasegmenteillä tai polylineillä , enintään kaksi reunaa leikkaa yhdessä pisteessä, ja jos kaksi reunaa leikkaavat, niiden on leikattava suorassa kulmassa .

Oikean kulman piirustustyyliä ja nimeä "RAC-piirustus" tälle tyylille ehdottivat Didimo, Eides ja Liotta [1] , ja tämä tyyli syntyi sen jälkeen, kun havaittiin, että suuren leikkauspisteen graafin piirtäminen suurissa kulmissa luetaan paremmin kuin piirustukset pienet kulmat [2] . Jopa tasokaavioissa joidenkin reunojen ylittäminen suorassa kulmassa voi parantaa merkittävästi piirustuksen ominaisuuksia, kuten pinta- alaa tai kulmaresoluutiota [3] .

Esimerkkejä

Koko graafissa K 5 on RPU-kuvio suorilla reunoilla, mutta K 6 : lla ei. Kaikissa RPC-piirustuksissa, joissa on 6 kärkeä, on enintään 14 reunaa ja K6 : ssa 15 reunaa, mikä on liikaa RPU-piirrokselle [1] .

Täydellisellä kaksiosaisella graafilla Ka , b on RPC -kuvio janoilla silloin ja vain jos min( a , b ) ≤ 2 tai a  +  b  ≤ 7. Jos min( a , b ) ≤ 2, niin graafi on tasomainen , ja ( Farin lauseen mukaan ) millä tahansa tasograafilla on kuvio suoraosien muodossa ilman leikkauspisteitä. Tällaiset piirustukset kuuluvat automaattisesti RAC-luokkaan. Vain kaksi tapausta on jäljellä, kaaviot K 3,3 ja K 3,4 . Kuva K 3.4 näkyy kuvassa. K 3,3 saadaan K 3,4 :stä poistamalla yksi kärki. Yhdelläkään kaavioista K 4.4 ja K 3.5 ei ole RPU-kuviota [4] .

Kylkiluut ja mutkat

Jos graafissa, jossa on n kärkeä, on RPC-esitys segmentin reunoilla, siinä voi olla enintään 4n  − 10 reunaa. Rajoitus on tiukka – on olemassa RPC-esityksellä varustettuja graafeja, joissa on täsmälleen 4n  − 10 reunaa [1] . Piirustuksissa, joissa on katkenneet reunat, graafin reunojen määrä riippuu reunaa kohti sallittujen katkosten määrästä. Graafeissa, joissa on RPC-esitys, jossa on yksi tai kaksi taivutusta reunaa kohti, on O( n ) reunaa. Tarkemmin sanottuna yhdellä taitolla reunojen lukumäärä ei saa ylittää 6,5 n ja kahdella taitolla 74,2 n [5] . Jokaisella graafilla on RPC-esitys, jos kolme taittumista reunaa kohden [1] sallitaan .

Suhde 1-tasoisuuteen

Graafi on 1-tasoinen , jos siinä on kuvio, jossa on enintään yksi leikkauspiste per reuna. On intuitiivisesti selvää, että tämä rajoitus helpottaa graafin esittämistä, jossa reunat risteävät suorassa kulmassa, ja rajoite 4 n  − 10 RPC-esityksen reunojen lukumäärälle, jossa reunat ovat segmenttejä, on lähellä 4 n  − 8 rajaa. 1-tasoisten graafien reunojen lukumäärä ja lähellä 4 n  − 9 -rajaa reunojen lukumäärä 1-tasograafisten esityksissä, joissa reunat ovat segmentteinä. Mikä tahansa RPC-esitys, jossa on 4n  − 10 reunaa, on 1-tasoinen [6] [7] . Lisäksi millä tahansa 1-ulkotason graafilla (eli graafilla, jossa on yksi leikkauspiste reunaa kohden, jossa kaikki kärjet ovat piirustuksen ulkopinnalla) on RPC-esitys [8] . On kuitenkin olemassa 1-tasograafisia graafisia 4 n  − 10 reunaa, joilla ei ole RPC-esitystä [6] .

Laskennallinen monimutkaisuus

Ongelma sen määrittämisessä, onko RPC-graafissa viivasegmenttiesitys, on NP-kova [9] ja RPC-piirustuksen rakenne on samanlainen kuin alhaalta ylöspäin suuntautuva tasopiirros [10] . 1-ulompitasoisten graafien erikoistapauksessa RPC-esitys voidaan kuitenkin rakentaa lineaarisessa ajassa [11] .

Muistiinpanot

  1. ↑ 1 2 3 4 Didimo, Eades, Liotta, 2009 , s. 206-217.
  2. ↑ Huang, Hong, Eades, 2008 , s. 41–46.
  3. ↑ van Kreveld, 2011 , s. 371-376.
  4. ↑ Didimo, Eades, Liotta, 2010 , s. 687–691.
  5. ↑ Arikushi, Fulek, Keszegh et ai., 2012 , s. 169-177.
  6. ↑ 1 2 Eades, Liotta, 2013 , s. 961–969.
  7. ↑ Ackerman, 2014 , s. 104-108.
  8. ↑ Dehkordi, Eades, 2012 , s. 543–557.
  9. ↑ Argyriou, Bekos, Symvonis, 2011 , s. 74–85.
  10. ↑ Angelini, Cittadini, Di Battista et ai., 2010 , s. 21–32.
  11. ↑ Auer, Bachmaier, Brandenburg et ai., 2013 , s. 107-118.

Kirjallisuus