Polygon-cirkel graf
I den matematiska disciplinen grafteori är en polygoncirkelgraf en skärningsgraf av en uppsättning konvexa polygoner vars alla hörn ligger på en gemensam cirkel. Dessa grafer har också kallats spindelgrafer . Denna klass av grafer föreslogs först av Michael Fellows 1988, motiverad av det faktum att den är stängd under kantkontraktion och inducerade subgrafoperationer .
En polygoncirkelgraf kan representeras som en "omväxlande sekvens". En sådan sekvens kan uppnås genom att störa polygonerna som representerar grafen (om nödvändigt) så att inte två delar en vertex, och sedan lista för varje vertex (i cirkulär ordning, med början vid en godtycklig punkt) polygonen som är fäst vid den vertexen.
Stängning under inducerade minderåriga
Att dra ihop en kant av en polygoncirkelgraf resulterar i en annan polygoncirkelgraf. En geometrisk representation av den nya grafen kan bildas genom att ersätta polygonerna som motsvarar de två ändpunkterna på den sammandragna kanten med deras konvexa skrov . Alternativt, i den alternerande sekvensen som representerar den ursprungliga grafen, ger kombination av delsekvenserna som representerar ändpunkterna för den sammandragna kanten till en enda delsekvens en alternerande sekvensrepresentation av den sammandragna grafen. Polygoncirkelgrafer stängs också under inducerade subgraf- eller motsvarande vertexraderingsoperationer: för att ta bort en vertex, ta bort dess polygon från den geometriska representationen eller ta bort dess underföljd av punkter från den alternerande sekvensen.
Erkännande
M. Koebe tillkännagav en polynomisk tidsigenkänningsalgoritm, men hans preliminära version hade "allvarliga fel" och en slutlig version publicerades aldrig. Martin Pergel visade senare att problemet med att känna igen dessa grafer är NP-komplett . Det är också NP-komplett att bestämma om en given graf kan representeras som en polygoncirkelgraf med högst k hörn per polygon, för någon k ≥ 3 .
Relaterade graffamiljer
Polygoncirkelgraferna är en generalisering av cirkelgraferna , som är skärningsgrafer för ackorden i en cirkel, och trapetsformade grafer , skärningsgrafer för trapetser som alla har sina hörn på samma två parallella linjer. De inkluderar också cirkelbågsgraferna .
Polygoncirkelgrafer är i allmänhet inte perfekta grafer , men de är nästan perfekta, i den meningen att deras kromatiska tal kan begränsas av en (exponentiell) funktion av deras klicknummer .