Vinkelopløsning (grafteori)

Vinkelopløsningen af ​​en graftegning refererer til den skarpeste vinkel dannet af to kanter, der mødes ved samme toppunkt i tegningen.

Egenskaber

Forholdet til vertex grad

Foreman et al . [1] bemærkede, at enhver tegning af en graf med segmentkanter med maksimal grad d har en vinkelopløsning, der ikke overstiger - hvis v er et toppunkt med grad d , så deler de kanter, der falder ind på v rummet omkring toppunktet v. ind i d kiler med samlet vinkel , og den mindste af disse kiler skal have en vinkel, der ikke overstiger . Mere strengt, hvis grafen er d - regulær , skal den have en vinkelopløsning mindre end , da dette er den bedste opløsning, der kan opnås for et toppunkt på figurens konvekse skrog .

Forholdet til graffarvning

Som vist af Foreman et al . [1] er den størst mulige vinkelopløsning af en graf G tæt forbundet med det kromatiske tal på kvadratet på grafen G 2 , det vil sige en graf med det samme sæt toppunkter, hvor hver par af hjørner er forbundet med en kant, hvis afstanden mellem dem i grafen G ikke er over to. Hvis graf G 2 kan farves med farver, så kan G tegnes med vinkelopløsning for enhver , ved at tildele forskellige farver til hjørnerne af en regulær -gon og placere hvert hjørne af G ved siden af ​​en polygon toppunkt med samme farve. Ved hjælp af denne konstruktion viste de, at enhver graf med maksimal grad d har et mønster med en vinkelopløsning proportional med 1/ d 2 . Denne grænse er tæt på nøjagtig - de brugte en probabilistisk metode til at bevise eksistensen af ​​grafer med en maksimal grad af d , hvis tegninger alle har vinkelopløsning .

Eksistens af optimale mønstre

Forman et al . [1] gav et eksempel, der viser, at der er grafer, der ikke har mønstre med den maksimalt mulige vinkelopløsning. Tværtimod har disse grafer en familie af tegninger, hvis vinkelopløsninger har en tendens til en vis begrænset værdi, men ikke når den. Specifikt præsenterede de en graf med 11 toppunkter, der har et mønster med en vinkelopløsning på enhver , men ikke har et mønster med en vinkelopløsning på nøjagtigt .

Særlige klasser af grafer

Træer

Ethvert træ kan tegnes på en sådan måde, at kanterne er jævnt fordelt rundt om hvert vertex, en egenskab kendt som perfekt vinkelopløsning . Desuden, hvis kanterne frit kan permuteres rundt om hvert toppunkt, så er et sådant mønster muligt uden skæringer med kanter af længde en eller flere, og hele mønsteret placeres i et polynomisk områderektangel . Men hvis den cirkulære rækkefølge af kanterne omkring hvert toppunkt allerede er specificeret som en del af problemformuleringen, så kan opnåelse af en vinkelopløsning uden krydsninger nogle gange kræve et eksponentielt areal [2] [3] .

Yderplanære grafer

Perfekt vinkelopløsning er ikke altid mulig for ydreplanære grafer , da hjørner på det konvekse skrog af et mønster med en grad større end én ikke kan have kanter, der falder ind på det jævnt fordelt rundt om vertexet. Imidlertid har enhver ydreplanær graf med maksimal grad d en ydreplantegning med en vinkelopløsning proportional med 1/ d [4] [5] .

Plane grafer

For plane grafer med maksimal grad d , producerer Foremans (et al.) grafkvadratfarveteknik [1] en tegning med en vinkelopløsning proportional med 1/ d , da kvadratet på en plan graf skal have et kromatisk tal proportionalt med d . Wegner formodede i 1977, at det kromatiske tal for kvadratet af en plan graf ikke overstiger , og det er kendt, at det kromatiske tal ikke overstiger [6] [7] . Imidlertid er mønsteret opnået ved denne teknik generelt ikke plant.

For nogle plane grafer er den optimale vinkelopløsning af en plan tegning med linjestykker O(1/ d 3 ) , hvor d er graden af ​​grafen [5] . Derudover kan sådanne mønstre være tvunget til at have meget lange kanter, længere end den eksponentielle faktor fra den korteste kant af mønsteret. Malitz og Papakostas [4] brugte cirkelpakningssætningen til at vise, at enhver plan graf med maksimal grad d har et plant mønster, hvis værst tænkelige vinkelopløsning er en eksponentiel funktion af d og uafhængig af antallet af grafens toppunkter.

Beregningsmæssig kompleksitet

Problemet med at afgøre, om en given graf med maksimal grad d har et mønster med vinkelopløsning , er NP-hårdt selv i det specielle tilfælde d =4 [1] [8] . Men for nogle begrænsede klasser af tegninger, herunder tegninger af træer, hvor forlængelsen af ​​blade til det uendelige giver en konveks skillevæg af planet, samt tegninger af plane grafer, hvor hver afgrænset flade er en centralt symmetrisk polygon, en tegning med optimal vinkelopløsning kan findes i polynomisk tid [9] [10] .

Historie

Vinkelopløsning blev bestemt af Forman et al . [1] .

Selvom det oprindeligt blev defineret til tegninger af grafer med lige kanter, undersøgte senere forfattere vinkelopløsningen af ​​tegninger, hvor kanterne er polygonale [11] [12] , cirkulære buer [13] [2] eller splines [14] [15] .

Vinkelopløsningen af ​​en graf er tæt forbundet med dens skæringsopløsning, vinklerne dannet af skæringspunkterne i graftegningen. Især tegning af grafer i rette vinkler leder efter en repræsentation, der sikrer, at alle disse vinkler er rette vinkler , hvilket er den størst mulige skæringsvinkel [16]

Noter

  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