Planarity testing
આલેખ સિદ્ધાંતમાં, પ્લેનેરિટી પરીક્ષણ સમસ્યા એ પરીક્ષણની અલ્ગોરિધમિક સમસ્યા છે કે શું આપેલ આલેખ એક પ્લેનર ગ્રાફ છે (એટલે કે, તે ધાર આંતરછેદો વિના સમતલમાં દોરી શકાય છે કે કેમ). કોમ્પ્યુટર વિજ્ઞાનમાં આ એક સારી રીતે અભ્યાસ કરાયેલી સમસ્યા છે, જેના માટે ઘણા વ્યવહારુ અલ્ગોરિધમ્સ ઉભરી આવ્યા છે, જેમાંથી ઘણા નવા ડેટા સ્ટ્રક્ચરનો લાભ લઈ રહ્યા છે. આમાંની મોટાભાગની પદ્ધતિઓ O (n) સમય (રેખીય સમય) માં કાર્ય કરે છે, જ્યાં n એ આલેખમાં ધાર (અથવા શિરોબિંદુઓ) ની સંખ્યા છે, જે લક્ષણવિહીન રીતે શ્રેષ્ઠ છે. માત્ર એક બુલિયન મૂલ્ય બનવાને બદલે, જો આલેખ સમતલીય હોય, અથવા જો ન હોય તો કુરાટોવ્સ્કી સબગ્રાફ જેવા સમતલીયતા માટે અવરોધ હોય, તો સમતલીયતા પરીક્ષણ અલ્ગોરિધમનું આઉટપુટ સમતલીય આલેખ એમ્બેડિંગ હોઈ શકે છે. પ્લેનરટી માપદંડ પ્લેનરટી ટેસ્ટિંગ એલ્ગોરિધમ્સ સામાન્ય રીતે ગ્રાફ થિયરીમાં પ્રમેયોનો લાભ લે છે જે ગ્રાફ રેખાંકનોથી સ્વતંત્ર હોય તેવા સંદર્ભમાં પ્લેનર ગ્રાફના સમૂહને લાક્ષણિકતા આપે છે. આમાં કુરાટોવ્સ્કીના પ્રમેયનો સમાવેશ થાય છે કે આલેખ સમતલ હોય છે જો અને માત્ર ત્યારે જ જો તેમાં પેટા આલેખ ન હોય જે K5 (પાંચ શિરોબિંદુઓ પર સંપૂર્ણ આલેખ) અથવા K3,3 (ઉપયોગિતા આલેખ, છ શિરોબિંદુઓ પર સંપૂર્ણ દ્વિપક્ષી આલેખ હોય, જેમાંથી ત્રણ અન્ય ત્રણમાંથી દરેક સાથે જોડાય છે). વેગનરનો પ્રમેય કે આલેખ સમતલીય હોય છે જો અને માત્ર ત્યારે જ જો તેમાં નાનો (સંકોચનનો પેટા આલેખ) ન હોય જે K5 અથવા K3,3 માટે સમરૂપ હોય. ફ્રેસીક્સ-રોસેનસ્ટીહલ સમતલીયતાના માપદંડ, ઊંડાણ-પ્રથમ શોધ વૃક્ષમાં ધારની ડાબી-જમણી ક્રમના સંદર્ભમાં સમતલીય આલેખની લાક્ષણિકતા દર્શાવે છે. ફ્રેસીક્સ-રોસેનસ્ટીહલ પ્લેનેરિટી માપદંડનો ઉપયોગ પ્લેનેરિટી પરીક્ષણ માટે અલ્ગોરિધમ્સના ભાગ રૂપે સીધો જ થઈ શકે છે, જ્યારે કુરાટોવ્સ્કી અને વેગનરના પ્રમેયોમાં પરોક્ષ ઉપયોગો છેઃ જો કોઈ અલ્ગોરિધમ આપેલ ગ્રાફમાં K5 અથવા K3,3 ની નકલ શોધી શકે, તો તે ખાતરી કરી શકાય છે કે ઇનપુટ ગ્રાફ પ્લેનર નથી અને વધારાની ગણતરી વિના પરત આવે છે. અન્ય સમતલીયતા માપદંડ, જે ગણિતીય રીતે સમતલીય આલેખની લાક્ષણિકતા ધરાવે છે પરંતુ સમતલીયતા પરીક્ષણ અલ્ગોરિધમ્સ માટે ઓછા કેન્દ્રિય છે, તેમાં નીચેનાનો સમાવેશ થાય છેઃ વ્હિટનીનો સમતલીયતા માપદંડ કે ગ્રાફ સમતલીય છે જો અને માત્ર ત્યારે જ જો તેની ગ્રાફિક મેટ્રોઇડ પણ ભૌગોલિક હોય, મેક લેનનો સમતલીયતા માપદંડ સમતલીય આલેખને તેમના ચક્ર અવકાશના પાયા દ્વારા લાક્ષણિકતા આપે છે, સ્નેઇડરનો પ્રમેય સંકળાયેલ આંશિક ક્રમના ક્રમ પરિમાણ દ્વારા સમતલીય આલેખની લાક્ષણિકતા આપે છે, અને કોલિન ડી વર્ડીયરનો વર્ણપટ આલેખ સિદ્ધાંતનો ઉપયોગ કરીને સમતલીયતા માપદંડ. એલ્ગોરિધમ્સ પાથ એડિશન મેથડ હોપક્રોફ્ટ અને ટાર્જનની ક્લાસિક પાથ એડિશન મેથડ 1974માં પ્રથમ પ્રકાશિત રેખીય-સમય પ્લેનેરિટી પરીક્ષણ એલ્ગોરિધમ હતી. હોપક્રોફ્ટ અને ટાર્જનના અલ્ગોરિધમનો અમલ લાઇબ્રેરી ઓફ એફિશિયન્ટ ડેટા પ્રકારો અને અલ્ગોરિધમ્સમાં મેહલોર્ન, મુત્ઝેલ અને નાહેર દ્વારા પ્રદાન કરવામાં આવ્યો છે. 2012 માં, ટેલરે આ અલ્ગોરિધમનોને બાયકનેક્ટેડ ઘટકોના પ્લાનર એમ્બેડિંગ્સ માટે ચક્રીય ધાર-ક્રમના તમામ ક્રમચયો પેદા કરવા માટે વિસ્તૃત કર્યો. વર્ટેક્સ એડિશન પદ્ધતિ વર્ટેક્સ એડિશન પદ્ધતિઓ આપેલ ગ્રાફના પ્રેરિત સબગ્રાફના સંભવિત એમ્બેડિંગનું પ્રતિનિધિત્વ કરતી માહિતી માળખું જાળવી રાખીને અને આ માહિતી માળખામાં એક સમયે એક શિરોબિંદુ ઉમેરીને કામ કરે છે. આ પદ્ધતિઓ 1967માં લેમ્પેલ, ઇવન અને સેડરબૌમ દ્વારા કલ્પના કરાયેલી બિનકાર્યક્ષમ O (n2) પદ્ધતિથી શરૂ થઈ હતી. તેમાં ઇવન અને ટાર્જન દ્વારા સુધારો કરવામાં આવ્યો હતો, જેમણે ટી-ક્રમાંકન પગલા માટે રેખીય-સમય ઉકેલ શોધી કાઢ્યો હતો અને બૂથ અને લ્યુકર દ્વારા, જેમણે પી. ક્યુ. વૃક્ષ માહિતી માળખું વિકસાવ્યું હતું. આ સુધારાઓ સાથે તે રેખીય-સમય છે અને વ્યવહારમાં પાથ એડિશન પદ્ધતિને પાછળ છોડી દે છે. આ પદ્ધતિને પ્લાનર ગ્રાફ માટે પ્લાનર એમ્બેડિંગ (રેખાંકન) ને અસરકારક રીતે ગણતરી કરવાની મંજૂરી આપવા માટે પણ વિસ્તૃત કરવામાં આવી હતી. 1999માં, શિહ અને હ્સુએ પીસી વૃક્ષ (પી. ક્યુ. વૃક્ષનો મૂળ વગરનો પ્રકાર) અને શિરોબિંદુઓના ઊંડાઈ-પ્રથમ શોધ વૃક્ષના પોસ્ટઓર્ડર ટ્રાવર્સલનો ઉપયોગ કરીને આ પદ્ધતિઓને સરળ બનાવી. 2004માં, જ્હોન બોયર અને વેન્ડી માયર્વોલ્ડે એક સરળ ઓ (એન) અલ્ગોરિધમ વિકસાવ્યું હતું, જે મૂળરૂપે પી. ક્યુ. વૃક્ષ પદ્ધતિથી પ્રેરિત હતું, જે પી. ક્યુ. વૃક્ષને દૂર કરે છે અને જો શક્ય હોય તો પ્લાનર એમ્બેડિંગની ગણતરી કરવા માટે ધાર ઉમેરણોનો ઉપયોગ કરે છે. નહિંતર, કુરાટોવ્સ્કી પેટાવિભાગ (K5 અથવા K3,3 માંથી) ની ગણતરી કરવામાં આવે છે. આ આજે બે વર્તમાન અત્યાધુનિક અલ્ગોરિધમ્સમાંથી એક છે (બીજું ડી ફ્રેસીક્સ, ઓસોના ડી મેન્ડેઝ અને રોસેનસ્ટીહલનું પ્લેનેરિટી પરીક્ષણ અલ્ગોરિધમ છે). બોયર અને માયર્વોલ્ડ પ્લેનેરિટી ટેસ્ટના પ્રારંભિક સંસ્કરણ સાથે પ્રાયોગિક સરખામણી માટે જુઓ. વધુમાં, બોયર-મિરવોલ્ડ પરીક્ષણને આઉટપુટ કદ પર રેખીય રીતે નિર્ભર ચાલતા સમયમાં બિન-પ્લેનર ઇનપુટ ગ્રાફના બહુવિધ કુરાટોવ્સ્કી પેટાવિભાગોને બહાર કાઢવા માટે વિસ્તૃત કરવામાં આવ્યું હતું. પ્લેનેરિટી ટેસ્ટ અને બહુવિધ કુરાટોવ્સ્કી પેટાવિભાગોના નિષ્કર્ષણ માટેનો સ્રોત કોડ જાહેરમાં ઉપલબ્ધ છે. એલ્ગોરિધમ્સ કે જે શિરોબિંદુઓમાં રેખીય સમયમાં કુરાટોવ્સ્કી સબગ્રાફને સ્થિત કરે છે તે વિલિયમસન દ્વારા 1980ના દાયકામાં વિકસાવવામાં આવ્યા હતા. બાંધકામ અનુક્રમ પદ્ધતિ એક અલગ પદ્ધતિ G ના દરેક 3-જોડાયેલા ઘટક (અને તેથી G પોતે જ એક સમતલીય એમ્બેડિંગ) ના સમતલીય એમ્બેડિંગ્સને વધારવા માટે 3-જોડાયેલા આલેખની પ્રેરક રચનાનો ઉપયોગ કરે છે. બાંધકામ K4 થી શરૂ થાય છે અને તેને એવી રીતે વ્યાખ્યાયિત કરવામાં આવે છે કે સંપૂર્ણ ઘટકના માર્ગ પરનો દરેક મધ્યવર્તી આલેખ ફરીથી 3-જોડાયેલ હોય. આવા આલેખમાં એક અનન્ય એમ્બેડિંગ (ફ્લિપિંગ અને બાહ્ય ચહેરાની પસંદગી સુધી) હોવાથી, આગામી મોટો આલેખ, જો હજુ પણ સમતોલ હોય, તો તે અગાઉના આલેખનું શુદ્ધિકરણ હોવો જોઈએ. આ પ્લેનેરિટી ટેસ્ટને ઘટાડીને માત્ર દરેક પગલા માટે પરીક્ષણ કરવાની મંજૂરી આપે છે કે પછીની ઉમેરેલી ધાર વર્તમાન એમ્બેડિંગના બાહ્ય ભાગમાં બંને છેડા ધરાવે છે કે કેમ. જ્યારે આ કલ્પનાત્મક રીતે ખૂબ જ સરળ છે (અને રેખીય ચાલવાનો સમય આપે છે), પદ્ધતિ પોતે બાંધકામ ક્રમ શોધવાની જટિલતાથી પીડાય છે. ડાયનેમિક અલ્ગોરિધમ્સ પ્લાનેરિટી પરીક્ષણનો અભ્યાસ ડાયનેમિક અલ્ગોરિધમ્સ મોડેલમાં કરવામાં આવ્યો છે, જેમાં વ્યક્તિ સમસ્યાનો જવાબ જાળવી રાખે છે (આ કિસ્સામાં પ્લાનેરિટી) કારણ કે ગ્રાફ સ્થાનિક સુધારાઓમાંથી પસાર થાય છે, સામાન્ય રીતે ધાર દાખલ કરવા/કાઢી નાખવાના સ્વરૂપમાં. ધાર-આગમનના કિસ્સામાં, લા પોઉટરને કારણે એસિમપોટિકલી ટાઈટ ઇન્વર્સ-એકરમેન ફંક્શન અપડેટ-ટાઇમ અલ્ગોરિધમ છે, જે ડી બેટિસ્ટા, તમાસિયા અને વેસ્ટબ્રૂક દ્વારા અલ્ગોરિધમ્સમાં સુધારો કરે છે. સંપૂર્ણ ગતિશીલ કિસ્સામાં જ્યાં ધાર બંને દાખલ કરવામાં આવે છે અને કાઢી નાખવામાં આવે છે, ત્યાં પેટ્રેસ્કુ અને ડેમેઇન દ્વારા લઘુગણક અપડેટ-ટાઇમ લોઅર બાઉન્ડ હોય છે, અને હોલ્મ અને રોટેનબર્ગ દ્વારા પોલિલોગેરિથમિક અપડેટ-ટાઇમ અલ્ગોરિધમ હોય છે, જે એપસ્ટીન, ગેલિલ, ઈટાલિયાનો, સારનાક અને સ્પેન્સર દ્વારા સબ-લિનિયર અપડેટ-ટાઇમ અલ્ગોરિધમ્સમાં સુધારો કરે છે. સંદર્ભો પ્લાનર ગ્રાફ ગ્રાફ થિયરીમાં કોમ્પ્યુટેશનલ સમસ્યાઓ