Beágyazott háromszögdiagram

Egy n csúcsú beágyazott háromszöggráf egy sík gráf , amelyet n /3 háromszög sorozat alkot , amelyeknek a megfelelő csúcspárjait élek kötik össze. Geometriailag is kialakítható úgy , hogy háromszög alakú prizmákat ragasztunk egymáshoz háromszöglapjuk mentén. Ezt a grafikont és a hozzá szorosan kapcsolódó grafikonokat gyakran használják a gráfvizualizáció területén , hogy bizonyítsák a különböző rajzstílusokhoz szükséges terület alsó határait .

Poliéderes ábrázolás

A két háromszögből álló beágyazott háromszöggráf háromszög prizmagráf , a három háromszögből álló beágyazott háromszöggráf pedig egy bitroncsolt bipiramisgráf . Általánosabban szólva, mivel a beágyazott háromszöggráfok síkbeliek és 3- as csúcsúak, Steinitz tételéből következik , hogy mindegyik konvex poliéderként ábrázolható.

Ezeknek a grafikonoknak egy alternatív geometriai ábrázolása adható meg háromszög alakú prizmák háromszöglapok mentén történő ragasztásával. A beágyazott háromszögek száma eggyel nagyobb, mint a ragasztott prizmák száma. Ha azonban téglalap alakú prizmákat használunk, a ragasztásuk során a szomszédos téglalaplapok egy síkban helyezkednek el , így az eredmény nem egy szigorúan domború test.

Alsó területhatárok grafikonok rajzaihoz

A beágyazott háromszöggráf elnevezést Dolev, Layton és Tricky [2] javasolta , akik arra használták, hogy bemutassák, hogy egy n csúcsú síkgráf egész rácsra rajzolásához ( szakasz élekkel ) legalább [3] határolódobozra van szükség. ] . Egy ilyen rajznál nem mindegy, hogy melyik lapot választjuk külső élnek, legalább n /6 háromszögből álló részsorozatot egymásba ágyazva kell megrajzolni, és a rajz ezen részében minden háromszögnek két-két sort kell használnia. két oszloppal több, mint a következő belső háromszög. Ha a külső felület kijelölése nem engedélyezett a rajzalgoritmus részeként, de a bemenet részeként megadva, ugyanazok az argumentumok azt mutatják, hogy szükség van egy mérethatároló dobozra, és létezik ilyen méretekkel rendelkező rajz.

Azoknál a rajzoknál, amelyeken a külső felület szabadon választható, Dolev, Leighton és Tricky [2] területének alsó határa nem lehet merev. Frati és Patrignani [1] megmutatta, hogy ez a gráf, és minden olyan gráf, amelyet a négyszögek átlóinak hozzáadásával alakítunk ki, megrajzolható egy méretű téglalapban . Ha nem adunk hozzá további átlókat, a beágyazott háromszöggráf az ábrához hasonlóan akár kisebb területtel is megrajzolható . Egy beágyazott háromszöggráf maximális síkkomplemensének területének felső és alsó korlátja közötti rés bezárása továbbra is nyitott probléma marad [4] .

Megoldatlan problémák a matematikában : Mekkora a minimális határolókeret területe, ha egy rácsra ágyazott háromszöggráfot rajzolunk, vagy annak maximális síkbeli befejezése?

A beágyazott háromszög gráfok változatait sok más alsó határhoz is használták gráfok rajzolásakor, mint például a téglalap alakú ábrázolás területe (amikor a csúcsokat téglalapok ábrázolják, az éleket pedig szaggatott vonalakként rajzolják meg a tengelyekkel párhuzamos részekkel). [5] , a merőleges metszéspontú rajzok területe [6] vagy egy síkbeli ábrázolás relatív területe a nem síkbeli ábrázoláshoz képest [7] .

Jegyzetek

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

Irodalom