Vinkelupplösning (grafritning)

Denna ritning av en hyperkubgraf har vinkelupplösning π/4 .

Vid grafritning är vinkelupplösningen för en ritning av en graf den skarpaste vinkeln som bildas av två kanter som möts vid en gemensam vertex av ritningen.

Egenskaper

Relation till vertexgrad

Formann et al. (1993) observerade att varje rätlinjeritning av en graf med maximal grad d har vinkelupplösning som högst 2π/ d : om v är en vertex av grad d , så delar kanterna som faller in mot v upp utrymmet runt v i d kilar med total vinkel 2π , och den minsta av dessa kilar måste ha en vinkel på högst 2π/ d . Ännu starkare, om en graf är d - regelbunden , måste den ha en vinkelupplösning som är mindre än ${\displaystyle {\frac {\pi }{d-1}}} ,$ eftersom detta är den bästa upplösningen som kan uppnås för en vertex på ritningens konvexa skrov .

Relation till graffärgning

Som Formann et al. (1993) visade att den största möjliga vinkelupplösningen för en graf G är nära relaterad till det kromatiska talet för kvadraten G ² , grafen på samma vertexuppsättning där par av hörn är förbundna med en kant närhelst deras avstånd i G är högst två. Om G ² kan färgas med χ- färger, kan G ritas med vinkelupplösning π/ χ − ε , för valfri ε > 0 , genom att tilldela distinkta färger till hörnen på en vanlig χ -gon och placera varje vertex av G nära till polygonens vertex med samma färg. Med hjälp av denna konstruktion visade de att varje graf med maximal grad d har en ritning med vinkelupplösning proportionell mot 1/ d ² . Denna gräns är nästan snäv: de använde den probabilistiska metoden för att bevisa förekomsten av grafer med maximal grad d vars ritningar alla har vinkelupplösning $O\left({\frac {\log d }{d^{2}}}\höger)$ .

Förekomsten av optimala ritningar

Formann et al. (1993) gav ett exempel som visar att det finns grafer som inte har en ritning som uppnår maximal möjlig vinkelupplösning; istället har dessa grafer en familj av ritningar vars vinkelupplösningar tenderar mot något begränsande värde utan att nå det. Specifikt uppvisade de en graf med 11 vertex som har ritningar med vinkelupplösning π/3 − ε för någon ε > 0 , men som inte har en ritning med vinkelupplösning exakt π/3 .

Särskilda klasser av grafer

Träd

Varje träd kan ritas på ett sådant sätt att kanterna är lika fördelade runt varje vertex, en egenskap som kallas perfekt vinkelupplösning . Dessutom, om kanterna kan permuteras fritt runt varje vertex, så är en sådan ritning möjlig, utan korsningar, med alla kanter enhetslängd eller högre, och med hela ritningen inpassad inom en begränsningslåda med polynomarea . Men om den cykliska ordningen av kanterna runt varje vertex redan bestäms som en del av indata till problemet, kan det ibland kräva exponentiell yta för att uppnå perfekt vinkelupplösning utan korsningar.

Outerplanar grafer

Perfekt vinkelupplösning är inte alltid möjlig för ytterplanära grafer , eftersom hörn på det konvexa skrovet på ritningen med en grad som är större än en inte kan ha sina infallande kanter lika fördelade runt dem. Icke desto mindre har varje ytterplanär graf med maximal grad d en ytterplanarritning med vinkelupplösning proportionell mot 1/ d .

Plana grafer

För plana grafer med maximal grad d , fyrkantsfärgningstekniken av Formann et al. (1993) tillhandahåller en ritning med vinkelupplösning proportionell mot 1/ d , eftersom kvadraten på en plan graf måste ha ett kromatiskt tal proportionellt mot d . Närmare bestämt antog Wegner 1977 att det kromatiska talet för kvadraten i en plan graf som mest är $\max \left(d+5,{\frac {3d }{2}}+1\right)$ , och det är känt att det kromatiska talet är högst ${\frac {5d}{3}}+O(1)$ . Ritningarna som härrör från denna teknik är emellertid i allmänhet inte plana.

För vissa plana grafer är den optimala vinkelupplösningen för en plan rätlinjeritning O(1/ d ³ ) , där d är graden av grafen. Dessutom kan en sådan ritning tvingas använda mycket långa kanter, längre med en exponentiell faktor än de kortaste kanterna i ritningen. Malitz & Papakostas (1994) använde cirkelpackningssatsen och ringlemma för att visa att varje plan graf med maximal grad d har en plan ritning vars vinkelupplösning i värsta fall är en exponentiell funktion av d , oberoende av antalet hörn i grafen.

Beräkningskomplexitet

Det är NP-svårt att avgöra om en given graf med maximal grad d har en ritning med vinkelupplösning 2π/ d , även i det speciella fallet att d = 4 . För vissa begränsade klasser av ritningar, inklusive ritningar av träd där utvidgning av löven till oändligheten ger en konvex indelning av planet samt ritningar av plana grafer där varje avgränsad yta är en centralsymmetrisk polygon, en ritning av optimal vinkelupplösning kan hittas i polynomtid .

Historia

Vinkelupplösning definierades först av Formann et al. (1993) .

Även om de ursprungligen endast definierades för rätlinjiga ritningar av grafer, har senare författare också undersökt vinkelupplösningen för ritningar där kanterna är polygonala kedjor, cirkulära bågar eller splinekurvor.

En grafs vinkelupplösning är nära relaterad till dess korsningsupplösning, den vinkel som bildas av korsningar i en ritning av grafen. I synnerhet RAC-ritningen säkerställa att dessa vinklar är alla räta vinklar , den största möjliga korsningsvinkeln.

Anteckningar

•   Brandes, Ulrik ; Shubina, Galina; Tamassia, Roberto (2000), "Improving angular resolution in visualizations of geographic networks", Data Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization i Amsterdam, Nederländerna, 29-31 maj 2000 , doi : 10.1000 978-3-7091-6783-0_3 , ISBN 9783211835159 .
•   Carlson, Josiah; Eppstein, David (2007), "Träd med konvexa ytor och optimala vinklar", i Kaufmann, Michael; Wagner, Dorothea (red.), Proc. 14:e Int. Symp. Graph Drawing (GD'06) , LNCS, vol. 4372, Springer-Verlag, s. 77–88, arXiv : cs.CG/0607113 , doi : 10.1007/978-3-540-70904-6_9 , S2CID 12598338 .
• Cheng, CC; Duncan, CA; Goodrich, MT ; Kobourov, SG (1999), "Drawing planar graphs with circular arcs", Graph Drawing, 7th International Symposium, GD'99, Štirín Castle, Tjeckien 15–19 september 1999, Proceedings , Lecture Notes in Computer Science , vol. 1731, Springer-Verlag, s. 117–126, doi : 10.1007/3-540-46648-7_12 .
• Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2009), "Drawing graphs with right angle crossings", Algorithms and Data Structures : 11th International Symposium, WADS 2009, Banff, Kanada, 21-23 augusti 2009. Proceedings , Lecture Notes in Computer Science, vol. 5664, s. 206–217, doi : 10.1007/978-3-642-03367-4_19 .
• Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T. ; Kobourov, Stephen G.; Nöllenburg, Martin (2011), "Att rita träd med perfekt vinkelupplösning och polynomarea", i Brandes, Ulrik; Cornelsen, Sabine (red.), Proc. 18:e Int. Symp. Graph Drawing , Lecture Notes in Computer Science, vol. 6502, Springer-Verlag, s. 183–194, arXiv : 1009.0581 , doi : 10.1007/978-3-642-18469-7_17 .
•   Eppstein, D .; Wortman, K. (2011), "Optimal angular resolution for face-symmetric drawings", Journal of Graph Algorithms and Applications , 15 (4): 551–564, arXiv : 0907.5474 , doi : 10.7155/jgaa.0026431 , S3C6431 , S3C6431 , S3C6431 , S3C5642 .
• Finkel, Benjamin; Tamassia, Roberto (2005), "Curvilinear graph drawing using the force-directed method", Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, 29 september-2 oktober 2004, Revised Selected Papers , Lecture Notes i datavetenskap, vol. 3383, Springer-Verlag, s. 448–453, doi : 10.1007/978-3-540-31843-9_46 .
•   Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E .; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing , 22 (5): 1035–1052, doi : 10.1137/0222063 , MR 1237161 .
• Garg, Ashim; Tamassia, Roberto (1994), "Planar drawings and angular resolution: Algorithms and bounds", Algorithms, Second Annual European Symposium, Utrecht, Nederländerna, 26–28 september 1994, Proceedings , Lecture Notes in Computer Science, vol. 855, Springer-Verlag, s. 12–23, doi : 10.1007/BFb0049393 .
• Garg, Ashim; Tamassia, Roberto (1995), "Om beräkningskomplexiteten av uppåtriktad och rätlinjig planaritetstestning", i Tamassia, Roberto; Tollis, Ioannis (red.), Graph Drawing , Lecture Notes in Computer Science, vol. 894, Springer Berlin / Heidelberg, s. 286–297, doi : 10.1007/3-540-58950-3_384 .
•   Gutwenger, Carsten; Mutzel, Petra (1998), "Planar polyline drawings with good angular resolution", Graph drawing (Montréal, QC, 1998) , Lecture Notes in Comput. Sci., vol. 1547, Berlin: Springer, s. 167–182, doi : 10.1007/3-540-37623-2_13 , MR 1717450 .
• Halupczok, Immanuel; Schulz, André (2011), "Nålning av ballonger med perfekta vinklar och optimal yta", Proceedings of the 19th International Symposium on Graph Drawing .
•   Kant, G. (1996), "Drawing planar graphs using the canonical ordering", Algorithmica , 16 (1): 4–32, doi : 10.1007/s004539900035 , hdl : 1874/16676 9 , MR 491 3 .
•   Kramer, Florica; Kramer, Horst (2008), "A survey on the distance-colouring of graphs", Discrete Mathematics , 308 (2–3): 422–426, doi : 10.1016/j.disc.2006.11.059 , MR 2378044 .
•   Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics , 7 (2): 172–183, doi : 10.1137/S0895480193242931 , MR 1271989 .
•   Molloy, Michael; Salavatipour, Mohammad R. (2005), "A bound on the chromatic number of the square of a planar graph", Journal of Combinatorial Theory , Series B, 94 (2): 189–213, doi : 10.1016/j.jctb. 2004.12.005 , hdl : 1807/9473 , MR 2145512 .