Kulmaresoluutio (graafiteoria)

Graafisen piirustuksen kulmaresoluutio viittaa terävimpään kulmaan, jonka muodostavat kaksi piirustuksen samassa kärjessä kohtaavaa reunaa.

Ominaisuudet

Suhde vertex-asteen kanssa

Foreman ym . [1] havaitsivat, että minkä tahansa piirustuksen graafista, jonka segmentin reunat ovat maksimiasteella d , kulmaresoluutio ei ylitä — jos v on kärki, jonka aste on d , niin v :lle tulevat reunat jakavat tilan kärjen v ympärillä d - kiilaksi, joiden kokonaiskulma on , ja pienimmän näistä kiiloista ei saa olla suurempi kuin . Tarkemmin sanottuna, jos kuvaaja on d - säännöllinen , sen kulmaresoluutio on oltava pienempi kuin , koska tämä on paras resoluutio, joka voidaan saada kuvion kuperan rungon kärjelle.

Suhde graafin väritykseen

Kuten Foreman ym . [1] osoittavat, graafin G suurin mahdollinen kulmaresoluutio liittyy läheisesti graafin G 2 neliön kromaattiseen numeroon , eli graafiin, jolla on samat kärkijoukot, joissa jokainen kärkipari on yhdistetty reunalla, jos niiden välinen etäisyys graafissa G ei ole suurempi kuin kaksi. Jos graafi G 2 voidaan värjätä väreillä, niin G voidaan piirtää kulmaresoluutiolla mille tahansa :lle antamalla eri värit säännöllisen kulman kärjeille ja asettamalla kukin G :n kärki samanvärisen monikulmion kärjen viereen. Tätä rakennetta käyttämällä he osoittivat, että millä tahansa graafilla, jolla on maksimiaste d , on kuvio, jonka kulmaresoluutio on verrannollinen 1/ d2 : een . Tämä rajoitus on lähellä tarkkaa – he käyttivät todennäköisyyspohjaista menetelmää sellaisten graafien olemassaolon osoittamiseen, joiden maksimiaste on d ja joiden kaikilla piirroksilla on kulmaresoluutio .

Optimaalisten kuvioiden olemassaolo

Forman ym . [1] antoivat esimerkin, joka osoittaa, että on olemassa kaavioita, joissa ei ole kuvioita suurimmalla mahdollisella kulmaresoluutiolla. Päinvastoin, näissä kaavioissa on piirrosperhe, jonka kulmaresoluutioilla on taipumus olla rajoitettu arvo, mutta ne eivät saavuta sitä. Erityisesti he esittivät 11-pisteisen graafin, jonka kuvion kulmaresoluutio on mikä tahansa , mutta jolla ei ole kuviota, jonka kulmaresoluutio on täsmälleen .

Graafeiden erikoisluokat

Puut

Mikä tahansa puu voidaan piirtää siten, että reunat jakautuvat tasaisesti jokaisen kärjen ympärille, mikä on ominaisuus, joka tunnetaan nimellä täydellinen kulmaresoluutio . Lisäksi, jos reunat voidaan permutoida vapaasti jokaisen kärjen ympärillä, niin tällainen kuvio on mahdollista ilman leikkausta reunojen kanssa, joiden pituus on yksi tai useampi, ja koko kuvio sijoitetaan polynomialueen suorakulmioon . Kuitenkin, jos kunkin kärjen ympärillä olevien reunojen ympyräjärjestys on jo määritelty osana ongelmankäsitystä, kulmaresoluution saaminen ilman risteyksiä voi joskus vaatia eksponentiaalisen alueen [2] [3] .

Ulkotasokaaviot

Täydellinen kulmaresoluutio ei ole aina mahdollista ulompitasoisille graafeille , koska kuvion kuperan rungon pisteillä, joiden aste on suurempi kuin yksi, ei voi olla siihen kohdistuvia reunoja, jotka jakautuvat tasaisesti kärjen ympärille. Kuitenkin millä tahansa ulkotasolla, jonka aste on d , on ulkotasopiirros, jonka kulmaresoluutio on verrannollinen 1/ d :hen [4] [5] .

Tasokaaviot

Tasograafille , jonka aste on maksimi d , Foremanin (et al.) graafisen neliön väritystekniikka [1] tuottaa piirustuksen, jonka kulmaresoluutio on verrannollinen arvoon 1/ d , koska tasograafin neliöllä on oltava kromaattinen luku, joka on verrannollinen arvoon d . Wegner arveli vuonna 1977, että tasograafin neliön kromaattinen luku ei ylitä ja tiedetään, että kromaattinen luku ei ylitä [6] [7] . Tällä tekniikalla saatu kuvio ei kuitenkaan yleensä ole tasomainen.

Joillekin tasokaavioille tasopiirroksen optimaalinen kulmaresoluutio viivasegmenteillä on O(1/ d 3 ) , missä d on kuvaajan aste [5] . Lisäksi tällaisilla kuvioilla voidaan pakottaa olemaan erittäin pitkät reunat, pidempiä kuin kuvion lyhimmällä reunalla oleva eksponentiaalinen kerroin. Malitz ja Papakostas [4] käyttivät ympyrän pakkauslausetta osoittaakseen, että millä tahansa tasograafilla , jolla on maksimiaste d , on tasokuvio, jonka pahimman tapauksen kulmaresoluutio on d :n eksponentiaalinen funktio ja riippumaton graafin kärkien lukumäärästä.

Laskennallinen monimutkaisuus

Ongelma määrittää, onko tietyllä graafilla, jonka maksimiaste on d , kuvio, jolla on kulmaresoluutio, on NP-kova jopa erikoistapauksessa d =4 [1] [8] . Kuitenkin joillekin rajoitetuille piirustusluokille, mukaan lukien piirustukset puista, joissa lehtien jatkeet äärettömään muodostavat tason kuperan osion, sekä piirustukset tasokaavioista, joissa jokainen rajattu pinta on keskellä symmetrinen monikulmio, Piirustus optimaalisella kulmaresoluutiolla löytyy polynomiajassa [9] [10] .

Historia

Kulmaresoluutio määritteli Forman ym . [1] .

Vaikka se alun perin määriteltiin suorareunaisten graafien piirustuksiin, myöhemmin kirjoittajat tutkivat piirustusten kulmaresoluutiota, jossa reunat ovat monikulmio [11] [12] , ympyräkaareja [13] [2] tai splineitä [14] [15] . .

Kuvaajan kulmaresoluutio liittyy läheisesti sen leikkausresoluutioon, kuvaajapiirustuksen leikkauspisteiden muodostamiin kulmiin . Erityisesti kaavioiden piirtäminen suorassa kulmassa etsii esitystä, joka varmistaa, että kaikki nämä kulmat ovat suoria kulmia , mikä on suurin mahdollinen leikkauskulma [16]

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 Formann, Hagerup, Haralambides et ai., 1993 .
  2. ↑ 1 2 Duncan, Eppstein, Goodrich et ai., 2011 .
  3. ↑ Halupczok, Schulz, 2011 .
  4. ↑ 1 2 Malitz, Papakostas, 1994 .
  5. ↑ 1 2 Garg, Tamassia, 1994 .
  6. ↑ Kramer, Kramer, 2008 .
  7. ↑ Molloy, Salavatipour, 2005 .
  8. ↑ Garg, Tamassia, 1995 .
  9. ↑ Carlson, Eppstein, 2007 .
  10. ↑ Eppstein, Wortman, 2011 .
  11. ↑ Kant, 1996 .
  12. ↑ Gutwenger, Mutzel, 1998 .
  13. ↑ Cheng, Duncan, Goodrich, Kobourov, 1999 .
  14. ↑ Brandes, Shubina, Tamassia, 2000 .
  15. ↑ Finkel, Tamassia, 2005 .
  16. ↑ Didimo, Eades, Liotta, 2009 .

Kirjallisuus