Left-right planarity test
આલેખ સિદ્ધાંતમાં, ગણિતની એક શાખા, ડાબી-જમણી પ્લેનેરિટી ટેસ્ટ અથવા ડી ફ્રેસીક્સ-રોસેનસ્ટીહલ પ્લેનેરિટી માપદંડ એ ઊંડાઈ-પ્રથમ શોધ વૃક્ષોના ગુણધર્મો પર આધારિત પ્લેનર ગ્રાફનું લાક્ષણિકતા છે, જે તેમના દ્વારા પેટ્રીસ ઓસોના ડી મેન્ડેઝ દ્વારા પ્રકાશિત અને તેમના દ્વારા રેખીય સમય પ્લેનેરિટી પરીક્ષણ અલ્ગોરિધમ વિકસાવવા માટે ઉપયોગમાં લેવાય છે. 2003માં છ પ્લેનેરિટી પરીક્ષણ અલ્ગોરિધમ્સની પ્રાયોગિક સરખામણીમાં, આ પરીક્ષણ કરાયેલ સૌથી ઝડપી અલ્ગોરિધમ્સમાંનું એક હતું. T-સમાન અને T-વિરુદ્ધ ધાર આલેખ G ની કોઈપણ ઊંડાઈ-પ્રથમ શોધ માટે, પ્રથમ વખત શિરોબિંદુ શોધતી વખતે જે ધારોનો સામનો કરવો પડે છે તે G ના ઊંડાઈ-પ્રથમ શોધ વૃક્ષ T ને વ્યાખ્યાયિત કરે છે. આ એક ટ્રેમોક્સ વૃક્ષ છે, જેનો અર્થ છે કે બાકીની ધાર (કોટ્રી) દરેક શિરોબિંદુઓની જોડીને જોડે છે જે T માં પૂર્વજ અને વંશજ તરીકે એકબીજા સાથે સંબંધિત છે. કોટ્રી ધારની જોડી વચ્ચેના બે સંબંધોને વ્યાખ્યાયિત કરવા માટે ત્રણ પ્રકારની પેટર્નનો ઉપયોગ કરી શકાય છે, જેને T-સમાન અને T-વિરુદ્ધ સંબંધો નામ આપવામાં આવ્યું છે. નીચેની આકૃતિઓમાં, સરળ વર્તુળ નોડ્સ શિરોબિંદુઓનું પ્રતિનિધિત્વ કરે છે, બેવડા વર્તુળ નોડ્સ સબટ્રીનું પ્રતિનિધિત્વ કરે છે, ટ્વિસ્ટેડ સેગમેન્ટ્સ વૃક્ષના માર્ગનું પ્રતિનિધિત્વ કરે છે અને વક્ર ચાપ કોટ્રી ધારનું પ્રતિનિધિત્વ કરે છે. દરેક વૃક્ષનું મૂળ આકૃતિની નીચે દર્શાવવામાં આવ્યું છે. પ્રથમ આકૃતિમાં, કિનારીઓ લેબલ થયેલ છે અને ટી-સમાન છે, જેનો અર્થ છે કે, વૃક્ષના મૂળની નજીકના અંતિમ બિંદુઓ પર, તેઓ બંને દરેક સમતલીય ચિત્રમાં વૃક્ષની એક જ બાજુ પર હશે. આગામી બે આકૃતિઓમાં, સમાન લેબલવાળી ધાર ટી-વિરુદ્ધ છે, જેનો અર્થ છે કે તેઓ દરેક સમતલીય ચિત્રમાં વૃક્ષની જુદી જુદી બાજુઓ પર હશે. લાક્ષણિકતા G એ આલેખ હોવો જોઈએ અને T એ G નું ટ્રેમોક્સ વૃક્ષ હોવું જોઈએ. આલેખ G એ સમતલ છે જો અને માત્ર ત્યારે જ જો G ની કોટ્રી ધારને બે વર્ગોમાં વિભાજિત કરવામાં આવે જેથી કોઈપણ બે ધાર એક જ વર્ગની હોય જો તે T-સમાન હોય અને કોઈપણ બે ધાર અલગ અલગ વર્ગની હોય જો તે T-વિરુદ્ધ હોય. આ લાક્ષણિકતા તરત જ (બિનકાર્યક્ષમ) સમતલતા પરીક્ષણ તરફ દોરી જાય છેઃ ધારની તમામ જોડી માટે નક્કી કરો કે શું તે ટી-સમાન અથવા ટી-વિરુદ્ધ છે, એક સહાયક આલેખ બનાવો જેમાં ટી-સમાન ધારના દરેક જોડાયેલા ઘટક માટે શિરોબિંદુ હોય અને ટી-વિરુદ્ધ ધારની દરેક જોડી માટે ધાર હોય, અને તપાસો કે આ સહાયક આલેખ દ્વિપક્ષી છે કે કેમ. આ અલ્ગોરિધમને કાર્યક્ષમ બનાવવા માટે ટી-સમાન અને ટી-વિરુદ્ધ જોડીનો સબસેટ શોધવાનો સમાવેશ થાય છે જે ઇનપુટ ગ્રાફમાં તમામ ધાર જોડી વચ્ચેના સંબંધને નિર્ધારિત કર્યા વિના આ પદ્ધતિને અમલમાં મૂકવા માટે પૂરતા છે. સંદર્ભો વધુ વાંચન ટોપોલોજીકલ ગ્રાફ થિયરી પ્લાનર ગ્રાફ