Left-right planarity test
গ্রাফ তত্ত্বে, গণিতের একটি শাখা, বাম-ডান সমতলীয় পরীক্ষা বা ডি ফ্রেইসিক্স-রোজেনস্টিল সমতলীয় মানদণ্ড হল গভীরতা-প্রথম অনুসন্ধান গাছের বৈশিষ্ট্যের উপর ভিত্তি করে সমতলীয় গ্রাফের একটি বৈশিষ্ট্য, যা প্যাট্রিস ওসোনা ডি মেন্ডেজের দ্বারা প্রকাশিত এবং তাদের দ্বারা একটি রৈখিক সময় সমতলীয় পরীক্ষার অ্যালগরিদম বিকাশের জন্য ব্যবহৃত হয়। 2003 সালে ছয়টি প্ল্যানারিটি টেস্টিং অ্যালগরিদমের পরীক্ষামূলক তুলনায়, এটি পরীক্ষিত দ্রুততম অ্যালগরিদমগুলির মধ্যে একটি ছিল। টি-সমতুল্য এবং টি-বিপরীত প্রান্ত গ্রাফ জি-এর যে কোনও গভীরতা-প্রথম অনুসন্ধানের জন্য, প্রথমবার একটি শীর্ষ আবিষ্কার করার সময় যে প্রান্তগুলির মুখোমুখি হয় সেগুলি জি-এর একটি গভীরতা-প্রথম অনুসন্ধান গাছ টি-কে সংজ্ঞায়িত করে। এটি একটি ট্রেমাক্স গাছ, যার অর্থ অবশিষ্ট প্রান্তগুলি (কোট্রি) প্রতিটি টি-তে পূর্বপুরুষ এবং বংশধর হিসাবে একে অপরের সাথে সম্পর্কিত এক জোড়া শীর্ষকে সংযুক্ত করে। কোট্রি প্রান্তের জোড়াগুলির মধ্যে দুটি সম্পর্ক সংজ্ঞায়িত করতে তিন ধরণের নিদর্শন ব্যবহার করা যেতে পারে, যার নাম টি-সমতুল্য এবং টি-বিপরীত সম্পর্ক। নিম্নলিখিত চিত্রগুলিতে, সাধারণ বৃত্তাকার নোডগুলি শীর্ষকে উপস্থাপন করে, ডবল সার্কেল নোডগুলি সাবট্রিকে প্রতিনিধিত্ব করে, বাঁকানো অংশগুলি গাছের পথকে উপস্থাপন করে এবং বাঁকা চাপগুলি কোট্রি প্রান্তকে উপস্থাপন করে। প্রতিটি গাছের মূল চিত্রের নীচে দেখানো হয়েছে। প্রথম চিত্রে, প্রান্তগুলি লেবেলযুক্ত এবং টি-সমতুল্য, যার অর্থ, গাছের মূলের নিকটতম শেষ বিন্দুতে, তারা উভয়ই প্রতিটি সমতলীয় অঙ্কনে গাছের একই দিকে থাকবে। পরবর্তী দুটি চিত্রে, একই লেবেলযুক্ত প্রান্তগুলি টি-বিপরীত, যার অর্থ তারা প্রতিটি সমতলীয় অঙ্কনে গাছের বিভিন্ন পাশে থাকবে। G-কে একটি গ্রাফ এবং T-কে G-এর একটি ট্রেমাক্স গাছ হিসাবে ধরা যাক। G গ্রাফটি সমতল হয় যদি G-এর কোট্রি প্রান্তগুলিকে দুটি শ্রেণীতে বিভক্ত করা হয় যাতে যে কোনও দুটি প্রান্ত একই শ্রেণীর হয় যদি তারা T-সমতুল্য হয় এবং যে কোনও দুটি প্রান্ত ভিন্ন শ্রেণীর হয় যদি তারা T-বিপরীত হয়। এই বৈশিষ্ট্যটি অবিলম্বে একটি (অদক্ষ) সমতলীয় পরীক্ষার দিকে নিয়ে যায়ঃ সমস্ত জোড়া প্রান্তের জন্য নির্ধারণ করুন যে তারা টি-সমতুল্য বা টি-বিপরীত কিনা, একটি সহায়ক গ্রাফ তৈরি করুন যাতে টি-সমতুল্য প্রান্তের প্রতিটি সংযুক্ত উপাদানের জন্য একটি শীর্ষ এবং টি-বিপরীত প্রান্তের প্রতিটি জোড়ের জন্য একটি প্রান্ত রয়েছে এবং এই সহায়ক গ্রাফটি দ্বিদলীয় কিনা তা পরীক্ষা করুন। এই অ্যালগরিদমকে দক্ষ করার জন্য টি-অ্যালাইক এবং টি-বিপরীত জুটির একটি উপসেট খুঁজে বের করা জড়িত যা ইনপুট গ্রাফের সমস্ত প্রান্ত জোড়ার মধ্যে সম্পর্ক নির্ধারণ না করে এই পদ্ধতিটি চালানোর জন্য যথেষ্ট। আরও পড়ুন টপোলজিক্যাল গ্রাফ তত্ত্ব প্ল্যানার গ্রাফ