Antal grafhældninger

I grafvisualisering og geometrisk grafteori , er antallet af hældninger i en graf det mindst mulige antal forskellige hældningskoefficienter af kanter i en tegning af en graf, hvor toppunkter er repræsenteret af punkter i den euklidiske plan og kanter er segmenter som ikke passerer gennem hjørner, der ikke falder ind i disse kanter.

Komplet grafer

Selvom beslægtede problemer i kombinatorisk geometri er blevet undersøgt før (Scott i 1970 og Jamison i 1984), blev problemet med at bestemme antallet af hældninger i en graf stillet af Wade og Chu [1] , hvilket viser, at antallet af hældninger i en graf med n toppunkter af en komplet graf er K n nøjagtigt n . En tegning af en graf med et sådant antal hældninger kan fås ved at placere grafens spidser i hjørnerne af en regulær polygon .

Sammenhæng med graden af ​​grafen

Det er klart, at antallet af hældninger af en graf med maksimal grad d er mindst , da højst to indfaldende kanter af et toppunkt af grad d kan ligge på samme linje (har en hældning). Mere præcist er antallet af skråninger ikke mindre end den lineære trævirkelighed af grafen , da kanterne af den samme hældning skal danne en lineær skov, og den lineære træplantning til gengæld ikke må være mindre end .

Der er grafer med en maksimal grad på fem, der har et vilkårligt stort antal hældninger [2] . Enhver graf med maksimal grad tre har dog højst fire hældninger [3] . Resultatet af Wade og Chu (1994 ) for den komplette graf K 4 viser, at denne grænse er skarp. Ikke et sæt med fire hældninger er egnet til at tegne alle grafer af grad 3 - et sæt hældninger er egnet til at tegne, hvis og kun hvis de er hældningerne af siderne og diagonalerne i parallelogrammet . Især kan enhver graf af grad 3 tegnes, så dens kanter enten er parallelle med akserne eller parallelle med heltalsgitterets hoveddiagonaler [ 4] . Det er ukendt, hvorvidt antallet af hældninger af grafer med en maksimal grad på fire er afgrænset [5] .

Plane grafer

Som Keszegh, Pach, Pálvölgyi (2011 ) har vist, har enhver plan graf et fladt linjesegmentmønster, hvor antallet af forskellige hældninger er en funktion af grafens grad. Deres bevis følger konstruktionen af ​​Malitz og Papakostas ( Malitz, Papakostas (1994 )) for at begrænse vinkelopløsningen af ​​plane grafer som funktion af grad. Gradbegrænsning udføres ved at forstærke grafen til en maksimal plan graf uden at øge dens grad med mere end en konstant faktor, og derefter anvende cirkelpakningssætningen til at repræsentere denne udvidede graf som et sæt tangentcirkler. Hvis graden af ​​den oprindelige graf er afgrænset, vil forholdet mellem radierne af tilstødende cirkler i pakningen også være afgrænset [7] , hvilket igen indebærer, at anvendelse af et quadtree på alle grafens hjørnepunkter i et punkt inde i cirklen giver hældninger, der er forhold mellem små heltal. Antallet af forskellige hældninger opnået i denne konstruktion er en eksponent for graden af ​​grafen.

Sværhedsgrad

Problemet med at bestemme om antallet af hældninger er lig med to er NP-komplet [8] [9] [10] . Dette indebærer, at det er et NP-svært problem at bestemme antallet af hældninger på en vilkårlig graf eller at tilnærme dette tal med en garanteret effektivitet bedre end 3/2.

Om en plan graf er en plan tegning med to hældninger er også et NP-komplet problem [11] .

Noter

  1. ↑ Wade, Chu, 1994 .
  2. ↑ Bevist uafhængigt af Barat, Matoušek, Wood (2006 ) og Pach, Pálvölgyi (2006 ), da de løste problemet fra Dujmovic, Suderman og Sharir ( Dujmović, Suderman, Wood (2005) ). Se sætning 5.1 og 5.2 i Pach og Sharir ( Pach og Sharir (2009 )).
  3. ↑ Mukkamala , Szegedy (2009 ), som forbedrede det tidligere resultat af Keszegh, Pálvölgyi, Tóth (2008 )). Se Pach og Sharirs sætning 5.3 ( Pach og Sharir (2009 )).
  4. ↑ Mukkamala, Pálvölgyi, 2012 .
  5. ↑ Pach, Sharir, 2009 .
  6. ↑ Keszegh, Pach, Pálvölgyi, 2011 .
  7. ↑ Hansen, 1988 .
  8. ↑ Formann, Hagerup, Haralambides, Kaufmann, 1993 .
  9. ↑ Eades, Hong, Poon, 2010 .
  10. ↑ Maňuch, Patterson, Poon, Thachuk, 2011 .
  11. ↑ Garg, Tamassia, 2001 .

Litteratur