St-plan graf


En st - plan graf er en bipolær orientering af en plan graf, for hvilken både kilden og fordybningen af ​​orienteringen er på den ydre side af grafen. Det vil sige, det er en rettet graf tegnet uden skæringspunkter på planet på en sådan måde, at der ikke er nogen rettede cyklusser i grafen, nøjagtigt et toppunkt på grafen har ingen indgangsbuer, nøjagtigt et toppunkt på grafen har ingen udgående buer, og begge disse to specielle hjørner ligger på den ydre sidesøjle [1] .

På tegningen skal hver flade af grafen have den samme struktur - der er et toppunkt, der tjener som kilden til ansigtet, et toppunkt fungerer som ansigtets synke, og alle kanter inde i ansigtet er rettet langs to stier fra kilden til vasken. Hvis vi tegner en ekstra kant fra synken af ​​den st -plane graf tilbage til kilden langs den ydre flade og derefter konstruerer den dobbelte graf (orienterer hver dobbeltkant med uret i forhold til den oprindelige kant), så får vi igen en st -planar graf udvidet med en ekstra kant på samme måde [1] .

Ordensteori

Disse grafer er tæt forbundet med delvist ordnede sæt og gitter . Hasse-diagrammet for en poset er en rettet acyklisk graf, hvis toppunkter er det sæt af elementer, hvori der er en kant fra x til y for hvert par x , y af elementer, for hvilke der er en delvis rækkefølge, men for hvilke der ikke er nogen z . c . En poset danner et komplet gitter, hvis og kun hvis en delmængde af elementer har en enkelt største nedre grænse og en enkelt mindste øvre grænse, og ordensdimensionen poset er det mindste antal lineært ordnede sæt på det samme sæt af elementer, hvis skæringspunkt er den givne delrækkefølge. Hvis hjørnerne af en st -plan graf er delvist tilgængelig-ordnet, så danner denne rækkefølge altid et todimensionalt komplet gitter, hvis Hasse-diagram er en transitiv sammentrækning af den givne graf. Omvendt er Hasse-diagrammet for ethvert todimensionelt komplet gitter altid en st -plan graf [2] .

Tegning af grafer

Baseret på denne todimensionelle partielle ordensegenskab kan enhver st -plan graf repræsenteres som et dominerende mønster , hvor der for hver to toppunkter u og v er en vej fra u til v , hvis og kun hvis begge koordinater u er mindre end, end de tilsvarende koordinater v [3] . Koordinaterne for en sådan tegning kan bruges som en datastruktur, der kan bruges til at kontrollere, at fra et toppunkt på en st -plan graf er det muligt at nå et andet toppunkt i konstant tid pr. anmodning. Drejning af figuren 45° giver en stigende plan repræsentation af grafen. En rettet acyklisk graf G har en stigende plan repræsentation, hvis og kun hvis G er en undergraf af en st -plan graf [4] .

Noter

  1. ↑ 1 2 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. 4.2 Egenskaber for plane acykliske digrafer // Graftegning: Algoritmer til visualisering af grafer. - Prentice Hall , 1998. - S. 89-96. — ISBN 978-0-13-301615-4 . .
  2. ↑ Platt CR Plane gitter og plane grafer // Journal of Combinatorial Theory . - 1976. - T. 21 , no. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 . .
  3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 112–127 §4.7 Dominanstegninger.
  4. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmer til planrepræsentationer af acykliske digrafer // Teoretisk datalogi . - 1988. - T. 61 , no. 2-3 . - doi : 10.1016/0304-3975(88)90123-5 . .