Topologisessa graafiteoriassa 1-tasograafi on graafi , joka voidaan piirtää euklidiseen tasoon siten , että kullakin reunalla on enintään yksi leikkauspiste vain yhden toisen reunan kanssa.
1-tasokaavioita tarkasteli ensin Ringel, joka osoitti, että ne voidaan värjätä enintään seitsemällä värillä [1] . Myöhemmin näiden kaavioiden värittämiseen tarvittavien värien tarkka määrä väheni (pahimmassa tapauksessa) kuuteen [2] . Esimerkki täydellisestä K 6 -kaaviosta , joka on 1-tasoinen, osoittaa, että 1-tasoiset kaaviot voivat joskus vaatia kuusi väriä värittämiseen. Kuuden värin riittävyyden todistaminen ei kuitenkaan ole helppoa.
Syynä Ringelin 1-tasograafien harkitsemiseen oli yritys ratkaista tasograafien kokonaisväritysongelman variantti, jossa tasograafin kärjet ja pinnat on väritetty siten, että kahdella vierekkäisellä pisteellä ei ole samaa väri ja mahdolliset kaksi vierekkäistä pintaa tulee myös värjätä eri väreillä.värien sekä niiden viereisten kärkien ja pintojen värien tulee olla erilaisia. Ilmeisesti tämä voidaan tehdä kahdeksalla värillä, jos käytämme neljän värin lausetta graafille ja sen kaksoisgraafille erikseen käyttämällä kahta neljän värin disjunktoitua joukkoa. Voit kuitenkin saada vähemmän värejä, jos muodostat apugraafin, jolla on piste jokaiselle alkuperäisen tasograafin pisteelle ja pinnalle ja jossa apugraafin kaksi kärkeä ovat vierekkäin, jos ne vastaavat annetun tasograafin vierekkäisiä objekteja. . Apugraafin kärkiväritys vastaa alkuperäisen tasograafin väritystä. Apugraafi on 1-tasoinen, mikä tarkoittaa, että Ringelin kärjen ja kasvojen väritysongelma voidaan ratkaista kuudella värillä [2] . Graafia K 6 ei voi saada apugraafiksi tällä tavalla, mutta kuitenkin pisteiden ja pintojen väritysongelma vaatii joskus kuusi väriä. Jos esimerkiksi värität kolmiomaisen prisman tasograafin , sen 6 kärkeä + 5 pintaa vaativat kuusi väriä [3] .
Millä tahansa 1-tasoisella graafilla, jossa on n kärkeä, on enintään 4n − 8 reunaa [4] . Tarkemmin sanottuna jokaisessa 1-tasograafin piirroksessa on enintään n − 2 leikkauspistettä . Yhden reunan poistaminen kustakin leikkaavasta reunaparista jättää tasograafin, jossa on enintään 3n − 6 reunaa, mikä tarkoittaa välittömästi alkuperäisen 1-tasograafin 4n − 8 reunarajaa [5] . Kuitenkin toisin kuin tasograafit (joille kaikilla tietyn kärkijoukon maksimaalisilla tasograafilla on sama määrä reunoja), on olemassa maksimi 1-tasograafit (kuvaajat, joihin ei voida lisätä reunaa samalla kun 1-tasoisuus säilyy). olennaisesti vähemmän kuin 4 n − 8 reunaa [6] . 4 n − 8, joka on sidottu 1-tasoisen graafin enimmäismäärään reunoja, voidaan käyttää osoittamaan, että täydellinen graafi K 7 , jossa on seitsemän kärkeä, ei ole 1-tasoinen, koska tässä graafissa on 21 reunaa ja sitten 4 n . − 8 = 20 < 21 [7] .
1-tasograafin sanotaan olevan optimaalinen 1-tasograafi, jos siinä on täsmälleen 4n − 8 reunaa, suurin mahdollinen määrä. Optimaalisen 1-tasoisen graafin 1-tasoisessa upotuksessa ei-leikkaavat reunat muodostavat välttämättä laatoituksen nelikulmioiksi (eli muodostavat monitahoisen graafin , jossa jokainen pinta on nelikulmio ). Mikä tahansa neliö muodostaa 1-tasoisen kuvaajan lisäämällä kaksi diagonaalia jokaiseen neliöpintaan. Tästä seuraa, että mikä tahansa optimaalinen 1-tasograafi on Eulerin (kaikilla sen pisteillä on parillinen aste ), että pienin aste näissä graafisissa on 6 ja että missä tahansa optimaalisessa 1-tasograafissa on vähintään kahdeksan kärkeä, joilla on täsmälleen kuusi astetta. Lisäksi mikä tahansa optimaalinen 1-tasograafi on yhdistetty 4-pisteisiin ja mikä tahansa 4-pisteinen osa tällaisessa graafissa on leikkaussykli alla olevassa nelikulmiossa [8] .
Kaavioissa, joissa on suoraviivaisia 1-tasoisia piirroksia (eli piirustuksia, joissa jokaista reunaa edustaa suora viivasegmentti ja kunkin segmentin leikkaa enintään yksi muu reuna), on hieman vahvempi raja 4 n − 9 maksimimäärällä reunat, mikä saavutetaan äärettömällä määrällä graafia [9] .
Täydellinen luokittelu 1-tasoisille täydellisille graafisille , täydellisille kaksiosaisille kaavioille ja yleisemmille täydellisille moniosaisille kaavioille tunnetaan. Mikä tahansa täydellinen kaksiosainen graafi muotoa K 2, n on 1-tasoinen, kuten myös täydellinen kolmiosainen graafi muotoa K 1,1, n . Näiden äärettömien joukkojen lisäksi täydelliset moniosaiset 1-tasograafit ovat K 6 , K 1,1,1,6 , K 1,1,2,3 , K 2,2,2,2 , K 1,1,1, 2 ,2 ja niiden alagraafit. Minimaaliset täydelliset moniosaiset graafit, jotka eivät ole 1-tasoisia, ovat K 3,7 , K 4,5 , K 1,3,4 , K 2,3,3 ja K 1,1,1,1,3 . Esimerkiksi täydellinen kaksiosainen graafi K 3,6 on 1-tasoinen, koska se on K 1,1,1,6 -osagraafi , mutta K 3,7 ei ole 1-tasoinen [7] .
Graafin 1-tasoisen tarkastaminen on NP-täydellinen [10] [11] ja ongelma pysyy NP-täydellisenä jopa graafisille, jotka on saatu tasograafista lisäämällä yksi reuna [12] ja graafisille, joiden leveys on rajoitettu [ 13] .
Ongelma on kiinteäparametrisesti ratkaistava , jos se parametroidaan syklomaattisen luvun tai puun syvyyden perusteella , joten se voidaan ratkaista polynomiajassa , jos nämä parametrit ovat rajoitettuja [13] .
Toisin kuin tasograafien Fareen lauseessa , kaikkia 1-tasoisia graafisia ei voida piirtää 1- tasoisina janat reunoilla [14] [15] . Polynomiajassa voidaan kuitenkin tarkistaa, voidaanko 1-tasoinen graafi piirtää suorilla reunoilla [16] . Lisäksi missä tahansa vertex-3-liitetyssä 1-tasograafissa on 1-tasopiirustus, jossa korkeintaan yksi reuna ulkopinnalla on mutka . Tällainen piirustus voidaan rakentaa lineaarisessa ajassa 1-tasograafisen upotuksen perusteella [17] . 1-tasokaavioilla on rajoitettu kirjan paksuus [18] , mutta joidenkin 1-tasograafien, mukaan lukien K 2,2,2,2 , kirjan paksuus on vähintään neljä [19] .
1-tasokaavioilla on rajoitettu paikallinen puunleveys , mikä tarkoittaa, että on olemassa (lineaarinen) funktio f siten, että halkaisijaltaan d olevien 1- tasokaavioiden puunleveys on enintään f ( d ). Sama ominaisuus pätee yleisempiin kuvaajiin, jotka voidaan upottaa rajatun suvun pintaan rajatulla määrällä risteyksiä reunaa kohti. Niissä on myös erottimet , pieni joukko kärkipisteitä, joiden poistaminen hajottaa graafin yhdistetyiksi komponenteiksi, joiden koko on vakio murto-osa koko graafista. Näiden ominaisuuksien perusteella lukuisia tasograafialgoritmeja, kuten Brenda Sue Bakerin approksimaatioalgoritmien konstruointitekniikkaa , voidaan laajentaa 1-tasograafisiksi graafisiksi . Tämä menetelmä johtaa esimerkiksi likimääräiseen polynomiaikakaavioon 1-tasograafin suurimman riippumattoman joukon löytämiseksi [20] .
1- tasotason ulkotason graafien kanssa analogista kuvaajien luokkaa kutsutaan ulompi-1- tasograafiksi . Nämä ovat kaavioita, jotka voidaan piirtää levylle, jonka kärjet ovat levyn rajalla ja joiden reunoilla on enintään yksi leikkauspiste reunaa kohden. Nämä graafit voidaan aina piirtää (ulkopuolisesti 1-tasoisena graafina) suorilla reunoilla ja suorakulmaisilla leikkauspisteillä [21] . Käyttämällä dynaamista ohjelmointia tietyn graafin SPQR-puussa on mahdollista tarkistaa, onko graafi ulkoisesti 1-tasoinen lineaarisessa ajassa [22] [23] . Kolmikytketyt graafikomponentit (SPQR-puusolmut) voivat koostua vain sykleistä , bondgrafeista ja täydellisistä graafista , joissa on neljä kärkeä, mikä tarkoittaa, että ulkoisesti 1-tasoiset graafit ovat tasomaisia ja niiden puun leveys on enintään kolme. Toisin kuin 1-tason graafit, ulkoisilla 1-tasograafisilla graafilla on karakterisointi graafin molempien suhteen - graafi on ulkoinen 1-taso, jos ja vain jos se ei sisällä mitään viidestä kielletystä alaväristä [23] .
1-tasograafien luokkaan kuuluvat 4-kartan graafit , tason vierekkäisistä alueista muodostetut graafit sillä ehdolla, että mikään piste ei ole useamman kuin neljän alueen rajalla (pisteet (alueet) on yhdistetty reunalla, jos alueiden rajalla). Sitä vastoin mikä tahansa optimaalinen 1-tasograafi on 4-kartan graafi. Kuitenkin 1-tasokaaviot, jotka eivät ole optimaalisia 1-tasoisia, eivät välttämättä ole karttakaavioita [24] .
1-tasograafit yleistetään k -tasograafiksi , joissa jokainen reuna ylittää toiset reunat enintään k kertaa. Ringel määritteli graafin G paikallisen leikkausluvun pienimmäksi ei-negatiiviseksi k :ksi siten, että G :llä on k -tasopiirustus. Koska paikallinen leikkauspisteiden lukumäärä on yhtä suuri kuin optimaalisen kuvion reunojen leikkauskäyrän suurin aste , ja paksuutta (minimimäärä tasokaavioita, joihin reunat voidaan hajottaa) voidaan pitää kromaattisena lukumääränä . sopivan kuvion leikkauskäyrä, Brooksin lauseesta seuraa , että paksuus on enintään yhden suurempi kuin paikallinen leikkauspisteiden lukumäärä [25] . k -tasograafissa, jossa on n kärkeä, on enintään O ( k 1/2 n ) reunaa [26] ja puun leveys on O (( kn ) 1/2 ) [27] . K -tasograafin, jonka syvyys on d , matala molli on itse ( 2d + 1) k -tasoinen, joten 1-tasograafin ja k - tasograafin matalat alavärit ovat harvalukuisia , eli tässä 1-taso- ja k- tasokaavioilla on rajoitettu laajennus [28] .
Ei-tasoisille kuvaajille voit myös määrittää leikkauspisteiden lukumäärän parametrin , joka on leikkausreunojen vähimmäismäärä missä tahansa kaaviopiirroksessa. Kuvaaja, jossa on k leikkauskohtaa , on välttämättä k -tasoinen, mutta päinvastoin ei välttämättä pidä paikkaansa. Esimerkiksi Heawood Graphissa on 3 leikkauspistettä, mutta näiden leikkauspisteiden ei tarvitse olla yhden reunan kanssa, se on 1-tasoinen ja voidaan piirtää optimoimalla samanaikaisesti leikkauspisteiden kokonaismäärä ja leikkauspisteet yhtä reunaa kohti.
Toinen asiaan liittyvä käsite ei-tasoisille graafille on vino , minimimäärä reunoja, jotka täytyy poistaa, jotta graafista tulee tasomainen.