Graafiteoriassa ulompi tasograafi on graafi, joka sallii tasokaavion , jossa kaikki kärjet kuuluvat ulkopinnalle.
Ulommat tasograafit voidaan karakterisoida (samalla tavalla kuin Wagnerin tasograafien lause ) kahdella kielletyllä mollilla K 4 ja K 2,3 tai niiden Colin de Verdière -invariantilla . Näissä kaavioissa on Hamiltonin sykliä silloin ja vain, jos ne ovat kaksikytkentäisiä, jolloin ulkopinta muodostaa yhden Hamiltonin syklin. Mikä tahansa ulompi tasokaavio on 3-värinen, ja sen rappeuma ja puunleveys on enintään 2.
Ulompi tasokuvaajat ovat tasokaavioiden , rinnakkaisten sarjakaavioiden alikaavioiden ja ympyräkaavioiden osajoukkoa . Maksimaalinen ulkotasograafi on graafi, johon ei voida lisätä reunaa menettämättä ulkotasoisuutta. Ne ovat myös sointu- ja näkyvyyskaavioita .
Chartrand ja Harari [1] tutkivat ja nimesivät ensin ulkotason graafit, kun pohdittiin ongelmaa sellaisten graafien tasomaisuuden määrittämisessä, jotka on muodostettu käyttämällä täydellisiä vastaavuuksia , jotka yhdistävät kaksi perusgraafin kopiota (esimerkiksi monet yleistetyistä Petersen-graafista on muodostettu tällä tavalla kahdesta jaksokaavion kopiosta ) . Kuten he osoittivat, jos perusgraafi on kaksikytkentäinen , siitä kuvatulla tavalla saatu graafi on tasainen silloin ja vain, jos perusgraafi on ulompi ja sovitus muodostaa ulkosyklin dihedraalisia permutaatioita.
Ulompi tasograafi on suuntaamaton graafi , joka voidaan piirtää tasolle ilman leikkauspisteitä siten , että kaikki kärjet kuuluvat piirustuksen rajoittamattomalle ulkopinnalle. Eli yksikään kärki ei ole täysin reunojen ympäröimä. Vaihtoehtoisesti graafi G on ulompi taso, jos G : stä muodostettu graafi , joka on muodostettu lisäämällä uusi kärki, joka on yhdistetty kaikkiin muihin kärkipisteisiin, on tasomainen [2] .
Maksimaalinen ulkotasograafi on ulkotasograafi, johon ei voida lisätä reunaa loukkaamatta ulkotasoominaisuutta. Jokaisella maksimaalisella ulkotasograafilla, jossa on n kärkeä, on täsmälleen 2n − 3 reunaa, ja mikä tahansa maksimaalisen ulomman graafin rajattu pinta on kolmio.
Ulompitasoisille graafiille on ominaista kielletyt graafit , jotka ovat samanlaisia kuin Pontryagin-Kuratovsky-lause ja Wagnerin lause tasograafille - graafi on ulompi, jos ja vain, jos se ei sisällä kokonaisen graafin K 4 tai täydellisen kaksiosaisen graafin K 2 alajakoa , 3 [3] . Vaihtoehtoisesti graafi on ulompi, jos ja vain jos se ei sisällä K 4 tai K 2,3 sivuarvona , graafi saadaan poistamalla ja supistamalla reunoja [4] .
Kolmioton graafi on ulompi silloin ja vain, jos se ei sisällä osajakoja K 2,3 [5] .
Graafi on ulkotasoinen silloin ja vain, jos sen Colin de Verdière -invariantti ei ylitä kahta. Graafit, joille on tunnusomaista tällä tavalla Colin de Verdièren invariantin arvo (joka ei ylitä arvoa 1, 3 tai 4), ovat lineaarisia metsiä, tasokaavioita ja upotettavia kaavioita ilman linkkiä .
Ulompi tasograafi on kaksinkertainen , jos ja vain jos ulkopinta muodostaa yksinkertaisen syklin ilman toistuvia pisteitä. Ulompi tasograafi on Hamiltonin , jos ja vain jos se on kaksikytkentäinen. Tässä tapauksessa ulkopinta muodostaa ainutlaatuisen Hamiltonin syklin [1] [5] . Yleisemmin sanottuna ulkotason graafin pisimmän syklin koko on yhtä suuri kuin pisimmän kaksikytketyn komponentin pisteiden lukumäärä . Tästä syystä Hamiltonin syklien ja pisimpien syklien löytäminen ulompitasoisista graafisista voidaan tehdä lineaarisessa ajassa , toisin kuin näiden ongelmien NP-täydellisyys mielivaltaisille graafille.
Mikä tahansa maksimaalinen ulompi tasograafi täyttää vahvemman ehdon kuin Hamiltonin graafi - se on vertex-pancyclic , mikä tarkoittaa, että millä tahansa kärjellä v ja mille tahansa luvulle k kolmen ja graafin kärkien lukumäärän välillä on sykli, jonka pituus on k , joka sisältää v . Tämän pituinen sykli voidaan löytää poistamalla peräkkäin kolmio, joka on yhdistetty graafin loppuosaan yhdellä reunalla siten, että poistettava kärki ei ole yhtäpitävä v :n kanssa , ennen kuin jäljellä olevan graafin ulkopinnan pituus on k . [6] .
Tasograafi on ulompi silloin ja vain, jos kaikki sen kaksinkertaisesti kytketyt komponentit ovat ulkotasoisia [5] .
Kaikki ulkotason graafit ilman silmukoita voidaan värjätä vain kolmella värillä [7] . Tämä seikka näkyy selvästi Chvatala Fiscomin yksinkertaistetussa todistuksessa taidegallerialauseesta [ 8] . Kolmen värin väritys voidaan löytää lineaarisessa ajassa ahneella väritysalgoritmilla , joka poistaa minkä tahansa kärjen, jonka aste on korkeintaan kaksi ja värittää jäljellä olevan graafin rekursiivisesti ja palauttaa sitten kunkin poistetun kärjen värillä, joka eroaa sen kahden väristä. naapurit.
Vizingin lauseen mukaan minkä tahansa graafin kromaattinen indeksi (minimimäärä värejä, jotka tarvitaan graafin reunojen värjäämiseen siten, että kahdella vierekkäisellä reunalla ei ole samaa väriä) on joko yhtä suuri kuin graafin kärkien maksimiaste, tai yksi enemmän kuin enimmäisaste. Ulompitasoisten graafien kromaattinen indeksi on yhtä suuri kuin maksimiteho, ellei kuvaaja ole parittoman pituinen sykli [9] . Reunavärjäys optimaalisella määrällä värejä voidaan löytää lineaarisessa ajassa heikon kaksoispuun leveyshaun perusteella [7] .
Ulompitasoisten graafien degeneraatio on korkeintaan 2 — mikä tahansa ulkotason graafin aligraafi sisältää kärjen, jonka aste on enintään 2 [10] .
Ulompitasoisten graafien puuleveys on korkeintaan 2, mikä tarkoittaa, että monet optimointiongelmat kaavioissa, jotka ovat NP-täydellisiä yleisille kuvaajille, voidaan ratkaista polynomiajassa käyttämällä dynaamista ohjelmointia , jos syöte on ulkotason graafi. Yleisemmin k -ulompitasograafilla on puunleveys O( k ) [11] .
Mikä tahansa ulompi tasokuvaaja voidaan esittää suorakulmioiden leikkauskuvaajana, jonka sivut ovat samansuuntaiset akselien kanssa, jolloin ulompitasoisten graafien intervallimitta [12] [13] on enintään kaksi [14] [15] .
Mikä tahansa ulkotason kuvaaja on tasomainen . Mikä tahansa ulompi tasograafi on rinnakkaissarjakuvaajan aligraafi [16] . Kaikki rinnakkaiset peräkkäiset kuvaajat eivät kuitenkaan ole ulompia. Täydellinen kaksiosainen graafi K 2,3 on tasomainen ja rinnakkainen sarja, mutta ei ulkotasoinen. Toisaalta koko graafi K 4 on tasomainen, mutta ei yhdensuuntainen peräkkäinen eikä ulkotasoinen. Mikä tahansa metsä ja mikä tahansa kaktus on tasojen ulkopuolella [17] .
Upotetun ulomman graafin heikosti duaalitasograafi (kuvaaja, jolla on kärki kullekin sisäkkäisen rajan pinnalle ja reuna vierekkäisille rajatuille pinnoille) on metsä, ja Halin- graafin heikosti duaalitasograafi on ulompi tasograafi. . Tasograafi on ulompi silloin ja vain, jos sen heikko duaali on metsä, ja graafi on Halin-graafi silloin ja vain, jos sen heikko duaali on kaksinkertaisesti kytketty ja ulompi [18] .
Ulkoisen tasomaisuuden asteen käsite on olemassa. Kuvaajan 1-ulompitasoinen upottaminen on sama kuin ulkotasoinen upotus. Kun k > 1, tasomaisen upotuksen sanotaan olevan k -ulkotasoinen , jos kärjen poistaminen ulkopinnasta johtaa ( k − 1)-ulompitasoiseen upotukseen. Graafi on k -ulompitasoinen silloin ja vain, jos siinä on k -ulompitasoinen upotus [19] [5] .
Mikä tahansa maksimaalinen ulkotasograafi on sointukaavio . Mikä tahansa maksimaalinen ulkotasograafi on yksinkertainen monikulmion näkyvyysgraafi [20] . Maksimaaliset ulkotason graafit muodostetaan monikulmiokolmiograafina . Ne ovat myös esimerkkejä 2-puusta , rinnakkaissekvenssikaavioista ja sointukaavioista .
Mikä tahansa ulkotasograafi on ympyräkuvaaja , ympyrän jännejoukon leikkauskuvaaja [21] [22] .