Plan graf - Planar graph

Exempel på grafer
Planar	Icke -plan
Fjäril graf	Komplett graf K ₅
Komplett graf K ₄	Verktygsgraf K _3,3

Inom grafteori är en plan graf en graf som kan vara inbäddad i planet , dvs den kan ritas på planet på ett sådant sätt att dess kanter skär varandra endast vid deras slutpunkter. Med andra ord kan den ritas på ett sådant sätt att inga kanter korsar varandra. En sådan ritning kallas en plan graf eller plan inbäddning av grafen . Ett plandiagram kan definieras som ett plant diagram med en kartläggning från varje nod till en punkt på ett plan och från varje kant till en plankurva på det planet, så att de extrema punkterna för varje kurva är de punkter som mappas från dess ände noder, och alla kurvor är osammanhängande utom på deras extrema punkter.

Varje graf som kan ritas på ett plan kan också ritas på sfären , och vice versa, med hjälp av stereografisk projektion .

Plangrafer kan kodas av kombinatoriska kartor eller rotationssystem .

En ekvivalensklass av topologiskt ekvivalenta ritningar på sfären, vanligtvis med ytterligare antaganden som frånvaro av isthmus , kallas en plan karta . Även om ett plandiagram har en yttre eller obegränsad yta , har ingen av ansiktena på en plan karta en särskild status.

Plana grafer generaliserar till grafer som kan ritas på en yta av ett visst släkte . I denna terminologi har plana grafer genus 0, eftersom planet (och sfären) är ytor av släkt 0. Se " grafinbäddning " för andra relaterade ämnen.

Kuratowskis och Wagners satser

Bevis utan ord om att tesseract-grafen är icke-plan med hjälp av Kuratowskis eller Wagners satser och att hitta antingen K ₅ (överst) eller K _3,3 (nedre) undergrafer

Den polska matematikern Kazimierz Kuratowski gav en karakterisering av plana grafer när det gäller förbjudna grafer , nu känd som Kuratowskis sats :

En ändlig graf är plan om och endast om den inte innehåller en undergraf som är en underavdelning av hela grafen K ₅ eller den fullständiga tvåpartsdiagrammet ( verktygsgraf ).

{\ displaystyle K_ {3,3}}

En indelning av en graf resulterar i att du sätter in hörn i kanterna (till exempel ändrar en kant • —— • till • - • - •) noll eller fler gånger.

Ett exempel på en graf utan K ₅ eller K _3,3 undergraf. Den innehåller dock en underavdelning av K _3,3 och är därför icke plan.

Istället för att överväga underavdelningar behandlar Wagners teorem minderåriga :

En ändlig graf är plan om och bara om den inte har eller som en minor .

{\ displaystyle K_ {5}}

{\ displaystyle K_ {3,3}}

En mindre del av en graf är resultatet av att ta en subgraf och upprepade gånger dra ihop en kant i en hörn, varvid varje granne till de ursprungliga ändpunktarna blir granne till den nya hörnpunkten.

En animering som visar att Petersen-grafen innehåller en mindre isomorf i förhållande till K _3,3- grafen och därför är icke-plan

Klaus Wagner frågade mer allmänt om någon mindre stängd grafklass bestäms av en begränsad uppsättning " förbjudna minderåriga ". Detta är nu Robertson – Seymour -satsen , bevisad i en lång serie papper. På språket i denna sats, och är de förbjudna minderåriga för klassen av ändliga plana grafer. ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {3,3}}$

Andra planitetskriterier

I praktiken är det svårt att använda Kuratowskis kriterium för att snabbt avgöra om en given graf är plan. Det finns dock snabba algoritmer för detta problem: för en graf med n hörn är det möjligt att i tid O ( n ) (linjär tid) avgöra om grafen kan vara plan eller inte (se planaritetstestning ).

För en enkel, ansluten, plan graf med v -hörn och e -kanter och f -ytor gäller följande enkla villkor för v ≥ 3:

Sats 1. e ≤ 3 v - 6;
Sats 2. Om det inte finns några cykler med längd 3, då e ≤ 2 v - 4.
Sats 3. f ≤ 2 v - 4.

I denna mening är plana grafer glesa grafer , eftersom de bara har O ( v ) kanter, asymptotiskt mindre än max O ( v ² ). Diagrammet K _3,3 har till exempel 6 hörn, 9 kanter och inga cykler med längd 3. Därför kan det med sats 2 inte vara plant. Dessa satser ger nödvändiga förutsättningar för planaritet som inte är tillräckliga villkor, och därför bara kan användas för att bevisa att en graf inte är plan, inte att den är plan. Om både sats 1 och 2 misslyckas kan andra metoder användas.

Whitneys planaritetskriterium ger en karakterisering baserad på förekomsten av en algebraisk dual;
Mac Lanes planaritetskriterium ger en algebraisk karakterisering av ändliga plana grafer, via deras cykelutrymmen ;
Den Fraysseix-Rosenstiehl plan kriterium ger en karakterisering baserad på förekomsten av en bidelning av cotree kanterna på en djup första sökträd. Det är centralt för vänster-höger planaritetstestalgoritm ;
Schnyders sats ger en karakterisering av planaritet i form av partiell ordningsdimension ;
Colin de Verdières planaritetskriterium ger en karakterisering baserad på den maximala mångfalden av det andra egenvärdet för vissa Schrödinger -operatörer som definieras av grafen.
Den Hanani-tutte teoremet säger att en graf är plan om och endast om den har en ritning, i vilken varje oberoende par kanter korsar ett jämnt antal gånger; den kan användas för att karakterisera de plana graferna via ett ekvationssystem modulo 2.

Eulers formel

Eulers formel säger att om en ändlig, ansluten , plan graf ritas i planet utan några kantkorsningar, och v är antalet hörn, e är antalet kanter och f är antalet ytor (områden begränsade av kanter, inklusive den yttre, oändligt stora regionen), då

{\ displaystyle v-e+f = 2.}

Som en illustration, i fjärilsdiagrammet ovan, v = 5, e = 6 och f = 3. Om egenskapen i allmänhet gäller för alla plana diagram över f -ansikten, ändras grafen som skapar ett extra ansikte samtidigt som diagramplanet skulle hålla v - e + f en invariant. Eftersom egenskapen gäller för alla grafer med f = 2, gäller den genom matematisk induktion för alla fall. Eulers formel kan också bevisas enligt följande: om diagrammet inte är ett träd , ta sedan bort en kant som slutför en cykel . Detta sänker både e och f med en och lämnar v - e + f konstant. Upprepa tills den återstående grafen är ett träd; träd har v = e + 1 och f = 1, vilket ger v - e + f = 2, dvs Euler -karakteristiken är 2.

I en ändlig, ansluten , enkel , plan graf är varje yta (utom möjligen den yttre) begränsad av minst tre kanter och varje kant vidrör högst två ytor; med hjälp av Eulers formel kan man sedan visa att dessa grafer är glesa i den meningen att om v ≥ 3:

{\ displaystyle e \ leq 3v-6.}

Ett Schlegel -diagram över en vanlig dodekaeder , som bildar en plan graf från en konvex polyeder.

Eulers formel är också giltig för konvexa polyeder . Detta är ingen slump: varje konvex polyhedron kan förvandlas till en ansluten, enkel, plan graf med hjälp av Schlegel -diagrammet över polyhedronen, en perspektivprojektion av polyhedronen till ett plan med perspektivets centrum vald nära mitten av en av polyhedrons ansikten. Inte varje plant diagram motsvarar en konvex polyhedron på detta sätt: det gör inte träden till exempel. Steinitz sats säger att de polyhedrala graferna som bildas av konvexa polyeder är just de ändliga 3-anslutna enkla plana graferna. Mer allmänt gäller Eulers formel för alla polyeder vars ytor är enkla polygoner som bildar en yta topologiskt ekvivalent med en sfär, oavsett dess konvexitet.

Genomsnittlig examen

Anslutna plana grafer med mer än en kant lyder ojämlikheten , eftersom varje sida har minst tre framkantskanter och varje kant bidrar med exakt två incidenter. Det följer via algebraiska transformationer av denna ojämlikhet med Eulers formel att för ändliga plana grafer är medelgraden strikt mindre än 6. Grafer med högre genomsnittlig grad kan inte vara plana. ${\ displaystyle 2e \ geq 3f}$ ${\ displaystyle v-e+f = 2}$

Myntgrafer

Exempel på cirkelpackningssatsen på K ^-₅ , hela grafen på fem hörn, minus en kant.

Vi säger att två cirklar ritade i en plan kyss (eller osculerar ) när de skär varandra i exakt en punkt. En "myntgraf" är en graf som bildas av en uppsättning cirklar, av vilka inga två har överlappande interiörer, genom att göra en toppunkt för varje cirkel och en kant för varje cirkelpar som kysser. Den cirkel packning teorem , först bevisas av Paul Koebe 1936, uppger att en graf är plan om och endast om det är ett mynt grafen.

Detta resultat ger ett enkelt bevis på Fárys sats , att varje enkelt plant diagram kan bäddas in i planet på ett sådant sätt att dess kanter är raka linjesegment som inte korsar varandra. Om man placerar varje toppunkt i grafen i mitten av motsvarande cirkel i en myntdiagramrepresentation, så korsar linjesegmenten mellan kyssande cirkels centrum inte någon av de andra kanterna.

Plan graftäthet

Tätheten hos en plan graf, eller nätverk, definieras som ett förhållande mellan antalet kanter och antalet möjliga kanter i ett nätverk med noder, givet av en plan graf , vilket ger . En helt gles plan graf har , alternativt en helt tät plan graf har ${\ displaystyle D}$ ${\ displaystyle E}$ ${\ displaystyle N}$ ${\ displaystyle (E _ {\ max} = 3N-6)}$ ${\ displaystyle D = {\ frac {E-N+1} {2N-5}}}$ ${\ displaystyle D = 0}$ ${\ displaystyle D = 1}$

Relaterade familjer av grafer

Maximala plana grafer

Den Goldner-Harary graf är maximal plana. Alla dess ytor är avgränsade av tre kanter.

En enkel graf kallas maximal plan om den är plan men att lägga till någon kant (på den givna hörnuppsättningen) skulle förstöra den egenskapen. Alla ytor (inklusive den yttre) begränsas sedan av tre kanter, vilket förklarar den alternativa termen plan triangulering . De alternativa namnen "triangulär graf" eller "triangulerad graf" har också använts, men är tvetydiga, eftersom de vanligare hänvisar till linjediagrammet för ett komplett diagram respektive till ackordgraferna . Varje maximal plan graf är minst 3-ansluten.

Om en maximal plan graf har v hörn med v > 2, så har den exakt 3 v - 6 kanter och 2 v - 4 sidor.

Apollonska nätverk är de maximala plana graferna som bildas genom att triangulära ytor upprepade gånger delas upp i tripplar av mindre trianglar. På motsvarande sätt är de de plana 3-träden .

Strangulerade grafer är graferna där varje perifer cykel är en triangel. I en maximal plan graf (eller mer allmänt en polyhedral graf) är de perifera cyklerna ytorna, så maximala plana grafer stryps. De strypade graferna inkluderar också ackordgraferna och är exakt de grafer som kan bildas av klicksummor (utan att ta bort kanter) av kompletta grafer och maximala plana grafer.

Ytterplanära grafer

Ytterplanära grafer är grafer med en inbäddning i planet så att alla hörn hör till inbäddningens obegränsade yta. Varje yttre plan graf är plan, men det motsatta är inte sant: K ₄ är plan men inte yttre plan. Ett teorem som liknar Kuratowskis säger att en ändlig graf är yttre plan om och bara om den inte innehåller en underavdelning av K ₄ eller K _2,3 . Ovanstående är en direkt följd av det faktum att en graf G är 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 1-yttre plan inbäddning av en graf är densamma som en yttre plan inbäddning. För k > 1 är en plan inbäddning 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.

Halin -grafer

En Halin-graf är en graf som bildas från ett oriktat platanträd (utan grad-två noder) genom att ansluta dess löv till en cykel, i den ordning som ges av planets inbäddning av trädet. På motsvarande sätt är det en polyhedral graf där ena sidan ligger intill alla andra. Varje Halin -graf är plan. Liksom yttre plana grafer har Halin -grafer låg trädbredd , vilket gör att många algoritmiska problem på dem lättare löses än i obegränsade plana grafer.

Andra närstående familjer

Ett spetsdiagram är ett diagram som kan göras plant genom att en toppunkt tas bort, och ett k -apex -diagram är ett diagram som kan göras plant genom att ta bort högst k hörn.

En 1 -plan graf är en graf som kan ritas i planet med högst en enkel korsning per kant, och en k -plan graf är en graf som kan ritas med högst k enkla korsningar per kant.

En kartgraf är en graf som bildas av en uppsättning av oändligt många enkelt anslutna inre-osammanhängande områden i planet genom att ansluta två regioner när de delar minst en gränspunkt. När högst tre regioner möts vid en punkt är resultatet ett plant diagram, men när fyra eller flera regioner möts vid en punkt kan resultatet bli icke -plan.

En toroidal graf är en graf som kan bäddas in utan korsningar på torus . Mer generellt är släktet för en graf det minsta släktet för en tvådimensionell yta i vilken grafen kan vara inbäddad; plana grafer har släktet noll och icke -plana toroidala grafer har ett släkt.

Vilken graf som helst kan vara inbäddad i tredimensionellt utrymme utan korsningar. Emellertid tillhandahålls en tredimensionell analog av de plana graferna av de länklöst inbäddbara graferna , grafer som kan inbäddas i tredimensionellt utrymme på ett sådant sätt att inga två cykler är topologiskt kopplade till varandra. I analogi med Kuratowskis och Wagners karaktäriseringar av de plana graferna som de grafer som inte innehåller K ₅ eller K _3,3 som en minor, kan de länklöst inbäddbara graferna karakteriseras som de grafer som inte innehåller som minor någon av sju grafer i Petersen -familjen . I analogi med karaktäriseringarna av de yttre planära och plana graferna som graferna med Colin de Verdière -grafen invariant högst två eller tre, är de länklöst inbäddbara graferna graferna som har Colin de Verdière invariant som högst fyra.

En plan plan uppåt är en riktad acyklisk graf som kan ritas i planet med dess kanter som icke-korsande kurvor som är konsekvent orienterade i en uppåtgående riktning. Inte varje planriktad acyklisk graf är plan uppåt, och det är NP-komplett för att testa om en given graf är plan uppåt.

Uppräkning av plana grafer

Den asymptotiska för antalet (märkta) plana grafer på vertex är , där och . ${\ displaystyle n}$ ${\ displaystyle g \ cdot n ^{-7/2} \ cdot \ gamma ^{n} \ cdot n!}$ ${\ displaystyle \ gamma \ approx 27.22687}$ ${\ displaystyle g \ ca 0,43 \ gånger 10^{-5}}$

Nästan alla plana grafer har ett exponentiellt antal automorfismer.

Antalet omärkta (icke-isomorfa) plana grafer på hörn är mellan och . ${\ displaystyle n}$ ${\ displaystyle 27.2^{n}}$ ${\ displaystyle 30.06^{n}}$

Andra fakta och definitioner

Satsen med fyra färger anger att varje plant diagram är 4- färgbart (dvs 4-partit).

Fárys sats säger att varje enkel plan graf medger en inbäddning i planet så att alla kanter är raka linjesegment som inte skär varandra. En universell punktuppsättning är en uppsättning punkter så att varje plant diagram med n hörn har en sådan inbäddning med alla hörn i punktuppsättningen; det finns universella punktuppsättningar av kvadratisk storlek, bildade genom att ta en rektangulär delmängd av heltalet . Varje enkel yttre planär graf tillåter en inbäddning i planet så att alla hörn ligger på en fast cirkel och alla kanter är raka linjesegment som ligger inuti skivan och inte skär varandra, så n -vertex regelbundna polygoner är universella för yttre plana grafer.

En plan graf och dess dubbla

Med tanke på en inbäddning G av en (inte nödvändigtvis enkel) ansluten graf i planet utan kantkorsningar konstruerar vi den dubbla grafen G * enligt följande: vi väljer en toppunkt i varje yta på G (inklusive ytterytan) och för varje kant e i G introducerar vi en ny kant i G * som förbinder de två hörnen i G * motsvarande de två ytorna i G som möts vid e . Vidare ritas denna kant så att den korsar e exakt en gång och att ingen annan kant av G eller G * skärs. Då är G * återigen inbäddningen av ett (inte nödvändigtvis enkelt) plant diagram; den har lika många kanter som G , lika många hörn som G har ansikten och lika många ansikten som G har hörn. Termen "dubbel" motiveras av att G ** = G ; här är likvärdigheten ekvivalensen av inbäddningar på sfären . Om G är det plana diagrammet som motsvarar en konvex polyhedron, då är G * det plana diagrammet som motsvarar den dubbla polyhedronen.

Dubblar är användbara eftersom många egenskaper hos det dubbla diagrammet på enkla sätt är relaterade till egenskaperna hos det ursprungliga diagrammet, vilket gör det möjligt att bevisa resultat om grafer genom att undersöka deras dubbla grafer.

Medan det dubbla konstruerade för en viss inbäddning är unikt (upp till isomorfism ), kan grafer ha olika (dvs icke-isomorfa) dualer, erhållna från olika (dvs. icke- homomorfa ) inbäddningar.

En euklidisk graf är en graf där hörnen representerar punkter i planet, och kanterna tilldelas längder lika med det euklidiska avståndet mellan dessa punkter; se Geometrisk grafteori .

En plan graf sägs vara konvex om alla dess ytor (inklusive den yttre ytan) är konvexa polygoner . Ett plant diagram kan ritas konvext om och bara om det är en underavdelning av ett 3-vertex-anslutet plant diagram.

Scheinermans gissningar (nu ett teorem) säger att varje plant diagram kan representeras som ett skärningsschema för linjesegment i planet.

De plana separator theorem påstår att varje n -vertex planär graf kan delas upp i två subgrafer av storlek som mest 2 n / 3 genom avlägsnande av O ( √ n ) vertex. Som en konsekvens har plana grafer också trädbredd och grenbredd O ( √ n ).

Den plana produktstruktursatsen säger att varje plant diagram är en subgraf av den starka grafprodukten från en graf av trädbredd högst 8 och en väg. Detta resultat har använts för att visa att plana grafer har begränsat könummer , begränsat icke-repetitivt kromatiskt tal och universella grafer med nära linjär storlek. Den har också applikationer för toppunktsrankning och p -centrerad färgning av plana grafer.

För två plana grafer med v hörn är det möjligt att i tid O ( v ) avgöra om de är isomorfa eller inte (se även graf isomorfismproblem ).

Den meshedness Koefficienten av en plan kurva normaliserar dess antal avgränsas ytor (samma som kretsen rang av grafen, genom Mac Lanes planhet kriterium ) genom att dividera den med 2 n - 5, det maximalt möjliga antalet avgränsas ansikten i en plan kurva med n hörn. Således varierar det från 0 för träd till 1 för maximala plana grafer.

Ordrepresenterbara plana grafer inkluderar triangelfria plana grafer och, mer allmänt, trefärgbara plana grafer, liksom vissa ansiktsindelningar av triangulära rutdiagram och vissa trianguleringar av rutnätscylindrade grafer.

Se även

Kombinerande karta ett kombinatoriskt objekt som kan koda plangrafer
Planarisering , en plan graf bildad av en ritning med korsningar genom att ersätta varje korsningspunkt med en ny toppunkt
Tjocklek (grafteori) , det minsta antalet plana grafer som kanterna på en given graf kan delas in i
Planaritet , ett pussel dataspel där målet är att bädda in en plan graf på ett plan
Groddar (spel) , ett penna-och-papper-spel där en plan graf som är föremål för vissa begränsningar konstrueras som en del av spelet
Problem med tre verktyg , ett populärt pussel

Anteckningar

^ Trudeau, Richard J. (1993). Introduktion till grafteori (korrigerad, förstorad republik. Red.). New York: Dover Pub. sid. 64. ISBN 978-0-486-67870-2. Hämtad 8 augusti 2012 . Således har ett plant diagram, när det ritas på en plan yta, antingen inga kantkorsningar eller kan ritas om utan dem.
^ Barthelemy, M. (2017). Morfogenes av rumsliga nätverk . New York: Springer. sid. 6.
^ Schnyder, W. (1989), "Planar grafer and poset dimension", Order , 5 (4): 323–343, doi : 10.1007/BF00353652 , MR 1010382 , S2CID 122785359.
^ Bhasker, Jayaram; Sahni, Sartaj (1988), "A linjär algoritm för att hitta en rektangulär dubbel av en plan Triangulated graf", Algorithmica , 3 (1-4): 247-278, doi : 10,1007 / BF01762117 , S2CID 2.709.057.
^ Seymour, PD; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR 0742878.
^ Felsner, Stefan (2004), "1.4 Outerplanar Graphs and Convex Geometric Graphs", Geometriska grafer och arrangemang , Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, s. 6–7, doi : 10.1007/978-3-322-80303-0_1 , ISBN 3-528-06972-4, MR 2061507
^ 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.
^ Giménez, Omer; Noy, Marc (2009). "Asymptotisk uppräkning och gränslagar för plana grafer". Journal of the American Mathematical Society . 22 (2): 309–329. arXiv : matematik/0501269 . Bibcode : 2009JAMS ... 22..309G . doi : 10.1090/s0894-0347-08-00624-3 . S2CID 3353537 .
^ McDiarmid, Colin; Steger, Angelika ; Welsh, Dominic JA (2005). "Slumpmässiga plana grafer". Journal of Combinatorial Theory, Serie B . 93 (2): 187–205. CiteSeerX 10.1.1.572.857 . doi : 10.1016/j.jctb.2004.09.007 .
^ Bonichon, N .; Gavoille, C .; Hanusse, N .; Poulalhon, D .; Schaeffer, G. (2006). "Plana grafer, via välordnade kartor och träd". Grafer och Combinatorics . 22 (2): 185–202. CiteSeerX 10.1.1.106.7456 . doi : 10.1007/s00373-006-0647-2 . S2CID 22639942 .
^ Dujmović, Vida ; Joret, Gwenäel; Micek, Piotr; Morin, Pat ; Ueckerdt, Torsten; Wood, David R. (2020), "Plana grafer har begränsat könummer", Journal of the ACM , 67 (4): 22: 1–22: 38, arXiv : 1904.04791 , doi : 10.1145/3385731
^ Bose, Prosenjit; Dujmović, Vida ; Javarsineh, Mehrnoosh; Morin, Pat (2020), Asymptotiskt optimal toppunktsrankning av plana grafer , arXiv : 2007.06455
^ Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2019), Förbättrade gränser för centrerade färgningar , arXiv : 1907.04586
^ ÄR Filotti, Jack N. Mayer. En polynom-tidsalgoritm för att bestämma isomorfismen för grafer av fast släkt. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, s.236–243. 1980.
^ Buhl, J .; Gautrais, J .; Sole, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Theraulaz, G. (2004), "Efficiency and robustness in ant network of galleries", European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004EPJB ... 42..123B , doi : 10.1140/epjb/e2004-00364-9 , S2CID 14975826.
^ M. Halldórsson, S. Kitaev och A. Pyatkin. Semitransitiva orienteringar och ordrepresenterbara grafer, Discr. Appl. Matematik. 201 (2016), 164-171.
^ TZQ Chen, S. Kitaev och BY Sun. Ordrepresenterbarhet för ansiktsindelningar av triangulära rutdiagram, grafer och kombinationer. 32 (5) (2016), 1749-1761.
^ TZQ Chen, S. Kitaev och BY Sun. Ordrepresenterbarhet för trianguleringar av gallertäckta cylindergrafer, Discr. Appl. Matematik. 213 (2016), 60-70.

Referenser

Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF) , Fundamenta Mathematicae (på franska), 15 : 271–283, doi : 10.4064/fm-15-1-271-283.
Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen (på tyska), 114 : 570–590, doi : 10.1007/BF01594196 , S2CID 123534907.
Boyer, John M .; Myrvold, Wendy J. (2005), "On the edge: Simplified O (n) planarity by edge addition" (PDF) , Journal of Graph Algorithms and Applications , 8 (3): 241–273, doi : 10.7155/jgaa .00091.
McKay, Brendan ; Brinkmann, Gunnar, En användbar plan grafgenerator.
de Fraysseix, H .; Ossona de Mendez, P .; Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science , 17 (5): 1017–1029, arXiv : math/0610935 , doi : 10.1142/S0129054106004248 , S2CID 40107560. Specialnummer på grafritning.
DA Bader och S. Sreshta, A New Parallel Algorithm for Planarity Testing , UNM-ECE Technical Report 03-002, 1 October 2003.
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.

externa länkar

Edge Addition Planarity Algorithm Source Code, version 1.0 - Gratis C -källkod för referensimplementering av Boyer – Myrvold planaritetsalgoritm, som tillhandahåller både en kombinatorisk plan inbäddare och Kuratowski subgrafisolator. Ett open source -projekt med gratis licens ger Edge Addition Planarity Algorithms, nuvarande version .
Offentlig implementering av ett grafalgoritmbibliotek och -redigerare - GPL -grafalgoritmbibliotek inklusive planaritetstestning, planaritetsinbäddare och Kuratowski -undergrafutställning i linjär tid.
Förbättra grafbiblioteksverktyg för plana grafer , inklusive linjär tidsplanaritetstestning, inbäddning, isolering av Kuratowski-undergraf och rätlinjeteckning.
3 Hjälpprogram pussel och plana grafer
NetLogo Planarity -modell - NetLogo -version av John Tantalos spel

[1] Trudeau, Richard J. (1993). Introduktion till grafteori (korrigerad, förstorad republik. Red.). New York: Dover Pub. sid. 64. ISBN 978-0-486-67870-2. Hämtad 8 augusti 2012 . Således har ett plant diagram, när det ritas på en plan yta, antingen inga kantkorsningar eller kan ritas om utan dem.

[2] Barthelemy, M. (2017). Morfogenes av rumsliga nätverk . New York: Springer. sid. 6.

[3] Schnyder, W. (1989), "Planar grafer and poset dimension", Order , 5 (4): 323–343, doi : 10.1007/BF00353652 , MR 1010382 , S2CID 122785359.

[4] Bhasker, Jayaram; Sahni, Sartaj (1988), "A linjär algoritm för att hitta en rektangulär dubbel av en plan Triangulated graf", Algorithmica , 3 (1-4): 247-278, doi : 10,1007 / BF01762117 , S2CID 2.709.057.

[5] Seymour, PD; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR 0742878.

[6] Felsner, Stefan (2004), "1.4 Outerplanar Graphs and Convex Geometric Graphs", Geometriska grafer och arrangemang , Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, s. 6–7, doi : 10.1007/978-3-322-80303-0_1 , ISBN 3-528-06972-4, MR 2061507

[7] 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.

[8] Giménez, Omer; Noy, Marc (2009). "Asymptotisk uppräkning och gränslagar för plana grafer". Journal of the American Mathematical Society . 22 (2): 309–329. arXiv : matematik/0501269 . Bibcode : 2009JAMS ... 22..309G . doi : 10.1090/s0894-0347-08-00624-3 . S2CID 3353537 .

[9] McDiarmid, Colin; Steger, Angelika ; Welsh, Dominic JA (2005). "Slumpmässiga plana grafer". Journal of Combinatorial Theory, Serie B . 93 (2): 187–205. CiteSeerX 10.1.1.572.857 . doi : 10.1016/j.jctb.2004.09.007 .

[10] Bonichon, N .; Gavoille, C .; Hanusse, N .; Poulalhon, D .; Schaeffer, G. (2006). "Plana grafer, via välordnade kartor och träd". Grafer och Combinatorics . 22 (2): 185–202. CiteSeerX 10.1.1.106.7456 . doi : 10.1007/s00373-006-0647-2 . S2CID 22639942 .

[11] Dujmović, Vida ; Joret, Gwenäel; Micek, Piotr; Morin, Pat ; Ueckerdt, Torsten; Wood, David R. (2020), "Plana grafer har begränsat könummer", Journal of the ACM , 67 (4): 22: 1–22: 38, arXiv : 1904.04791 , doi : 10.1145/3385731

[12] Bose, Prosenjit; Dujmović, Vida ; Javarsineh, Mehrnoosh; Morin, Pat (2020), Asymptotiskt optimal toppunktsrankning av plana grafer , arXiv : 2007.06455

[13] Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2019), Förbättrade gränser för centrerade färgningar , arXiv : 1907.04586

[14] ÄR Filotti, Jack N. Mayer. En polynom-tidsalgoritm för att bestämma isomorfismen för grafer av fast släkt. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, s.236–243. 1980.

[15] Buhl, J .; Gautrais, J .; Sole, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Theraulaz, G. (2004), "Efficiency and robustness in ant network of galleries", European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004EPJB ... 42..123B , doi : 10.1140/epjb/e2004-00364-9 , S2CID 14975826.

[HKP16-16] M. Halldórsson, S. Kitaev och A. Pyatkin. Semitransitiva orienteringar och ordrepresenterbara grafer, Discr. Appl. Matematik. 201 (2016), 164-171.

[CKS2016-17] TZQ Chen, S. Kitaev och BY Sun. Ordrepresenterbarhet för ansiktsindelningar av triangulära rutdiagram, grafer och kombinationer. 32 (5) (2016), 1749-1761.

[CKS2016-2-18] TZQ Chen, S. Kitaev och BY Sun. Ordrepresenterbarhet för trianguleringar av gallertäckta cylindergrafer, Discr. Appl. Matematik. 213 (2016), 60-70.

Languages

In other projects