Graficul st-planar

Un graf st - plan este o orientare bipolară a unui graf plan pentru care atât sursa, cât și receptorul orientării sunt pe fața exterioară a graficului. Adică, este un grafic dirijat desenat fără intersecții pe plan în așa fel încât să nu existe cicluri direcționate în grafic, exact un vârf al graficului nu are arce de intrare, exact un vârf al graficului nu are arce de ieșire, iar ambele aceste două vârfuri speciale se află pe coloana feței exterioare [1] .

În desen, fiecare față a graficului trebuie să aibă aceeași structură - există un vârf care servește ca sursă pentru față, un vârf servește ca chiuvetă a feței și toate marginile din interiorul feței sunt direcționate pe două căi de la sursa la chiuvetă. Dacă tragem o muchie suplimentară din scufundarea graficului st -planar înapoi la sursă de-a lungul feței exterioare și apoi construim graficul dual (orientând fiecare muchie dublă în sensul acelor de ceasornic față de muchia originală), atunci obținem din nou un st -planar. grafic extins cu o muchie suplimentară în același mod [1 ] .

Teoria ordinii

Aceste grafice sunt strâns legate de mulțimi și rețele parțial ordonate . Diagrama Hasse a unui poset este un graf aciclic direcționat ale cărui vârfuri sunt mulțimea de elemente în care există o muchie de la x la y pentru fiecare pereche x , y de elemente pentru care există o ordine parțială dar pentru care nu există z c . Un poset formează o rețea completă dacă și numai dacă orice subset de elemente are o singură limită inferioară cea mai mare și o singură limită superioară cea mai mică, iar dimensiunea ordinală posetului este cel mai mic număr de mulțimi ordonate liniare din același set de elemente a căror intersecție este ordinea parțială dată. Dacă vârfurile unui graf st -planar sunt parțial accesibile-ordonate, atunci această ordonare formează întotdeauna o rețea completă bidimensională a cărei diagramă Hasse este o contracție tranzitivă a graficului dat. În schimb, diagrama Hasse a oricărei rețele complete bidimensionale este întotdeauna un graf st -planar [2] .

Desenarea graficelor

Pe baza acestei proprietăți de ordin parțial bidimensional, orice graf st -plan poate fi reprezentat ca un model dominant în care pentru fiecare două vârfuri u și v există o cale de la u la v dacă și numai dacă ambele coordonate u sunt mai mic decât, decât coordonatele corespunzătoare v [3] . Coordonatele unui astfel de desen pot fi folosite ca o structură de date care poate fi folosită pentru a verifica că dintr-un vârf al unui graf st -planar este posibil să se ajungă la un alt vârf în timp constant per interogare. Rotirea figurii cu 45° oferă o reprezentare plană ascendentă a graficului. Un graf aciclic direcționat G are o reprezentare plană ascendentă dacă și numai dacă G este un subgraf al unui graf st -planar [4] .

Note

1. ↑ 1 2 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. 4.2 Proprietăţile digrafelor aciclice plane // Desen grafic: algoritmi pentru vizualizarea graficelor. - Prentice Hall , 1998. - S. 89-96. — ISBN 978-0-13-301615-4 . .
2. ↑ Platt CR Rețele planare și grafuri plane // 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 , p. 112–127 §4.7 Desene de dominanță.
4. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmi pentru reprezentări plane ale digrafelor aciclice // Informatică teoretică . - 1988. - T. 61 , nr. 2-3 . - doi : 10.1016/0304-3975(88)90123-5 . .