Ytterplanar graf - Outerplanar graph
I grafteori är en yttre plan graf en graf som har en plan ritning för vilken alla hörn hör till ritningens yttre yta.
Ytterplanära grafer kan karakteriseras (analogt med Wagners sats för plana grafer) av de två förbjudna minderåriga K 4 och K 2,3 , eller av deras Colin de Verdière -grafvarianter . De har Hamiltoniska cykler om och bara om de är sammankopplade, i vilket fall yttre ytan bildar den unika Hamiltonian cykeln. Varje outerplanar grafen är 3-PLAUSIBEL, och har degeneration och treewidth högst två.
De yttre plana graferna är en delmängd av de plana graferna , delgraferna för serie -parallella grafer och cirkeldiagrammen . De maximala yttre planära graferna , de till vilka inga fler kanter kan läggas till samtidigt som ytterplanariteten bevaras, är också ackordgrafer och synlighetsgrafer .
Historia
Ytterplanära grafer studerades och namngavs först av Chartrand & Harary (1967) , i samband med problemet med att bestämma planariteten hos grafer som bildas genom att använda en perfekt matchning för att ansluta två kopior av en basgraf (till exempel många av de generaliserade Petersen -graferna) bildas på detta sätt från två kopior av en cykeldiagram ). Som de visade, när basdiagrammet är dubbelkopplat , är en graf konstruerad på detta sätt plan om och endast om dess basdiagram är yttre plan och matchningen bildar en dihedral permutation av dess yttre cykel. Chartrand och Harary bevisade också en analog av Kuratowskis sats för yttre plana grafer, att en graf är yttre plan om och endast om den inte innehåller en underavdelning av en av de två graferna K 4 eller K 2,3 .
Definition och karakteriseringar
En yttre plan graf är en oriktad graf som kan ritas i planet utan korsningar på ett sådant sätt att alla hörn hör till ritningens obegränsade yta. Det vill säga att ingen hörn är helt omgiven av kanter. Alternativt är en graf G yttre plan om grafen som bildas från G genom att lägga till en ny toppunkt, med kanter som förbinder den med alla andra hörn, är en plan graf .
En maximal yttre plan graf är en yttre plan graf som inte kan ha några ytterligare kanter adderade till den samtidigt som den bevarar yttre planariteten. Varje maximal yttre plan graf med n hörn har exakt 2 n - 3 kanter, och varje avgränsad yta av en maximal yttre plan graf är en triangel.
Förbjudna grafer
Ytterplanära grafer har en förbjuden grafkarakterisering analog med Kuratowskis sats och Wagners sats för plana grafer: en graf är yttre plan om och endast om den inte innehåller en underavdelning av hela grafen K 4 eller den fullständiga tvåpartsdiagrammet K 2,3 . Alternativt är en graf yttre plan om och endast om den inte innehåller K 4 eller K 2,3 som en minor , en graf erhållen från den genom att radera och dra ihop kanter.
En triangelfri graf är yttre plan om och bara om den inte innehåller en underavdelning av K 2,3 .
Colin de Verdière invariant
En graf är yttre plan om och endast om dess Colin de Verdière -graf invariant är högst två. Graferna kännetecknas på ett liknande sätt av att ha Colin de Verdière invariant högst en, tre eller fyra är de linjära skogarna, plana graferna och länklöst inbäddbara grafer .
Egenskaper
Biconnectivity och Hamiltonicity
En yttre plan graf kopplas ihop om och bara om grafens yttre yta bildar en enkel cykel utan upprepade hörn. En yttre plan graf är Hamiltonian om och bara om den är dubbelkopplad; i detta fall bildar ytterytan den unika hamiltons cykel. Mer generellt är storleken på den längsta cykeln i en yttre plan graf detsamma som antalet hörn i dess största bikopplade komponent . Av denna anledning kan det vara att lösa Hamilton-cykler och längsta cykler i yttre planära grafer i linjär tid , till skillnad från NP-fullständigheten av dessa problem för godtyckliga grafer.
Varje maximal yttre plan graf uppfyller ett starkare tillstånd än Hamiltonicity: den är nodpykyklisk , vilket betyder att för varje hörn v och varje k i intervallet från tre till antalet hörn i grafen finns det en längd- k cykel som innehåller v . En cykel med denna längd kan hittas genom att upprepade gånger ta bort en triangel som är ansluten till resten av diagrammet med en enda kant, så att den borttagna hörnpunkten inte är v , förrän den yttre ytan på den återstående grafen har längden k .
En plan graf är yttre plan om och endast om var och en av dess bikopplade komponenter är yttre plan.
Färg
Alla loopless yttre plana grafer kan färgas med endast tre färger; detta faktum framträder framträdande i det förenklade beviset på Chvátals konstgallerisatsning av Fisk (1978) . En 3-färgning kan återfinnas i linjär tid av en girig färgande algoritm som avlägsnar varje vertex grad som mest två, färger den återstående grafen rekursivt, och lägger sedan tillbaka det avlägsnade vertex med en annan färg än färgerna på dess två grannar.
Enligt Vizinges sats är det kromatiska indexet för en graf (det minsta antalet färger som behövs för att färga dess kanter så att inga två intilliggande kanter har samma färg) antingen den maximala graden av grafens hörn eller en plus den maximala graden . I en ansluten yttre plan graf är dock det kromatiska indexet lika med den maximala graden utom när grafen bildar en cykel med udda längd. En kantfärgning med ett optimalt antal färger kan hittas i linjär tid baserat på den första bredden av det svaga dubbla trädet.
Övriga fastigheter
Ytterplanära grafer har degeneration högst två: varje delgraf av en yttre plan graf innehåller en toppunkt med högst två.
Outerplanar grafer har treewidth högst två, vilket innebär att många graf optimeringsproblem som är NP-komplett för godtyckliga grafer kan lösas i polynomisk tid av dynamisk programmering när ingången är outerplanar. Mer generellt har k -outerplanar -grafer trebredd O ( k ).
Varje yttre plan graf kan representeras som ett skärningsschema för axelinriktade rektanglar i planet, så yttre plana grafer har boxicity högst två.
Relaterade familjer av grafer
Varje yttre plan graf är ett plant diagram . Varje yttre plan graf är också en undergraf av en serie -parallell graf . Det är dock inte alla plana serier - parallella grafer som är yttre. Den kompletta bipartitdiagrammet K 2,3 är plan och serieparallell men inte yttre. Å andra sidan är den fullständiga grafen K 4 plan men varken serie -parallell eller yttre plan. Varje skog och varje kaktusgraf är yttre planar.
Den svaga plana dubbla grafen för en inbäddad yttre plan graf (grafen som har en hörnpunkt för varje avgränsad yta av inbäddningen och en kant för varje par av angränsande avgränsade ytor) är en skog, och den svaga plana dubbla av en Halin -graf är ett yttre plan diagram. En plan graf är yttre plan om och bara om dess svaga dual är en skog, och det är Halin om och bara om dess svaga dual är dubbelkopplad och yttre plan.
Det finns en uppfattning om yttre planaritet. En 1-yttre plan inbäddning av en graf är densamma som en yttre plan inbäddning. För k > 1 sägs en plan inbäddning vara k -outerplanar om borttagning av hörnen på ytterytan resulterar i en ( k -1) -planplanering. En graf är k -outerplanar om den har en k -outerplanar inbäddning.
Ett yttre-1-plan diagram , analogt med 1-plana diagram kan ritas i en skiva, med hörnen på skivans gräns och med högst en korsning per kant.
Varje maximal yttre planär graf är ett ackorddiagram . Varje maximal yttre plan graf är synlighetsgrafen för en enkel polygon . Maximala yttre plana grafer bildas också som graferna för polygontrianguleringar . De är exempel på 2-träd , på serie-parallella grafer och på ackordgrafer .
Varje yttre planärt diagram är ett cirkeldiagram , skärningsgrafen för en uppsättning ackord i en cirkel.
Anteckningar
Referenser
- Baker, Brenda S. (1994), "Approximation algoritms for NP-complete problems on planar graphs", Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID 9706753.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2004), "Problemet med yttre inbäddningar i pseudosurfaces", Ars Combinatoria , 71 : 79–91.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2004), "Objektuppsättningar för yttre bananer-ytdiagram", Ars Combinatoria , 73 : 65–77.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2006), "Otalbara grafer med alla sina hörn i ett ansikte", Acta Mathematica Hungarica , 112 (4): 307–313, doi : 10.1007/s10474-006-0082-0 , S2CID 123241658.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2010), "Yttre inbäddbarhet i vissa pseudosytor som härrör från tre sfärer", Diskret matematik , 310 (23): 3359–3367, doi : 10.1016/j.disc.2010.07.027.
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics , ISBN 0-89871-432-X.
- Chartrand, Gary ; Harary, Frank (1967), "Planar permutation graphs" , Annales de l'Institut Henri Poincaré B , 3 (4): 433–438, MR 0227041.
- Diestel, Reinhard (2000), Graph Theory , Graduate Texts in Mathematics , 173 , Springer-Verlag, sid. 107, ISBN 0-387-98976-5.
- El-Gindy, H. (1985), Hierarkisk sönderdelning av polygoner med applikationer , Ph.D. avhandling, McGill University. Som citerat av Brandstädt, Le & Spinrad (1999) .
- Felsner, Stefan (2004), Geometriska grafer och arrangemang: några kapitel från kombinationsgeometri , Vieweg+Teubner Verlag, sid. 6, ISBN 978-3-528-06972-8.
- Fiorini, Stanley (1975), "Om det kromatiska indexet för yttre planära grafer", Journal of Combinatorial Theory , Series B, 18 (1): 35–38, doi : 10.1016/0095-8956 (75) 90060-X.
- Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory , Series B, 24 (3): 374, doi : 10.1016/0095-8956 (78) 90059-X.
- Fleischner, Herbert J .; Geller, DP; Harary, Frank (1974), "Outerplanar grafer and weak duals", Journal of the Indian Mathematical Society , 38 : 215–219, MR 0389672.
- Kane, Vinay G .; Basu, Sanat K. (1976), "On the depth of a planar graph", Diskret matematik , 14 (1): 63–67, doi : 10.1016/0012-365X (76) 90006-6.
- Li, Ming-Chu; Corneil, Derek G .; Mendelsohn, Eric (2000), "Pancyklicitet och NP-fullständighet i plana grafer", Diskret tillämpad matematik , 98 (3): 219–225, doi : 10.1016/S0166-218X (99) 00163-8.
- Lick, Don R .; White, Arthur T. (1970), " k -genererade grafer" , Canadian Journal of Mathematics , 22 (5): 1082–1096, doi : 10.4153/CJM-1970-125-1.
- Lin, Yaw-Ling; Skiena, Steven S. (1995), "Komplexitetsaspekter av synlighetsgrafer", International Journal of Computational Geometry and Applications , 5 (3): 289–312, doi : 10.1142/S0218195995000179.
- Proskurowski, Andrzej; Sysło, Maciej M. (1986), "Effektiv topp-och kantfärgning av yttre plana grafer", SIAM Journal on Algebraic and Discrete Methods , 7 : 131–136, doi : 10.1137/0607016.
- Scheinerman, ER (1984), Intersection Classes and Multiple Intersection Parameters of a Graph , Ph.D. avhandling, Princeton University. Som citerat av Brandstädt, Le & Spinrad (1999) .
- Sysło, Maciej M. (1979), "Karakteriseringar av yttre plana grafer", Diskret matematik , 26 (1): 47–53, doi : 10.1016/0012-365X (79) 90060-8.
- Sysło, Maciej M .; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, 10–13 februari 1981 , Lecture Notes in Mathematics , 1018 , Springer-Verlag, s. 248–256, doi : 10.1007/BFb0071635.
- Unger, Walter (1988), "Om k -färgning av cirkeldiagram", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88) , Lecture Notes in Computer Science , 294 , Springer-Verlag, s. 61–72, doi : 10.1007/BFb0035832.
- Wessel, W .; Pöschel, R. (1985), "On circle graphs", i Sachs, Horst (red.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, 1st to 5th October, 1984 , Teubner-Texte zur Mathematik, 73 , BG Teubner, s. 207–210. Enligt Unger (1988) .