St-planar graf


En st - plan graf är en bipolär orientering av en plan graf där både källan och sänkan för orienteringen är på utsidan av grafen. Det vill säga, det är en riktad graf ritad utan skärningar på planet på ett sådant sätt att det inte finns några riktade cykler i grafen, exakt en vertex på grafen har inga ingående bågar, exakt en vertex på grafen har inga utgående bågar, och båda dessa två speciella hörn ligger på yttersidans kolumn [1] .

På ritningen måste varje yta av grafen ha samma struktur - det finns en vertex som fungerar som källan för ansiktet, en vertex fungerar som sänkan av ansiktet, och alla kanter inuti ansiktet är riktade längs två banor från källan till diskbänken. Om vi ​​ritar ytterligare en kant från sänkan av den st -plana grafen tillbaka till källan längs den yttre ytan och sedan konstruerar den dubbla grafen (orienterar varje dubbelkant medurs i förhållande till den ursprungliga kanten), så får vi återigen en st -planar graf förlängd med ytterligare en kant på samma sätt [1] .

Ordningsteori

Dessa grafer är nära besläktade med delvis ordnade uppsättningar och gitter . Hasse-diagrammet för en poset är en riktad acyklisk graf vars hörn är den uppsättning element där det finns en kant från x till y för varje par x , y av element för vilka det finns en partiell ordning men för vilka det inte finns någon z c . En poset bildar ett komplett gitter om och endast om någon delmängd av element har en enda största nedre gräns och en enda minsta övre gräns, och ordningsdimensionen poset är det minsta antalet linjärt ordnade uppsättningar på samma uppsättning av element vars skärningspunkt är den givna delordningen. Om hörnen på en st -planär graf är delvis nåbar-ordnad, så bildar denna ordning alltid ett tvådimensionellt komplett gitter vars Hasse-diagram är en transitiv sammandragning av den givna grafen. Omvänt är Hasse-diagrammet för alla tvådimensionella kompletta gitter alltid en st -planär graf [2] .

Rita grafer

Baserat på denna tvådimensionella partiella ordningsegenskap kan vilken st -plan graf som helst representeras som ett dominerande mönster där det för varje två hörn u och v finns en väg från u till v om och endast om båda koordinaterna u är mindre än, än motsvarande koordinater v [3] . Koordinaterna för en sådan ritning kan användas som en datastruktur som kan användas för att kontrollera att från en vertex av en st -planar graf är det möjligt att nå en annan vertex i konstant tid per fråga. Att rotera figuren 45° ger en stigande plan representation av grafen. En riktad acyklisk graf G har en stigande plan representation om och endast om G är en subgraf till en st -planär graf [4] .

Anteckningar

  1. ↑ 1 2 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. 4.2 Egenskaper för plana acykliska diagram // Grafritning: Algoritmer för visualisering av grafer. - Prentice Hall , 1998. - S. 89-96. — ISBN 978-0-13-301615-4 . .
  2. ↑ Platt CR Plana gitter och plana grafer // Journal of Combinatorial Theory . - 1976. - T. 21 , nr. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 . .
  3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 112–127 §4.7 Dominansritningar.
  4. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmer för planrepresentationer av acykliska digrafer // Teoretisk datavetenskap . - 1988. - T. 61 , nr. 2-3 . - doi : 10.1016/0304-3975(88)90123-5 . .