Left-right planarity test
گراف تھیوری میں، ریاضی کی ایک شاخ، لیفٹ-رائٹ پلانریٹی ٹیسٹ یا ڈی فریسیکس-روزنسٹیل پلانریٹی کرائٹیرین گہرائی سے پہلے تلاش کرنے والے درختوں کی خصوصیات پر مبنی پلانر گراف کی ایک خصوصیت ہے، جسے پیٹریس اوسونا ڈی مینڈیز کے ذریعہ شائع کیا گیا اور ان کے ذریعہ استعمال کیا گیا تاکہ لکیری ٹائم پلانریٹی ٹیسٹنگ الگورتھم تیار کیا جا سکے۔ 2003 میں چھ پلانریٹی ٹیسٹنگ الگورتھم کے تجرباتی موازنہ میں، یہ ٹیسٹ کیے گئے تیز ترین الگورتھم میں سے ایک تھا۔ ٹی-الائکی اور ٹی-مخالف کناروں کے لیے گراف جی کی کسی بھی گہرائی-پہلی تلاش کے لیے، پہلی بار کسی ورٹیکس کو دریافت کرتے وقت جن کناروں کا سامنا کرنا پڑتا ہے وہ ڈیپتھ-فرسٹ سرچ ٹری آف جی کی وضاحت کرتے ہیں۔ یہ ایک ٹریماکس ٹری ہے، جس کا مطلب ہے کہ باقی کناروں (کوٹری) میں سے ہر ایک ایسے عمودی جوڑے کو جوڑتا ہے جو ٹی میں آباؤ اجداد اور نسل کے طور پر ایک دوسرے سے متعلق ہیں۔ کوٹری کناروں کے جوڑوں کے درمیان دو تعلقات کی وضاحت کے لیے تین قسم کے نمونوں کا استعمال کیا جا سکتا ہے، جسے ٹی-الائکی اور ٹی-مخالف تعلقات کا نام دیا گیا ہے۔ مندرجہ ذیل اعداد و شمار میں، سادہ سرکل نوڈس عمودی کی نمائندگی کرتے ہیں، ڈبل سرکل نوڈس ذیلی درختوں کی نمائندگی کرتے ہیں، مڑے ہوئے حصے درخت کے راستوں کی نمائندگی کرتے ہیں، اور مڑے ہوئے آرکس کوٹری کے کناروں کی نمائندگی کرتے ہیں۔ ہر درخت کی جڑ شکل کے نچلے حصے میں دکھائی گئی ہے۔ پہلی شکل میں، کناروں پر ٹی-الائکی لیبل لگا ہوا ہے، جس کا مطلب ہے کہ، درخت کی جڑ کے قریب ترین اختتامی نکات پر، وہ دونوں ہر پلینر ڈرائنگ میں درخت کے ایک ہی طرف ہوں گے۔ اگلے دو اعداد و شمار میں، ایک ہی لیبل والے کنارے ٹی-مخالف ہیں، جس کا مطلب ہے کہ وہ ہر پلینر ڈرائنگ میں درخت کے مختلف اطراف ہوں گے۔ G کو ایک گراف ہونے دیں اور T کو G کا ٹریماکس ٹری ہونے دیں۔ گراف G صرف اس صورت میں پلانر ہے جب G کے کوٹری کناروں کو دو کلاسوں میں تقسیم کیا جائے تاکہ کوئی بھی دو کنارے ایک ہی کلاس سے تعلق رکھتے ہوں اگر وہ T-الائکی ہوں اور کوئی بھی دو کنارے مختلف کلاسوں سے تعلق رکھتے ہوں اگر وہ T-مخالف ہوں۔ یہ خصوصیت فوری طور پر ایک (غیر موثر) پلانریٹی ٹیسٹ کی طرف لے جاتی ہے: کناروں کے تمام جوڑوں کا تعین کریں کہ آیا وہ ٹی-الائک ہیں یا ٹی-مخالف، ایک معاون گراف بنائیں جس میں ٹی-الائک کناروں کے ہر منسلک جزو کے لیے ایک ورٹیکس اور ٹی-مخالف کناروں کے ہر جوڑے کے لیے ایک کنارہ ہو، اور چیک کریں کہ آیا یہ معاون گراف دو طرفہ ہے۔ اس الگورتھم کو موثر بنانے میں ٹی-الائک اور ٹی-مخالف جوڑوں کا ایک ذیلی سیٹ تلاش کرنا شامل ہے جو ان پٹ گراف میں تمام کنارے کے جوڑوں کے درمیان تعلق کا تعین کیے بغیر اس طریقہ کو انجام دینے کے لیے کافی ہے۔ حوالہ جات مزید پڑھنا ٹوپوولوجیکل گراف تھیوری پلانر گراف