St-planární graf

St - planární graf je bipolární orientace rovinného grafu , pro kterou je zdroj i pokles orientace na vnější straně grafu. To znamená, že jde o orientovaný graf nakreslený bez průsečíků v rovině tak, že v grafu nejsou žádné orientované cykly, přesně jeden vrchol grafu nemá žádné vstupní oblouky, přesně jeden vrchol grafu nemá žádné výstupní oblouky, a oba tyto dva speciální vrcholy leží na vnějším čelním sloupu [1] .

Na výkresu musí mít každá plocha grafu stejnou strukturu – existuje jeden vrchol, který slouží jako zdroj plochy, jeden vrchol slouží jako propad plochy a všechny hrany uvnitř plochy směřují podél dvou cest od zdroj do umyvadla. Pokud nakreslíme další hranu z propadu st -planárního grafu zpět ke zdroji podél vnější plochy a poté sestrojíme duální graf (s orientací každé duální hrany ve směru hodinových ručiček vzhledem k původní hraně), pak opět dostaneme st -planární graf rozšířený o další hranu stejným způsobem [1] .

Teorie řádu

Tyto grafy úzce souvisejí s částečně uspořádanými množinami a svazy . Hasseův diagram posetu je orientovaný acyklický graf, jehož vrcholy jsou množinou prvků, ve kterých je hrana od x do y pro každou dvojici x , y prvků, pro které existuje částečné uspořádání, ale pro které neexistuje žádné z c . Poset tvoří úplnou mřížku právě tehdy, když jakákoli podmnožina prvků má jedinou největší dolní hranici a jedinou nejmenší horní hranici a ordinální rozměr posetu je nejmenší počet lineárně uspořádaných množin na stejné množině prvky, jejichž průsečíkem je daný dílčí řád. Pokud jsou vrcholy st -planárního grafu částečně dosažitelné-uspořádané, pak toto uspořádání vždy tvoří dvourozměrnou úplnou mřížku, jejíž Hasseův diagram je tranzitivní kontrakcí daného grafu. Naopak Hasseův diagram jakékoli dvourozměrné kompletní mřížky je vždy st - planární graf [2] .

Kreslení grafů

Na základě této dvourozměrné vlastnosti částečného řádu lze jakýkoli st -planární graf reprezentovat jako dominantní vzor , ve kterém pro každé dva vrcholy u a v existuje cesta z u do v právě tehdy, když jsou obě souřadnice u menší než, než odpovídající souřadnice v [3] . Souřadnice takového výkresu lze použít jako datovou strukturu , kterou lze použít ke kontrole, že z vrcholu st - planárního grafu je možné dosáhnout jiného vrcholu v konstantním čase na dotaz. Otočením obrázku o 45° získáte vzestupnou rovinnou reprezentaci grafu. Orientovaný acyklický graf G má vzestupnou rovinnou reprezentaci právě tehdy, když G je podgrafem st - planárního grafu [4] .

Poznámky

1. ↑ 1 2 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. 4.2 Vlastnosti planárních acyklických digrafů // Kreslení grafů: Algoritmy pro vizualizaci grafů. - Prentice Hall , 1998. - S. 89-96. — ISBN 978-0-13-301615-4 . .
2. ↑ Platt CR Rovinné svazy a rovinné grafy // 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 , str. 112–127 §4.7 Kresby dominance.
4. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmy pro rovinné reprezentace acyklických digrafů // Teoretická informatika . - 1988. - T. 61 , no. 2-3 . - doi : 10.1016/0304-3975(88)90123-5 . .