Vnořený trojúhelníkový graf

Vnořený trojúhelníkový graf s n vrcholy je rovinný graf tvořený posloupností n /3 trojúhelníků, jejichž odpovídající dvojice vrcholů jsou spojeny hranami. Může být také vytvořen geometricky slepením trojúhelníkových hranolů podél jejich trojúhelníkových ploch. Tento graf a úzce související grafy se často používají v oblasti vizualizace grafů k prokázání spodních hranic požadované oblasti pro různé styly kreslení. ${\tfrac {n}{3}}-1$

Polyedrické zobrazení

Vnořený trojúhelníkový graf se dvěma trojúhelníky je trojúhelníkový hranolový graf a vnořený trojúhelníkový graf se třemi trojúhelníky je bitrunncated bipyramidový graf . Obecněji, protože vložené trojúhelníkové grafy jsou rovinné a vrcholově-3-spojené , vyplývá ze Steinitzovy věty , že všechny mohou být reprezentovány jako konvexní mnohostěny.

Alternativní geometrická reprezentace těchto grafů může být dána lepením trojúhelníkových hranolů podél trojúhelníkových ploch. Počet vnořených trojúhelníků je o jeden větší než počet lepených hranolů. Při použití pravoúhlých hranolů však proces jejich lepení způsobí, že sousední pravoúhlé plochy jsou koplanární , takže výsledkem není přísně konvexní těleso.

Dolní hranice oblasti pro kreslení grafů

Název vnořený trojúhelníkový graf navrhli Dolev, Layton a Tricky [2] , kteří jej použili, aby ukázali, že kreslení rovinného grafu s n vrcholy na celočíselné mřížce (s hranami úsečky ) může vyžadovat ohraničující rámeček o velikosti alespoň [3 ] . V takovém výkresu je jedno, která plocha je zvolena jako vnější hrana, musí být nakreslena nějaká dílčí posloupnost alespoň n /6 trojúhelníků vnořených do sebe a v této části výkresu musí každý trojúhelník používat dvě řady a o dva sloupce více než další vnitřní trojúhelník. Pokud není výběr vnější plochy povolen jako součást kreslicího algoritmu, ale je zadán jako součást vstupu, stejné argumenty ukazují, že je potřeba ohraničovací rámeček velikosti a výkres s těmito rozměry existuje. ${\tfrac {n}{3}}\times {\tfrac {n}{3}}$ ${\tfrac {2n}{3}}\times {\tfrac {2n}{3}}$

U výkresů, u kterých lze libovolně zvolit vnější plochu, nemusí být spodní hranice oblasti Doleva, Leightona a Trickyho [2] pevná. Frati a Patrignani [1] ukázali, že tento graf a jakýkoli graf vytvořený přidáním úhlopříček k jeho čtyřúhelníkům lze nakreslit v obdélníku o velikosti . Pokud nejsou přidány žádné další úhlopříčky, lze vnořený trojúhelníkový graf nakreslit i s menší plochou, podobně jako na obrázku. Otevřeným problémem zůstává uzavření mezery mezi horní a dolní hranicí plochy maximálního rovinného doplňku vloženého trojúhelníkového grafu [4] . ${\tfrac {n}{3}}\times {\tfrac {2n}{3}}$ ${\tfrac {n}{3}}\times {\tfrac {n}{2}}$ ${\tfrac {2n^{2}}{9}}$ ${\tfrac {n^{2}}{9}}$

Nevyřešené problémy v matematice : Jaká je plocha minimálního ohraničujícího rámečku při kreslení vnořeného trojúhelníkového grafu na mřížku nebo jeho maximální rovinné dokončení?

Varianty vnořených trojúhelníkových grafů byly použity pro mnoho dalších spodních hranic při kreslení grafů, jako je plocha obdélníkového zobrazení (když jsou vrcholy reprezentovány obdélníky a hrany jsou nakresleny jako přerušované čáry s částmi rovnoběžnými s osami) [5] , plocha výkresů s kolmými průsečíky [6] nebo relativní plochy rovinného zobrazení ve srovnání s nerovinným [7] .

Poznámky

↑ 12 Frati , Patrignani, 2008 .
↑ 1 2 Dolev, Leighton, Trickey, 1984 .
↑ Dolev, Leighton, Trickey, 1984 , str. 147–161.
↑ Frati, Patrignani, 2008 , s. 339–344.
↑ Fößmeier, Kant, Kaufmann, 1997 , str. 155–168.
↑ Didimo a Liotta, 2013 , str. 167–184.
↑ van Kreveld, 2011 , str. 371–376.

Literatura

Danny Dolev, F. Thomson Leighton, Howard Trickey. Rovinné vkládání rovinných grafů // Pokroky ve výzkumu výpočetní techniky. - 1984. - T. 2 . — S. 147–161 .
Fabrizio Frati, Maurizio Patrignani. Poznámka k přímkovým nákresům rovinných grafů s minimální plochou // Kresba grafů: 15. mezinárodní symposium, GD 2007 , Sydney, Austrálie, 24.–26. září 2007, Revised Papers. - Berlin: Springer, 2008. - T. 4875. - S. 339–344. — ( Poznámky k přednáškám z informatiky ). - doi : 10.1007/978-3-540-77537-9_33 .
Ulrich Fössmeier, Goos Kant, Michael Kaufmann. 2-visibility drawings of planar graphs // Graph Drawing: Symposium on Graph Drawing, GD '96 Berkeley, Kalifornie, USA, 18.–20. září 1996, Proceedings. - 1997. - T. 1190. - S. 155-168. — (Poznámky z informatiky). - doi : 10.1007/3-540-62495-3_45 .
Walter Didimo, Giuseppe Liotta. Rozlišení úhlu křížení při kreslení grafů // Thirty Essays on Geometric Graph Theory / János Pach. - Springer, 2013. - S. 167-184. - doi : 10.1007/978-1-4614-0110-0_10 .
Marc van Creveld. Poměr kvality výkresů RAC a plošných výkresů rovinných grafů // Kresba grafů: 18. mezinárodní symposium, GD 2010, Konstanz, Německo, 21.-24. září 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. - 2011. - T. 6502. - S. 371-376. — (Poznámky z informatiky). - doi : 10.1007/978-3-642-18469-7_34 .