Indlejret trekantgraf

En indlejret trekantgraf med n toppunkter er en plan graf dannet af en sekvens af n /3 trekanter, hvis tilsvarende par af hjørner er forbundet med kanter. Det kan også dannes geometrisk ved at lime trekantede prismer sammen langs deres trekantede flader. Denne graf og nært beslægtede grafer bruges ofte inden for grafvisualisering for at bevise nedre grænser for det påkrævede område for forskellige tegnestile.

Polyhedral repræsentation

En indlejret trekantgraf med to trekanter er en trekantet prismegraf , og en indlejret trekantgraf med tre trekanter er en bitrunkeret bipyramidegraf . Mere generelt, da indlejrede trekantgrafer er plane og vertex-3-forbundne , følger det af Steinitz's sætning , at de alle kan repræsenteres som konvekse polyedre.

En alternativ geometrisk repræsentation af disse grafer kan gives ved at lime trekantede prismer langs trekantede flader. Antallet af indlejrede trekanter er én større end antallet af limede prismer. Men når du bruger rektangulære prismer, forårsager processen med at lime dem, at tilstødende rektangulære flader er koplanære , så resultatet ikke er en strengt konveks krop.

Nedre arealgrænser for tegninger af grafer

Navnet indlejret trekantgraf blev foreslået af Dolev, Layton og Tricky [2] , som brugte det til at vise, at tegning af en plan graf med n toppunkter på et heltalsgitter (med linjesegmentkanter ) kan kræve en afgrænsningsramme på mindst [3] ] . I en sådan tegning er det ligegyldigt, hvilken flade der vælges som yderkant, der skal tegnes en efterfølger på mindst n /6 trekanter indlejret i hinanden, og i denne del af tegningen skal hver trekant bruge to rækker og to kolonner mere end den næste indre trekant. Hvis valg af ydre flade ikke er tilladt som en del af tegningsalgoritmen, men givet som en del af inputtet, viser de samme argumenter, at der er behov for en afgrænsningsramme for størrelse, og at der findes en tegning med disse dimensioner.

For tegninger, hvor den ydre flade kan vælges frit, er den nedre grænse af området Dolev, Leighton og Tricky [2] muligvis ikke stiv. Frati og Patrignani [1] viste, at denne graf, og enhver graf dannet ved at tilføje diagonaler til dens firkanter, kan tegnes i et rektangel af størrelse . Hvis der ikke tilføjes yderligere diagonaler, kan den indlejrede trekant-graf tegnes selv med et mindre område, svarende til figuren. At lukke afstanden mellem den øvre grænse og den nedre grænse af området af det maksimale plane komplement af en indlejret trekantet graf forbliver et åbent problem [4] .

Uløste problemer i matematik : Hvad er arealet af den mindste afgrænsningsramme, når man tegner en indlejret trekantet graf på et gitter, eller dens maksimale plane færdiggørelse?

Varianter af indlejrede trekantede grafer er blevet brugt til mange andre nedre grænser ved tegning af grafer, såsom arealet af en rektangulær repræsentation (når hjørnerne er repræsenteret af rektangler, og kanterne er tegnet som stiplede linjer med dele parallelt med akserne) [5] , arealet af tegninger med vinkelrette skæringspunkter [6] eller relative arealer af en plan repræsentation sammenlignet med en ikke-plan repræsentation [7] .

Noter

  1. ↑ 12 Frati , Patrignani, 2008 .
  2. ↑ 1 2 Dolev, Leighton, Trickey, 1984 .
  3. ↑ Dolev, Leighton, Trickey, 1984 , s. 147-161.
  4. ↑ Frati, Patrignani, 2008 , s. 339-344.
  5. ↑ Fößmeier, Kant, Kaufmann, 1997 , s. 155-168.
  6. ↑ Didimo og Liotta, 2013 , s. 167-184.
  7. ↑ van Kreveld, 2011 , s. 371-376.

Litteratur