Antal graflutningar

I grafvisualisering och geometrisk grafteori , är antalet lutningar i en graf det minsta möjliga antalet olika lutningskoefficienter för kanter i en ritning av en graf där hörn representeras av punkter på det euklidiska planet och kanter är segment som inte passerar genom hörn som inte faller in mot dessa kanter.

Kompletta grafer

Även om relaterade problem inom kombinatorisk geometri har studerats tidigare (Scott 1970 och Jamison 1984), ställdes problemet med att bestämma antalet lutningar i en graf av Wade och Chu [1] , vilket visar att antalet lutningar i en graf med n hörn av en komplett graf är K n exakt n . En ritning av en graf med ett sådant antal lutningar kan erhållas genom att placera grafens hörn i hörnen av en vanlig polygon .

Samband med graden av grafen

Det är tydligt att antalet lutningar i en graf med maximal grad d är minst , eftersom högst två infallande kanter av en vertex av grad d kan ligga på samma linje (har en lutning). Mer exakt är antalet sluttningar inte mindre än grafens linjära arborealitet , eftersom kanterna på samma sluttning måste bilda en linjär skog, och den linjära arborescensen får i sin tur inte vara mindre än .

Det finns grafer med en maxgrad på fem som har ett godtyckligt stort antal lutningar [2] . Men varje graf med maximal grad tre har som mest fyra lutningar [3] . Resultatet av Wade och Chu (1994 ) för hela grafen K 4 visar att denna gräns är skarp. Ingen uppsättning med fyra lutningar är lämpliga för att rita alla grafer av grad 3 - en uppsättning lutningar är lämplig för att rita om och endast om de är lutningarna på parallellogrammets sidor och diagonaler . I synnerhet kan vilken graf som helst av grad 3 ritas så att dess kanter antingen är parallella med axlarna eller parallella med heltalsgittrets huvuddiagonaler [4] . Det är okänt huruvida antalet lutningar av grafer med en maximal grad av fyra är begränsat [5] .

Plana grafer

Som Keszegh, Pach, Pálvölgyi (2011 ) har visat har varje plan graf ett platt linjesegmentmönster där antalet olika lutningar är en funktion av grafens grad. Deras bevis följer konstruktionen av Malitz och Papakostas ( Malitz, Papakostas (1994 )) för att begränsa vinkelupplösningen för plana grafer som en funktion av graden. Gradbegränsning görs genom att utöka grafen till en maximal plan graf utan att öka dess grad med mer än en konstant faktor, och sedan tillämpa cirkelpackningssatsen för att representera denna utökade graf som en uppsättning tangentcirklar. Om graden av den initiala grafen är avgränsad, kommer förhållandet mellan radierna för intilliggande cirklar i packningen också att begränsas [7] , vilket i sin tur innebär att applicering av ett fyrträd på alla grafens hörn i en punkt inuti cirkeln ger lutningar som är förhållanden mellan små heltal. Antalet olika lutningar som erhålls i denna konstruktion är en exponent för graden av grafen.

Svårighet

Problemet med att avgöra om antalet backar är lika med två är NP-komplett [8] [9] [10] . Detta innebär att det är ett NP-svårt problem att bestämma antalet lutningar i en godtycklig graf eller att approximera detta antal med en garanterad effektivitet bättre än 3/2.

Huruvida en plan graf är en plan ritning med två lutningar är också ett NP-komplett problem [11] .

Anteckningar

  1. ↑ Wade, Chu, 1994 .
  2. ↑ Bevisas oberoende av Barat, Matoušek, Wood (2006 ) och Pach, Pálvölgyi (2006 ) när de löste problemet från Dujmovic, Suderman och Sharir ( Dujmović, Suderman, Wood (2005) ). Se satser 5.1 och 5.2 i Pach och Sharir ( Pach och Sharir (2009 )).
  3. ↑ Mukkamala , Szegedy (2009 ), som förbättrade det tidigare resultatet av Keszegh, Pálvölgyi, Tóth (2008 )). Se Pach och Sharirs sats 5.3 ( Pach och 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