Circle graph
આલેખ સિદ્ધાંતમાં, વર્તુળ આલેખ એ તાર આકૃતિનો આંતરછેદ આલેખ છે. એટલે કે, તે એક દિશાહીન આલેખ છે, જેના શિરોબિંદુઓ વર્તુળની તારોની મર્યાદિત પ્રણાલી સાથે સંકળાયેલા હોઈ શકે છે, જેમ કે જો અને માત્ર ત્યારે જ બે શિરોબિંદુઓ અડીને હોય જો અનુરૂપ તારો એકબીજાને પાર કરે. એલ્ગોરિધમિક જટિલતા ઓ (એન 2)-ટાઇમ અલ્ગોરિધમ આપે છે જે પરીક્ષણ કરે છે કે આપેલ એન-વર્ટેક્સ દિશાહીન આલેખ એક વર્તુળ આલેખ છે કે કેમ અને, જો તે હોય, તો તેને રજૂ કરતી તારોનો સમૂહ બનાવે છે. સામાન્ય આલેખ પર એન. પી.-પૂર્ણ હોય તેવી સંખ્યાબંધ અન્ય સમસ્યાઓ જ્યારે વર્તુળ આલેખ સુધી મર્યાદિત હોય ત્યારે બહુપદી સમય અલ્ગોરિધમ્સ ધરાવે છે. દાખલા તરીકે, દર્શાવ્યું કે વર્તુળ આલેખની ત્રિ-પહોળાઈ નક્કી કરી શકાય છે, અને O (n3) સમયમાં વૃક્ષનું શ્રેષ્ઠ વિઘટન બને છે. વધુમાં, ઓ (એન3) સમયમાં લઘુતમ ભરણ (એટલે કે, શક્ય તેટલી ઓછી ધાર સાથેનો કોર્ડલ ગ્રાફ જેમાં સબગ્રાફ તરીકે આપેલ વર્તુળ ગ્રાફ હોય છે) મળી શકે છે. દર્શાવ્યું છે કે વર્તુળ આલેખનો મહત્તમ સમૂહ O (n log2n) સમયમાં મળી શકે છે, જ્યારે દર્શાવ્યું છે કે ભારરહિત વર્તુળ આલેખનો મહત્તમ સ્વતંત્ર સમૂહ O (n મિનિટ {d, α}) સમયમાં મળી શકે છે, જ્યાં d એ તેની ઘનતા તરીકે ઓળખાતા આલેખનો પરિમાણ છે, અને α એ વર્તુળ આલેખની સ્વતંત્ર સંખ્યા છે. જો કે, એવી સમસ્યાઓ પણ છે જે વર્તુળ આલેખ સુધી મર્યાદિત હોય ત્યારે એન. પી.-પૂર્ણ રહે છે. આમાં લઘુતમ પ્રભુત્વ ધરાવતો સમૂહ, લઘુતમ જોડાણ ધરાવતો પ્રભુત્વ ધરાવતો સમૂહ અને લઘુતમ કુલ પ્રભુત્વ ધરાવતો સમૂહ સમસ્યાઓનો સમાવેશ થાય છે. રંગીન સંખ્યા વર્તુળ આલેખની રંગીન સંખ્યા એ રંગોની લઘુતમ સંખ્યા છે જેનો ઉપયોગ તેના તારોને રંગવા માટે કરી શકાય છે જેથી કોઈ પણ બે પાર કરતા તારોનો રંગ સમાન ન હોય. વર્તુળ આલેખ બનાવવાનું શક્ય હોવાથી જેમાં આપખુદ રીતે તારોના મોટા સમૂહો એકબીજાને પાર કરે છે, વર્તુળ આલેખની રંગીન સંખ્યા આપખુદ રીતે મોટી હોઈ શકે છે, અને વર્તુળ આલેખની રંગીન સંખ્યા નક્કી કરવી એ એન. પી.-પૂર્ણ છે. વર્તુળ આલેખ ચાર રંગોથી રંગીન થઈ શકે છે કે કેમ તે ચકાસવા માટે તે એન. પી.-પૂર્ણ રહે છે. દાવો કરવામાં આવ્યો હતો કે ત્રણ રંગો સાથે રંગ શોધવો બહુપદી સમયમાં થઈ શકે છે પરંતુ આ પરિણામના તેમના લખાણમાં ઘણી વિગતો અવગણવામાં આવી છે. કેટલાક લેખકોએ વર્તુળ આલેખના મર્યાદિત પેટા વર્ગોને થોડા રંગોથી રંગવાની સમસ્યાઓની તપાસ કરી છે. ખાસ કરીને, વર્તુળ આલેખ માટે જેમાં k અથવા વધુ તારોનો કોઈ સમૂહ એકબીજાને પાર કરતો નથી, આલેખને ઓછા રંગોથી રંગવાનું શક્ય છે. આ કહેવાની એક રીત એ છે કે વર્તુળ આલેખ-બાઉન્ડેડ છે. ચોક્કસ કિસ્સામાં જ્યારે k = 3 (એટલે કે, ત્રિકોણ-મુક્ત વર્તુળ આલેખ માટે) રંગીન સંખ્યા વધુમાં વધુ પાંચ હોય છે, અને આ ચુસ્ત હોય છેઃ બધા ત્રિકોણ-મુક્ત વર્તુળ આલેખ પાંચ રંગોથી રંગીન હોઈ શકે છે, અને ત્રિકોણ-મુક્ત વર્તુળ આલેખ અસ્તિત્વ ધરાવે છે જેને પાંચ રંગોની જરૂર હોય છે. જો વર્તુળ આલેખમાં ઓછામાં ઓછો પાંચ ઘેરો હોય (એટલે કે, તે ત્રિકોણ-મુક્ત હોય અને તેમાં કોઈ ચાર-અક્ષતંતુ ચક્ર ન હોય) તો તેને મહત્તમ ત્રણ રંગોથી રંગીન કરી શકાય છે. ત્રિકોણ-મુક્ત સ્ક્વેરગ્રાફને રંગવાની સમસ્યા વૃક્ષોના કાર્ટેશિયન ઉત્પાદનોના આઇસોમેટ્રિક સબગ્રાફ તરીકે સ્ક્વેરગ્રાફને રજૂ કરવાની સમસ્યાની સમકક્ષ છે; આ પત્રવ્યવહારમાં, રંગમાં રંગોની સંખ્યા ઉત્પાદનની રજૂઆતમાં વૃક્ષોની સંખ્યાને અનુરૂપ છે. એપ્લિકેશન્સ વર્તુળ આલેખ વી. એલ. એસ. આઈ. ભૌતિક ડિઝાઇનમાં વાયર રાઉટીંગ માટેના વિશેષ કેસ માટે અમૂર્ત રજૂઆત તરીકે ઉદભવે છે, જેને "બે-ટર્મિનલ સ્વીચબોક્સ રાઉટીંગ" તરીકે ઓળખવામાં આવે છે. આ કિસ્સામાં રાઉટીંગ વિસ્તાર એક લંબચોરસ છે, બધી જાળી બે-ટર્મિનલ છે, અને ટર્મિનલ લંબચોરસની પરિમિતિ પર મૂકવામાં આવે છે. તે સરળતાથી જોઈ શકાય છે કે આ જાળીનો આંતરછેદ આલેખ એક વર્તુળ આલેખ છે. વાયર રાઉટીંગ પગલાના લક્ષ્યાંકો પૈકી એ સુનિશ્ચિત કરવાનું છે કે વિવિધ જાળીઓ વિદ્યુત રીતે ડિસ્કનેક્ટ રહે, અને તેમના સંભવિત આંતરછેદના ભાગો વિવિધ વાહક સ્તરોમાં નાખવા જોઈએ. તેથી વર્તુળ આલેખ આ રૂટીંગ સમસ્યાના વિવિધ પાસાઓને મેળવે છે. વર્તુળ આલેખના રંગોનો ઉપયોગ મનસ્વી આલેખના પુસ્તક એમ્બેડિંગ શોધવા માટે પણ થઈ શકે છેઃ જો આપેલ આલેખ G ના શિરોબિંદુઓ વર્તુળ પર ગોઠવાયેલા હોય, તો G ની ધાર વર્તુળની કોર્ડ બનાવે છે, પછી આ કોર્ડનો આંતરછેદ આલેખ એક વર્તુળ આલેખ છે અને આ વર્તુળ આલેખના રંગો પુસ્તક એમ્બેડિંગની સમકક્ષ છે જે આપેલ ગોળાકાર લેઆઉટને માન આપે છે. આ સમાનતામાં, રંગમાં રંગોની સંખ્યા પુસ્તક એમ્બેડિંગમાં પૃષ્ઠોની સંખ્યાને અનુરૂપ છે. સંબંધિત આલેખ વર્ગો આલેખ એ વર્તુળ આલેખ છે જો અને માત્ર ત્યારે જ જો તે રેખા પરના અંતરાલોના સમૂહનો ઓવરલેપ આલેખ હોય. આ એક આલેખ છે જેમાં શિરોબિંદુઓ અંતરાલને અનુરૂપ હોય છે, અને જો બે અંતરાલો ઓવરલેપ થાય તો બે શિરોબિંદુઓ એક ધાર દ્વારા જોડાયેલા હોય છે, જેમાં ન તો અન્ય હોય છે. રેખા પરના અંતરાલોના સમૂહના આંતરછેદના આલેખને અંતરાલ આલેખ કહેવામાં આવે છે. સ્ટ્રિંગ આલેખ, સમતલમાં વળાંકના આંતરછેદ આલેખ, એક વિશેષ કેસ તરીકે વર્તુળ આલેખનો સમાવેશ કરે છે. દરેક અંતર-વારસાગત આલેખ એક વર્તુળ આલેખ છે, જેમ કે દરેક ક્રમચય આલેખ અને દરેક ઉદાસીનતા આલેખ છે. દરેક બાહ્ય સમતલ આલેખ પણ એક વર્તુળ આલેખ છે. વર્તુળ આલેખને બહુકોણ-વર્તુળ આલેખ દ્વારા સામાન્યીકૃત કરવામાં આવે છે, બહુકોણના આંતરછેદ આલેખ બધા એક જ વર્તુળમાં અંકિત છે. નોંધો સંદર્ભો. . . . . . . જેમ ટાંકવામાં આવ્યું છે. . જેમ ટાંકવામાં આવ્યું છે. . જેમ ટાંકવામાં આવ્યું છે. . . . . જેમ ટાંકવામાં આવ્યું છે. . . . . . . . જેમ ટાંકવામાં આવ્યું છે. વર્તુળો આલેખના આંતરછેદના વર્ગો ભૌમિતિક આલેખ