Cirkulär layout

Cirkulär layout av Chvátal-grafen
Cirkulär layout av ett tillståndsdiagram för gränsgatewayprotokollet
Inkrementell konstruktion av en cirkulär layout för Barabási–Albert-modellen för bildande av sociala nätverk

I grafritning är en cirkulär layout en ritstil som placerar hörn av en graf på en cirkel , ofta jämnt fördelade så att de bildar hörn av en vanlig polygon .

Ansökningar

Cirkulära layouter passar bra för kommunikationsnätverkstopologier som stjärn- eller ringnät , och för de cykliska delarna av metaboliska nätverk . För grafer med en känd Hamiltonsk cykel tillåter en cirkulär layout att cykeln kan avbildas som cirkeln, och på så sätt utgör cirkulära layouter grunden för LCF-notationen för Hamiltonska kubiska grafer .

En cirkulär layout kan användas på egen hand för en hel grafritning, men den kan också användas som layout för mindre kluster av hörn inom en större grafritning, såsom dess dubbelkopplade komponenter, kluster av gener i en geninteraktionsgraf , eller naturliga undergrupper inom ett socialt nätverk . Om flera vertexcirklar används på detta sätt kan andra metoder som kraftriktad grafritning användas för att arrangera klustren.

En fördel med en cirkulär layout i vissa av dessa applikationer, såsom bioinformatik eller visualisering av sociala nätverk, är dess neutralitet: genom att placera alla hörn på lika avstånd från varandra och från mitten av ritningen, ges ingen en privilegierad position, vilket motverkar tittarnas tendens att uppfatta mer centralt belägna noder som viktigare.

Kantstil

Ritningens kanter kan avbildas som ackord av cirkeln, som cirkelbågar (möjligen vinkelräta mot vertexcirkeln, så att kanterna modellerar linjerna i Poincaré-skivans modell av hyperbolisk geometri ), eller som andra typer av kurvor.

Den visuella skillnaden mellan insidan och utsidan av vertexcirkeln i en cirkulär layout kan användas för att separera två olika stilar av kantritning. Till exempel använder en cirkulär ritningsalgoritm av Gansner & Koren (2007) kantbuntning inom cirkeln, tillsammans med några kanter som inte är buntade, ritade utanför cirkeln.

För cirkulära layouter av vanliga grafer , med kanter ritade både inuti och utanför som cirkulära bågar , är infallsvinkeln för en av dessa bågar med vertexcirkeln densamma i båda ändarna av bågen, en egenskap som förenklar optimeringen av vinkeln ritningens upplösning .

Antal korsningar

Flera författare har studerat problemet med att hitta en permutation av hörnen i en cirkulär layout som minimerar antalet kantkorsningar när alla kanter är ritade inuti vertexcirkeln. Detta antal korsningar är noll endast för ytterplanära grafer . För andra grafer kan den optimeras eller reduceras separat för varje bikopplad komponent i grafen innan lösningarna kombineras, eftersom dessa komponenter kan ritas så att de inte interagerar.

  I allmänhet är minimering av antalet korsningar NP-komplett , men kan approximeras med ett approximationsförhållande på O (log 2 n ) där n är antalet hörn. Heuristiska metoder för att reducera korsningskomplexiteten har också utarbetats, baserade t.ex. på en noggrann ordning för insättning av vertex och på lokal optimering .

En cirkulär layout kan också användas för att maximera antalet korsningar. I synnerhet, val av en slumpmässig permutation för hörn gör att varje möjlig korsning sker med sannolikhet 1/3, så det förväntade antalet korsningar är inom en faktor tre av det maximala antalet korsningar bland alla möjliga layouter. Att avrandomisera denna metod ger en deterministisk approximationsalgoritm med approximationsförhållande tre.

Andra optimeringskriterier

Tillsammans med korsningar har cirkulära versioner av problem med att optimera kanternas längder i en cirkulär layout, korsningarnas vinkelupplösning eller skärbredden (det maximala antalet kanter som förbinder en cirkelbåge med den motsatta bågen) övervägas, men många av dessa problem är NP-kompletta.

Se även

externa länkar

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Circular_layout&oldid=1117564853 "