Kapslad triangelgraf

En kapslad triangelgraf med n hörn är en plan graf som bildas av en sekvens av n /3 trianglar vars motsvarande par av hörn är förbundna med kanter. Den kan också formas geometriskt genom att limma ihop triangulära prismor längs deras triangulära ytor. Denna graf och närbesläktade grafer används ofta inom grafvisualisering för att bevisa nedre gränser för det område som krävs för olika ritstilar. ${\tfrac {n}{3}}-1$

Polyedrisk representation

En kapslad triangelgraf med två trianglar är en triangulär prismagraf , och en kapslad triangelgraf med tre trianglar är en bitrunkerad bipyramidgraf . Mer generellt, eftersom inbäddade triangelgrafer är plana och vertex-3-anslutna , följer det av Steinitz sats att de alla kan representeras som konvexa polyedrar.

En alternativ geometrisk representation av dessa grafer kan ges genom att limma triangulära prismor längs triangulära ytor. Antalet kapslade trianglar är en större än antalet limmade prismor. Men när du använder rektangulära prismor, gör processen att limma dem att angränsande rektangulära ytor är i samma plan , så att resultatet inte är en strikt konvex kropp.

Nedre områdesgränser för ritningar av grafer

Namnet kapslad triangelgraf föreslogs av Dolev, Layton och Tricky [2] , som använde det för att visa att ritning av en plan graf med n hörn på ett heltalsgitter (med linjesegmentkanter ) kan kräva en begränsningsruta på minst [3] ] . I en sådan ritning spelar det ingen roll vilken yta som väljs som ytterkant, någon efterföljd av minst n /6 trianglar måste ritas kapslade inuti varandra, och i denna del av ritningen måste varje triangel använda två rader och två kolumner mer än nästa inre triangel. Om val av yttre yta inte är tillåtet som en del av ritningsalgoritmen, utan ges som en del av inmatningen, visar samma argument att en storleksgränsruta behövs och en ritning med dessa dimensioner finns. ${\tfrac {n}{3}}\times {\tfrac {n}{3}}$ ${\tfrac {2n}{3}}\times {\tfrac {2n}{3}}$

För ritningar där den yttre ytan kan väljas fritt, kanske den nedre gränsen för området Dolev, Leighton och Tricky [2] inte är stel. Frati och Patrignani [1] visade att denna graf, och vilken graf som helst som bildas genom att lägga till diagonaler till dess fyrhörningar, kan ritas i en rektangel med storlek . Om inga ytterligare diagonaler läggs till kan den kapslade triangelgrafen ritas även med en mindre yta, liknande figuren. Att stänga gapet mellan den övre gränsen och den nedre gränsen för området för det maximala plana komplementet av en inbäddad triangulär graf förblir ett öppet problem [4] . ${\tfrac {n}{3}}\times {\tfrac {2n}{3}}$ ${\tfrac {n}{3}}\ gånger {\tfrac {n}{2}}$ ${\tfrac {2n^{2}}{9}}$ ${\tfrac {n^{2}}{9}}$

Olösta problem i matematik : Vad är arean för den minsta begränsningsrutan när man ritar en kapslad triangulär graf på ett gitter, eller dess maximala plana komplettering?

Varianter av kapslade triangulära grafer har använts för många andra nedre gränser när man ritar grafer, till exempel arean av en rektangulär representation (när hörnen representeras av rektanglar och kanterna är ritade som streckade linjer med delar parallella med axlarna) [5] , arean av ritningar med vinkelräta skärningar [6] eller relativa områden av en plan representation jämfört med en icke-plan [7] .

Anteckningar

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

Litteratur

Danny Dolev, F. Thomson Leighton, Howard Trickey. Plan inbäddning av plana grafer // Framsteg inom datorforskning. - 1984. - T. 2 . — S. 147–161 .
Fabrizio Frati, Maurizio Patrignani. En anteckning om rätlinjeritningar med minsta area av plana grafer // Graph Drawing: 15th International Symposium, GD 2007 , Sydney, Australien, 24-26 september 2007, Revised Papers. - Berlin: Springer, 2008. - T. 4875. - S. 339–344. — ( Lecture Notes in Computer Science ). - doi : 10.1007/978-3-540-77537-9_33 .
Ulrich Fössmeier, Goos Kant, Michael Kaufmann. 2-synlighetsritningar av plana grafer // Graph Drawing: Symposium on Graph Drawing, GD '96 Berkeley, Kalifornien, USA, 18–20 september 1996, Proceedings. - 1997. - T. 1190. - S. 155-168. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/3-540-62495-3_45 .
Walter Didimo, Giuseppe Liotta. Korsningsvinkelupplösningen i grafritning // Trettio uppsatser om geometrisk grafteori / János Pach. - Springer, 2013. - S. 167-184. - doi : 10.1007/978-1-4614-0110-0_10 .
Marc van Creveld. Kvalitetsförhållandet mellan RAC-ritningar och planritningar av plana grafer // Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Tyskland, 21-24 september 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. - 2011. - T. 6502. - S. 371-376. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-642-18469-7_34 .