Cirkeldiagram - Circle graph

För diagrammet, se cirkeldiagram .
En cirkel med fem ackord och motsvarande cirkeldiagram.

I grafteori , en cirkel graf är skärnings grafen av en uppsättning av ackord av en cirkel . Det vill säga det är en oriktad graf vars hörn kan associeras med ackord i en cirkel så att två hörn är intill om och endast om motsvarande ackord korsar varandra.

Algoritmisk komplexitet

Spinrad (1994) ger en O ( n 2 ) -tid algoritm som testar huruvida en given n -vertex oriktad graf är en cirkel grafen och, om det är, konstruerar en uppsättning ackord som representerar det.

Ett antal andra problem som är NP-kompletta i allmänna grafer har polynomiska tidsalgoritmer när de är begränsade till cirkeldiagram. Till exempel visade Kloks (1996) att trebredden för en cirkeldiagram kan bestämmas, och en optimal trädnedbrytning kan konstrueras på O ( n 3 ) -tid. Dessutom kan ett minimiutfyllnad (det vill säga ett ackorddiagram med så få kanter som möjligt som innehåller den angivna cirkeldiagrammet som en subgraf) hittas på O ( n 3 ) -tid. Tiskin (2010) har visat att en maximal klick av en cirkeldiagram kan hittas på O ( n log 2 n ) tid, medan Nash & Gregg (2010) har visat att en maximal oberoende uppsättning av en obevägad cirkeldiagram kan hittas i O ( n min { d , α }) tid, där d är en parameter i grafen som kallas dess densitet, och α är cirkelgrafens oberoende nummer.

Det finns dock också problem som förblir NP-kompletta när de är begränsade till cirkeldiagram. Dessa inkluderar minsta dominerande uppsättning , minsta anslutna dominerande uppsättning och minsta totala dominerande uppsättningsproblem.

Kromatiskt nummer

Akkorden som bildar 220-vertex 5-kromatisk triangelfri cirkeldiagram över Ageev (1996) , ritade som ett linjearrangemang i det hyperboliska planet .

Det kromatiska antalet i en cirkeldiagram är det minsta antalet färger som kan användas för att färga ackorden så att inga två korsande ackord har samma färg. Eftersom det är möjligt att bilda cirkeldiagram där godtyckligt stora uppsättningar av ackord korsar varandra kan det kromatiska antalet i ett cirkeldiagram vara godtyckligt stort, och bestämning av det kromatiska antalet i ett cirkeldiagram är NP-komplett. Det är fortfarande NP-komplett för att testa om ett cirkeldiagram kan färgas med fyra färger. Unger (1992) hävdade att det att hitta en färgning med tre färger kan göras på polynomisk tid men hans skrivning av detta resultat utelämnar många detaljer.

Flera författare har undersökt problem med att färga begränsade underklasser av cirkeldiagram med få färger. I synnerhet för cirkeldiagram där inga uppsättningar k eller flera ackord korsar varandra är det möjligt att färga grafen med så få som färger. Ett sätt att säga detta är att cirkeldiagrammen är -bundna . I det särskilda fallet när k  = 3 (det vill säga för triangelfria cirkeldiagram) är det kromatiska talet högst fem, och detta är tätt: alla triangelfria cirkeldiagram kan vara färgade med fem färger, och det finns triangel- fria cirkeldiagram som kräver fem färger. Om en cirkel graf har omkrets minst fem (det vill säga det triangel-fri och har inga fyra vertex cykler) Det kan färgas med högst tre färger. Problemet med att färglägga triangelfria kvadratgrafer motsvarar problemet med att representera kvadratgrafer som isometriska delbilder av kartesiska produkter av träd ; i denna korrespondens motsvarar antalet färger i färgen antalet träd i produktrepresentationen.

Applikationer

Cirkeldiagram uppstår i VLSI- fysisk design som en abstrakt representation för ett speciellt fall för ledningsdragning , känd som "tvåterminal switchbox routing ". I detta fall är dirigeringsområdet en rektangel, alla nät är två-terminala och terminalerna placeras på rektangelns omkrets. Det är lätt att se att korsningsdiagrammet för dessa nät är en cirkeldiagram. Bland målen för tråddragningssteget är att säkerställa att olika nät förblir elektriskt frånkopplade och att deras potentiella korsande delar måste läggas i olika ledande lager. Därför fångar cirkeldiagram olika aspekter av detta routingproblem.

Färgning av cirkeldiagram kan också användas för att hitta inbäddningar av godtyckliga grafer i boken : om hörnpunkterna i en given graf G är ordnade på en cirkel, med kanterna på G som bildar ackord i cirkeln, är skärningspunkten för dessa ackord en cirkeldiagram och färgläggningar av denna cirkeldiagram motsvarar bokinbäddningar som respekterar den givna cirkulära layouten. I denna ekvivalens motsvarar antalet färger i färgen antalet sidor i bokbäddningen.

Relaterade diagramklasser

Ett intervallsystem med fem intervall och motsvarande överlappningsdiagram.

Ett diagram är ett cirkeldiagram om och endast om det är överlappningsdiagrammet för en uppsättning intervall på en linje. Detta är ett diagram i vilket hörnpunkterna motsvarar intervallen, och två hörn är förbundna med en kant om de två intervallen överlappar varandra, och ingen av dem innehåller det andra.

Den skärnings graf av en uppsättning av intervaller på en linje kallas intervall grafen .

Strängdiagram , skärningsdiagrammen för kurvor i planet, inkluderar cirkeldiagram som ett specialfall.

Varje avstånds-ärftlig graf är ett cirkeldiagram, liksom varje permutationsdiagram och varje likgiltighetsdiagram . Varje ytterplan är också ett cirkeldiagram.

Varje cirkeldiagram är ett polygoncirkeldiagram .

Anteckningar

Referenser

externa länkar