Vinkelupplösning (grafteori)

Vinkelupplösningen för en grafritning hänvisar till den skarpaste vinkeln som bildas av två kanter som möts vid samma vertex i ritningen.

Egenskaper

Förhållande med vertex grad

Foreman et al [1] märkte att varje ritning av en graf med segmentkanter med maximal grad d har en vinkelupplösning som inte överstiger - om v är en vertex med grad d , så delar kanterna infallande mot v utrymmet runt vertexet v i d kilar med total vinkel , och den minsta av dessa kilar måste ha en vinkel som inte överstiger . Mer strikt, om grafen är d - regelbunden , måste den ha en vinkelupplösning som är mindre än , eftersom detta är den bästa upplösningen som kan erhållas för en vertex på figurens konvexa skrov .

Förhållande med graffärgning

Som visas av Foreman et al . [1] är den största möjliga vinkelupplösningen för en graf G nära relaterad till det kromatiska talet på kvadraten på grafen G 2 , det vill säga en graf med samma uppsättning av hörn där varje hörnpar är förbundna med en kant om avståndet mellan dem i grafen G inte överstiger två. Om graf G 2 kan färgläggas med färger, så kan G ritas med vinkelupplösning för vilken som helst , genom att tilldela olika färger till hörnen på en vanlig -gon och placera varje hörn av G bredvid en polygonhörn med samma färg. Med hjälp av denna konstruktion visade de att varje graf med maximal grad d har ett mönster med en vinkelupplösning som är proportionell mot 1/ d 2 . Denna gräns är nära exakt - de använde en probabilistisk metod för att bevisa förekomsten av grafer med en maximal grad av d , vars alla ritningar har vinkelupplösning .

Förekomsten av optimala mönster

Forman et al [1] gav ett exempel som visar att det finns grafer som inte har mönster med högsta möjliga vinkelupplösning. Tvärtom, dessa grafer har en familj av ritningar vars vinkelupplösningar tenderar till ett visst begränsat värde, men inte når det. Specifikt presenterade de en graf med 11 vertex som har ett mönster med en vinkelupplösning på någon , men som inte har ett mönster med en vinkelupplösning på exakt .

Särskilda klasser av grafer

Träd

Vilket träd som helst kan ritas på ett sådant sätt att kanterna är jämnt fördelade runt varje vertex, en egenskap som kallas perfekt vinkelupplösning . Dessutom, om kanterna kan permuteras fritt runt varje vertex, är ett sådant mönster möjligt utan skärningar med kanter av längd en eller flera, och hela mönstret placeras i en polynomarea rektangel . Men om den cirkulära ordningen av kanterna runt varje vertex redan är specificerad som en del av problemformuleringen, kan det ibland krävas ett exponentiellt område för att få en vinkelupplösning utan korsningar [2] [3] .

Yttreplanära grafer

Perfekt vinkelupplösning är inte alltid möjlig för ytterplanära grafer , eftersom hörn på det konvexa skrovet av ett mönster med en grad som är större än en inte kan ha kanter som faller in mot det jämnt fördelade runt vertexet. Men varje yttre plan graf med maximal grad d har en yttre plan ritning med en vinkelupplösning proportionell mot 1/ d [4] [5] .

Plana grafer

För plana grafer med maximal grad d , producerar Foremans (et al.) grafkvadratfärgningsteknik [1] en ritning med en vinkelupplösning som är proportionell mot 1/ d , eftersom kvadraten på en plan graf måste ha ett kromatiskt tal proportionellt mot d . Wegner antog 1977 att det kromatiska talet för kvadraten i en plan graf inte överstiger och det är känt att det kromatiska talet inte överstiger [6] [7] . Mönstret som erhålls med denna teknik är emellertid i allmänhet inte plant.

För vissa plana grafer är den optimala vinkelupplösningen för en plan ritning med linjesegment O(1/ d 3 ) , där d är graden av grafen [5] . Dessutom kan sådana mönster tvingas ha mycket långa kanter, längre än exponentialfaktorn från mönstrets kortaste kant. Malitz och Papakostas [4] använde cirkelpackningssatsen för att visa att varje plan graf med maximal grad d har ett plant mönster vars sämsta vinkelupplösning är en exponentiell funktion av d och oberoende av antalet grafens hörn.

Beräkningskomplexitet

Problemet med att avgöra om en given graf med maximal grad d har ett mönster med vinkelupplösning är NP-hårt även i specialfallet d =4 [1] [8] . Men för vissa begränsade klasser av ritningar, inklusive ritningar av träd, där förlängningen av löv till oändligheten ger en konvex partition av planet, såväl som ritningar av plana grafer, där varje avgränsad yta är en centralt symmetrisk polygon, en ritning med optimal vinkelupplösning kan hittas i polynomtid [9] [10] .

Historik

Vinkelupplösningen bestämdes av Forman et al [1] .

Även om det ursprungligen definierades för ritningar av grafer med raka kanter, undersökte senare författare vinkelupplösningen för ritningar där kanterna är polygonala [11] [12] , cirkulära bågar [13] [2] eller splines [14] [15] .

En grafs vinkelupplösning är nära relaterad till dess skärningsupplösning, de vinklar som bildas av skärningspunkterna i grafritningen. Särskilt, att rita grafer i räta vinklar letar efter en representation som säkerställer att alla dessa vinklar är räta vinklar , vilket är den största möjliga skärningsvinkeln [16]

Anteckningar

  1. ↑ 1 2 3 4 5 6 Formann, Hagerup, Haralambides et al., 1993 .
  2. ↑ 1 2 Duncan, Eppstein, Goodrich et al., 2011 .
  3. ↑ Halupczok, Schulz, 2011 .
  4. ↑ 1 2 Malitz, Papakostas, 1994 .
  5. ↑ 1 2 Garg, Tamassia, 1994 .
  6. ↑ Kramer, Kramer, 2008 .
  7. ↑ Molloy, Salavatipour, 2005 .
  8. ↑ Garg, Tamassia, 1995 .
  9. ↑ Carlson, Eppstein, 2007 .
  10. ↑ Eppstein, Wortman, 2011 .
  11. ↑ Kant, 1996 .
  12. ↑ Gutwenger, Mutzel, 1998 .
  13. ↑ Cheng, Duncan, Goodrich, Kobourov, 1999 .
  14. ↑ Brandes, Shubina, Tamassia, 2000 .
  15. ↑ Finkel, Tamassia, 2005 .
  16. ↑ Didimo, Eades, Liotta, 2009 .

Litteratur