Planarity testing
گراف تھیوری میں، پلانریٹی ٹیسٹنگ کا مسئلہ یہ جانچنے کا الگورتھمک مسئلہ ہے کہ آیا دیا گیا گراف پلانر گراف ہے (یعنی، کیا اسے کنارے کے چوراہوں کے بغیر ہوائی جہاز میں کھینچا جا سکتا ہے)۔ یہ کمپیوٹر سائنس میں ایک اچھی طرح سے مطالعہ شدہ مسئلہ ہے جس کے لیے بہت سے عملی الگورتھم سامنے آئے ہیں، جن میں سے بہت سے نئے ڈیٹا ڈھانچے سے فائدہ اٹھا رہے ہیں۔ ان میں سے زیادہ تر طریقے O (n) وقت (لکیری وقت) میں کام کرتے ہیں، جہاں n گراف میں کناروں (یا عمودی) کی تعداد ہے، جو غیر علامتی طور پر زیادہ سے زیادہ ہے۔ صرف ایک واحد بولین ویلیو ہونے کے بجائے، پلانریٹی ٹیسٹنگ الگورتھم کی آؤٹ پٹ ایک پلانر گراف ایمبیڈنگ ہو سکتی ہے، اگر گراف پلانر ہے، یا پلانریٹی میں رکاوٹ جیسے کوراتووسکی سب گراف اگر نہیں ہے۔ پلانریٹی ٹیسٹنگ الگورتھم عام طور پر گراف تھیوری میں ان نظریات سے فائدہ اٹھاتے ہیں جو پلانر گراف کے سیٹ کو گراف ڈرائنگ سے آزاد ہوتے ہیں۔ ان میں کوراتووسکی کا نظریہ شامل ہے کہ گراف اس صورت میں اور صرف اس صورت میں پلانر ہوتا ہے جب اس میں کوئی ذیلی گراف نہ ہو جو کہ K5 (پانچ عمودی پر مکمل گراف) یا K3,3 (یوٹیلیٹی گراف، چھ عمودی پر ایک مکمل دو طرفہ گراف، جن میں سے تین دیگر تینوں میں سے ہر ایک سے جڑتے ہیں) کا ذیلی گراف ہو۔ ویگنر کا نظریہ کہ ایک گراف پلانر ہے اگر اور صرف اس صورت میں جب اس میں کوئی معمولی (سنکچن کا ذیلی گراف) نہ ہو جو کہ K5 یا K3,3 کے لیے آئسومورفک ہو۔ فریسیکس-روزنسٹیل پلانریٹی کا معیار، گہرائی سے پہلے تلاش کے درخت میں کناروں کی بائیں دائیں ترتیب کے لحاظ سے پلانر گراف کی خصوصیت ہے۔ فریسیکس-روزنسٹیل پلانریٹی معیار کو براہ راست پلانریٹی ٹیسٹنگ کے لیے الگورتھم کے حصے کے طور پر استعمال کیا جا سکتا ہے، جبکہ کوراتووسکی اور ویگنر کے نظریات میں بالواسطہ ایپلی کیشنز ہیں: اگر کوئی الگورتھم کسی دیئے گئے گراف کے اندر K5 یا K3,3 کی کاپی تلاش کر سکتا ہے، تو یہ یقینی بنایا جا سکتا ہے کہ ان پٹ گراف پلانر نہیں ہے اور اضافی حساب کے بغیر واپس آتا ہے۔ دیگر طیاروں کے معیار، جو کہ ریاضیاتی طور پر طیاروں کے گراف کی خصوصیت رکھتے ہیں لیکن طیاروں کی جانچ کے الگورتھم کے لیے کم مرکزی ہیں، میں شامل ہیں: وٹنی کا طیاروں کا معیار کہ ایک گراف طیاروں کا ہے اگر اور صرف اس صورت میں جب اس کا گرافک میٹرائڈ بھی کوگرافک ہو، میک لین کا طیاروں کا معیار طیاروں کے گراف کو ان کے سائیکل خالی جگہوں کے اڈوں سے نمایاں کرتا ہے، شنائڈر کا نظریہ طیاروں کے گراف کو متعلقہ جزوی ترتیب کے ترتیب کے طول و عرض سے نمایاں کرتا ہے، اور سپیکٹرم گراف تھیوری کا استعمال کرتے ہوئے کولن ڈی ورڈیئر کا طیاروں کا معیار۔ الگورتھم پاتھ ایڈیشن میتھڈ ہاپکرافٹ اور ٹارجن کا کلاسک پاتھ ایڈیشن میتھڈ 1974 میں شائع ہونے والا پہلا لینیر ٹائم پلانریٹی ٹیسٹنگ الگورتھم تھا۔ ہاپکرافٹ اور ٹارجن کے الگورتھم کا نفاذ لائبریری آف ایفیشینٹ ڈیٹا ٹائپز اور الگورتھم میں مہلہورن، متزل اور نیہر کے ذریعہ فراہم کیا گیا ہے۔ 2012 میں، ٹیلر نے اس الگورتھم کو دو جڑے ہوئے اجزاء کے پلانر ایمبیڈنگ کے لیے سائکلک ایج آرڈر کی تمام تغیرات پیدا کرنے کے لیے بڑھایا۔ ورٹیکس کے اضافے کا طریقہ ورٹیکس کے اضافے کے طریقے ڈیٹا ڈھانچے کو برقرار رکھتے ہوئے کام کرتے ہیں جو دیئے گئے گراف کے ایک انڈیوسڈ سب گراف کے ممکنہ سرایت کی نمائندگی کرتے ہیں، اور اس ڈیٹا ڈھانچے میں ایک وقت میں عمودی حصے شامل کرتے ہیں۔ ان طریقوں کا آغاز ایک غیر موثر O (n2) طریقہ سے ہوا جس کا تصور لیمپل، ایون اور سیڈربام نے 1967 میں کیا تھا۔ اسے ایون اور ٹارجن نے بہتر بنایا، جنہوں نے ایس، ٹی نمبرنگ اسٹیپ کے لیے لکیری ٹائم حل تلاش کیا، اور بوتھ اور لیوکر نے، جنہوں نے پی کیو ٹری ڈیٹا اسٹرکچر تیار کیا۔ ان بہتریوں کے ساتھ یہ لکیری ٹائم ہے اور عملی طور پر پاتھ ایڈیشن کے طریقہ کار کو پیچھے چھوڑ دیتا ہے۔ اس طریقہ کار کو پلانر ایمبیڈنگ (ڈرائنگ) کو پلانر گراف کے لیے مؤثر طریقے سے شمار کرنے کی اجازت دینے کے لیے بھی بڑھایا گیا تھا۔ 1999 میں، شیہ اور سو نے پی سی ٹری (پی کیو ٹری کا ایک غیر جڑا ہوا ورژن) اور چوٹیوں کے ڈیپتھ-فرسٹ سرچ ٹری کے پوسٹ آرڈر ٹریورسل کا استعمال کرتے ہوئے ان طریقوں کو آسان بنایا۔ ایج ایڈیشن کا طریقہ 2004 میں، جان بوئیر اور وینڈی مروولڈ نے ایک آسان O (n) الگورتھم تیار کیا، جو اصل میں PQ ٹری کے طریقہ سے متاثر تھا، جو PQ ٹری سے چھٹکارا حاصل کرتا ہے اور اگر ممکن ہو تو پلانر ایمبیڈنگ کا حساب لگانے کے لیے ایج ایڈیشن کا استعمال کرتا ہے۔ بصورت دیگر، کوراتووسکی ذیلی تقسیم (K5 یا K3,3 میں سے) کا حساب لگایا جاتا ہے۔ یہ آج کے دو موجودہ جدید ترین الگورتھم میں سے ایک ہے (دوسرا ڈی فریسیکس، اوسونا ڈی مینڈیز اور روزنسٹیل کا پلانریٹی ٹیسٹنگ الگورتھم ہے)۔ بوئیر اور مروولڈ پلانریٹی ٹیسٹ کے ابتدائی ورژن کے ساتھ تجرباتی موازنہ کے لیے دیکھیں۔ مزید برآں، بوئیر-مروولڈ ٹیسٹ کو آؤٹ پٹ سائز پر منحصر ایک رننگ ٹائم میں غیر پلینر ان پٹ گراف کے متعدد کوراتووسکی سب ڈویژنوں کو نکالنے کے لیے بڑھایا گیا تھا۔ پلانریٹی ٹیسٹ اور متعدد کوراتووسکی سب ڈویژنوں کو نکالنے کے لیے سورس کوڈ عوامی طور پر دستیاب ہے۔ وہ الگورتھم جو عمودی میں لکیری وقت میں کوراتووسکی سب گراف کا پتہ لگاتے ہیں، ولیمسن نے 1980 کی دہائی میں تیار کیے تھے۔ تعمیراتی ترتیب کا طریقہ ایک مختلف طریقہ 3 منسلک گرافوں کی تعمیری تعمیر کا استعمال کرتا ہے تاکہ G کے ہر 3 منسلک جزو (اور اسی وجہ سے خود G کی ایک پلانر سرایت) کے پلانر سرایت کو بڑھایا جا سکے۔ تعمیر K4 سے شروع ہوتی ہے اور اس کی وضاحت اس طرح کی جاتی ہے کہ مکمل جزو کے راستے میں ہر انٹرمیڈیٹ گراف دوبارہ 3 سے منسلک ہوتا ہے۔ چونکہ اس طرح کے گرافوں میں ایک منفرد سرایت ہوتی ہے (پلٹنے اور بیرونی چہرے کے انتخاب تک)، اگلا بڑا گراف، اگر اب بھی ہموار ہے، تو سابقہ گراف کی اصلاح ہونی چاہیے۔ یہ پلانریٹی ٹیسٹ کو صرف ہر مرحلے کے لیے جانچ کرنے تک کم کرنے کی اجازت دیتا ہے کہ آیا اگلے اضافی کنارے کے دونوں سرے موجودہ سرایت کے بیرونی چہرے پر ہیں۔ اگرچہ یہ تصوراتی طور پر بہت آسان ہے (اور لکیری رننگ ٹائم دیتا ہے)، طریقہ خود تعمیراتی ترتیب کو تلاش کرنے کی پیچیدگی سے دوچار ہے۔ متحرک الگورتھم پلانریٹی ٹیسٹنگ کا مطالعہ متحرک الگورتھم ماڈل میں کیا گیا ہے، جس میں کوئی شخص کسی مسئلے کا جواب برقرار رکھتا ہے (اس معاملے میں پلانریٹی) کیونکہ گراف مقامی اپ ڈیٹس سے گزرتا ہے، عام طور پر کناروں کو داخل کرنے/حذف کرنے کی شکل میں۔ کنارے کی آمد کے معاملے میں، لا پوٹری کی وجہ سے ایک غیر متزلزل طور پر سخت الٹا ایکرمین فنکشن اپ ڈیٹ ٹائم الگورتھم ہے، جو ڈی بٹسٹا، تاماسیا اور ویسٹ بروک کے الگورتھم میں بہتری لاتا ہے۔ مکمل طور پر متحرک معاملے میں جہاں کناروں کو داخل اور حذف کیا جاتا ہے، وہاں پیٹراسکو اور ڈیمین کے ذریعہ ایک لوگرتھمک اپ ڈیٹ ٹائم کم باؤنڈ ہوتا ہے، اور ہولم اور روٹن برگ کے ذریعہ ایک پولی لوگرتھمک اپ ڈیٹ ٹائم الگورتھم ہوتا ہے، جو ایپسٹین، گیلیل، اطالوی، سرنک اور اسپینسر کے ذریعہ ذیلی لکیری اپ ڈیٹ ٹائم الگورتھم کو بہتر بناتا ہے۔ حوالہ جات پلانر گرافز گراف تھیوری میں کمپیوٹیشنل مسائل