În teoria grafurilor, un graf exterior planar este un graf care admite o diagramă plană în care toate vârfurile aparțin feței exterioare.
Graficele plane exterioare pot fi caracterizate (în mod similar teoremei lui Wagner pentru graficele plane) prin două minore interzise K 4 și K 2,3 , sau invarianții lor Colin de Verdière . Aceste grafice au cicluri hamiltoniene dacă și numai dacă sunt biconectate, caz în care fața exterioară formează un singur ciclu hamiltonian. Orice grafic exterior planar are 3 culori și are degenerescență și lățime de arbore de cel mult 2.
Graficele outerplanare sunt un subset de grafice plane , subgrafe ale graficelor paralele-seriale și grafice circulare . Un grafic maxim exterior planar este un grafic la care nu se poate adăuga o muchie fără a pierde planaritatea exterioară. Sunt, de asemenea , grafice de acorduri și de vizibilitate .
Graficele outerplanare au fost studiate și denumite pentru prima dată de Chartrand și Harari [1] atunci când s-a luat în considerare problema determinării planarității graficelor formate folosind potriviri perfecte care conectează două copii ale graficului de bază (de exemplu, multe dintre graficele Petersen generalizate sunt formate în acest fel ). din două copii ale graficului ciclului ). După cum au arătat, dacă graficul de bază este biconectat , graficul obținut din acesta în modul descris este plan dacă și numai dacă graficul de bază este exterior plan și potrivirea formează permutări diedrice ale ciclului exterior.
Un graf exterior planar este un graf nedirecționat care poate fi desenat pe un plan fără intersecții astfel încât toate vârfurile să aparțină feței exterioare nemărginite a desenului. Adică, niciunul dintre vârfuri nu este complet înconjurat de muchii. Alternativ, un grafic G este exterior planar dacă graficul format din G prin adăugarea unui nou vârf conectat prin muchii la toate celelalte vârfuri este planar [2] .
Un graf maxim exterior planar este un graf exterior planar la care nu poate fi adăugată nicio muchie fără a încălca proprietatea de planaritate exterioară. Orice graf maxim exterior planar cu n vârfuri are exact 2n - 3 muchii, iar orice față mărginită a unui graf maxim exterior planar este un triunghi.
Graficele outerplanare au o caracterizare prin grafice interzise similare teoremei Pontryagin-Kuratovsky și teoremei lui Wagner pentru graficele plane - un grafic este exterior planar dacă și numai dacă nu conține o subdiviziune a unui grafic complet K 4 sau a unui grafic bipartit complet K 2, 3 [3] . Alternativ, un grafic este exterior planar dacă și numai dacă nu conține K 4 sau K 2,3 ca minor , graficul obținut prin îndepărtarea și contractarea muchiilor [4] .
Un grafic fără triunghi este exterior plan dacă și numai dacă nu conține subdiviziuni K 2,3 [5] .
Un grafic este plan exterior dacă și numai dacă invariantul lui Colin de Verdière nu depășește doi. Graficele caracterizate în acest fel prin valoarea invariantului Colin de Verdière (care nu depășește valoarea 1, 3 sau 4) sunt păduri liniare, grafice plane și grafice încorporabile fără legătură .
Un graf exterior planar este dublu conectat dacă și numai dacă fața exterioară formează un ciclu simplu fără vârfuri repetate. Un graf exterior planar este hamiltonian dacă și numai dacă este biconectat. În acest caz, fața exterioară formează un ciclu Hamiltonian unic [1] [5] . Mai general, dimensiunea celui mai lung ciclu dintr-un grafic exterior planar este egală cu numărul de vârfuri din cea mai lungă componentă biconectată . Din acest motiv, găsirea ciclurilor hamiltoniene și a celor mai lungi cicluri în graficele planare exterioare se poate face în timp liniar , spre deosebire de completitudinea NP a acestor probleme pentru graficele arbitrare.
Orice graf maxim exterior planar satisface o condiție mai puternică decât a fi hamiltonian - este un vârf-panciclic , ceea ce înseamnă că pentru orice vârf v și orice număr k între trei și numărul de vârfuri din grafic, există un ciclu de lungime k care conține v . Un ciclu de această lungime poate fi găsit prin îndepărtarea succesivă a unui triunghi legat de restul graficului printr-o singură muchie, astfel încât vârful de îndepărtat să nu coincidă cu v , până când fața exterioară a graficului rămas are lungimea k [6] .
Un graf plan este exterior planar dacă și numai dacă toate componentele sale dublu conectate sunt outerplanare [5] .
Toate graficele planare exterioare fără bucle pot fi colorate cu doar trei culori [7] . Acest fapt apare în mod proeminent într-o demonstrație simplificată a teoremei galeriei de artă de Chvatala Fiscom [ 8] . O colorare cu trei culori poate fi găsită în timp liniar printr-un algoritm de colorare lacom care elimină orice vârf cu gradul de cel mult doi și colorează graficul rămas în mod recursiv, iar apoi returnează fiecare dintre vârfurile eliminate cu o culoare diferită de culorile celor două. vecini.
Conform teoremei lui Vizing , indicele cromatic al oricărui grafic (numărul minim de culori necesare pentru a colora marginile graficului, astfel încât două margini adiacente să nu aibă aceeași culoare) este fie egal cu gradul maxim al vârfurilor graficului, sau cu unul mai mult decât gradul maxim. Pentru graficele planare exterioare, indicele cromatic este egal cu puterea maximă, cu excepția cazului în care graficul este un ciclu de lungime impară [9] . O colorare a marginilor cu numărul optim de culori poate fi găsită în timp liniar pe baza unei căutări pe lățimea întâi a unui arbore dual slab [7] .
Graficele outerplanare au degenerare de cel mult 2 — orice subgraf al unui graf exteriorul planar conține un vârf cu gradul de cel mult 2 [10] .
Graficele outerplanare au lățimea arborelui de cel mult 2, ceea ce implică faptul că multe probleme de optimizare pe grafice care sunt NP-complete pentru graficele generale pot fi rezolvate în timp polinomial folosind programarea dinamică dacă intrarea este un grafic exterior planar. Mai general, un graf k -exterior are lățimea arborelui O( k ) [11] .
Orice grafic exterior planar poate fi reprezentat ca un grafic de intersecție de dreptunghiuri cu laturile paralele cu axele, astfel încât graficele exterioare planare să aibă o dimensiune a intervalului [12] [13] de cel mult două [14] [15] .
Orice graf exterior planar este planar . Orice graf exterior planar este un subgraf al unui graf paralel-serial [16] . Cu toate acestea, nu toate graficele paralele-secvențiale sunt planare. Graficul bipartit complet K 2,3 este plan și paralel-serial, dar nu exterior. Pe de altă parte, graficul complet K 4 este plan, dar nici paralel-secvențial, nici exterior plan. Orice pădure și orice cactus sunt supraplanare [17] .
Graficul planar slab dual al unui grafic exterior planar încorporat (un grafic care are un vârf pentru fiecare față mărginită a cuibării și o muchie pentru fețele delimitate adiacente) este o pădure, iar graficul planar slab dual al graficului Halin este un grafic exterior planar. . Un graf planar este exterior planar dacă și numai dacă dualul său slab este o pădure, iar graficul este un graf Halin dacă și numai dacă dualul său slab este dublu conex și exterior [18] .
Există un concept al gradului de planaritate externă. O încorporare 1-exterioară a unui grafic este aceeași cu o încorporare exterioară. Pentru k > 1, se spune că o încorporare plană este k -exterioară dacă îndepărtarea unui vârf de pe fața exterioară are ca rezultat o înglobare ( k - 1) -exterioară. Un grafic este k -exterior planar dacă și numai dacă are o încorporare k -exteriorplanar [19] [5] .
Orice graf maxim exterior planar este un graf cordal . Orice grafic maxim exterior planar este un simplu grafic de vizibilitate poligon [20] . Graficele maxime exterioare sunt formate ca grafice de triangulație poligonală . Ele sunt, de asemenea, exemple de 2 arbori , grafice cu secvențe paralele și grafice cu acorduri .
Orice grafic exterior planar este un grafic circular , graficul de intersecție al mulțimii de coarde ale cercului [21] [22] .