سنجش مسطح بودن

در نظریه گراف، مسئله سنجش مسطح بودن، مسئله الگوریتمی است راجع به اینکه آیا یک گراف داده شده گراف مسطح است یا خیر (یعنی آیا آن را می‌توان در صفحه بدون اینکه یال‌هایش تقاطع داشته باشند رسم کرد). این مسئله در علم کامپیوتر به خوبی بررسی شده‌است که برای آن الگوریتم‌های عملی بسیاری پدید آمده که خیلی از آن‌ها از رمان ساختارهای داده بهره گرفته‌اند. بیشتر این روش‌ها در زمانی از مرتبه n (زمان خطی) که در آن n تعداد یال (یا راس) در گراف است انجام می‌شوند که به صورت جانبی مطلوب است. به جای فقط یک مقدار بولی (صفر و یک) برای خروجی از یک آزمون الگوریتم مسطح بودن ممکن است خروجی یک گراف مسطح تعبیه شده باشد اگر گراف مسطح باشد یا یک مانع برای مسطح بودن باشد مانند یک زیرگراف کراتوفسکی اگر مسطح نباشد.

معیارهای مسطح بودن 
الگوریتم‌های آزمون مسطح بودن به‌طور معمول از قضایا در نظریه گراف استفاده می‌کنند که در اصطلاح مجموعه‌ای از گراف‌های مسطح که مستقل از کشیدن گراف است را مشخص می‌کند.
این قضایا عبارت اند از:
 قضیه Kuratowski که می‌گوید یک گراف مسطح است اگر و تنها اگر شامل یک زیر گراف که زیر بخشی از K5 (گراف کامل با پنج راس) یا K3,3 (گراف دو بخشی با ۶ راس که ۳ راس در یک بخش و ۳ بخش در بخش دیگر و هیچ دو یال در یک بخش به هم وصل نیستند) نباشد.
 قضیه واگنر که می‌گوید یک گراف مسطح است اگر و تنها اگر شامل یک جزء (زیرگراف انقباضی) که هم ریخت با K5 یا K3,3 است نباشد.
 معیار مسطح بودن Fraysseix–Rosenstiehl گراف‌های مسطح را در اصطلاح چیدن از چپ به راست راس‌ها در جستجوی اول عمق درخت مشخص می‌کند.
معیار مسطح بودن Fraysseix–Rosenstiehl می‌تواند به‌طور مستقیم به عنوان بخشی از الگوریتم برای آزمون مسطح بودن مورد استفاده قرار گیرد در حالی که قضایای Kuratowski و واگنر کاربرد غیرمستقیم دارند: اگر یک الگوریتم می‌توانید یک کپی از K5 یا K3,3 در یک گراف داده شده را پیدا کند می‌توان مطمئن شد که گراف ورودی مسطح نیست و بدون محاسبات اضافی آزمون تمام می‌شود.

دیگر معیارهای مسطح بودن، که مسطح بودن گراف را به صورت ریاضی و کمتر به‌طور مرکزی با الگوریتم‌های آزمون مسطح بودن مشخص می‌کند، شامل معیار مسطح بودن ویتنی است که می‌گوید یک گراف مسطح است اگر و تنها اگر متروید گرافیکی آن شرکت گرافیکی نیز است. معیار مسطح بودن مک لین گراف مسطح را برمبنای چرخه فضاها مشخص می‌کند، قضیه Schnyder گراف مسطح را با ترتیب فضایی از جمع‌بندی ترتیب جزئی مشخص می‌کند و معیار مسطح بودن کالین د وردیر با استفاده از نظریه گراف طیفی است.

الگوریتم‌ها

روش افزایش مسیر 
روش کلاسیک افزایش مسیر توسط Hopcroft و Tarjan اولین روش آزمون مسطح بودن در زمان خطی بود که در ماه مه سال ۱۹۷۴ منتشر شد. یک پیاده‌سازی از الگوریتم Hopcroft و Tarjan's در کتابخانه کارآمد انواع داده‌ها و الگوریتم‌ها توسط Mehlhorn، Mutzel و Näher
ارائه شد. در سال ۲۰۱۲ تیلور این الگوریتم را برای تولید تمام جایگشت‌های چرخ‌های ترتیب یال برای به صورت مسطح جاسازی شده از قطعات بدون اتصال توسعه داد.

روش افزایش رئوس 
روش افزایش رئوس با حفظ ساختار داده‌ها که نمایش می‌دهند زیرگراف القایی محتمل موجود را و اضافه کردن رئوس در یک زمان به این ساختار داده‌ها کار می‌کند. این روش با یک روش نامناسب که از مرتبه n² درست شده توسط Lempel، Even و Cederbaum در سال ۱۹۶۷ آغاز می‌شود. این روش توسط Evan و Tirjan که یک روش در زمان خطی پیدا کردند برای s، شماره گذاری قدمی t، و توسط Booth و Lucker که ساختار داده درختی PQ را ساختند بهتر شد. با این بهتر شدن‌ها، روش‌ها در زمان خطی اجرا شدند و در عمل روش افزایش مسیر را بهتر کردند. در سال ۱۹۹۹، Shih و Hsu این روش‌ها را با استفاده از درخت کامپیوتری (یک نوع درخت PQ) و یک پیمایش پسا ترتیب ازجست و جوی اول عمق درخت از راس‌ها ساده کردند.

روش افزایش یال 
در سال ۲۰۰۴ بویر و Myrvold یک الگوریتم از مرتبه n را توسعه دادند، که در اصل با الهام از درخت PQ است که با خلاص شدن از درخت PQ از افزایش یال یک جاسازی مسطح را اگر ممکن باشد محاسبه می‌کند. در غیر این صورت یک زیر بخش Kuratowski (یا K5 یا K3,3) محاسبه می‌شود. امروزه این یکی از دو وضعیت فعلی الگوریتم هنری است (یک دیگر از الگوریتم‌های آزمون مسطح بودن الگوریتم de Fraysseix، د مندز و Rosenstiehl است). را برای یک مقایسه عملی با مدل مقدماتی از آزمون بویر و Myrvold planarity ببینید. بعلاوه آزمون بویر–Myrvold برای استخراج چند زیربخش Kuratowski از یک گراف ورودی غیر مسطح در یک زمان در حال اجرا خطی وابسته به خروجی اندازه گسترش یافت. منبع کد برای آزمون مسطح بودن و استخراج متعدد زیربخش‌های Kuratowski در دسترس عموم است. الگوریتم‌هایی که یک زیرگراف Kuratowski در زمان خطی در راس‌ها پیدا می‌کنند، توسط ویلیامسون در دهه ۱۹۸۰ توسعه یافتند.

روش ساخت دنباله 
یک روش متفاوت از ساخت القایی گراف ۳ بخشی استفاده می‌کند تا به صورت صعودی یک زیر گراف بسازد از گراف G(در نتیجه یک جاسازی مسطح از گراف G). ساخت و ساز با K4 شروع می‌شود و در چنین راهی تعریف شده‌است که هر گراف حد واسط در راه کامل شدن اجزا که دوباره ۳ بخشی می‌شود قرار می‌گیرد. به خاطر اینکه این نوع گراف‌ها یک جاسازی یکتا دارند، گراف بزرگتر بعدی اگر باز سطحی باشد باید بهبودی از گراف قبلی باشد. این کاهش آزمون مسطح بودن برای در هر مرحله را اجازه می‌دهد که آیا یال اضافه شده بعدی دو انتها در هر دو وجه خروجی زیر گراف فعلی دارد یا خیر. در حالی که این یک مفهوم بسیار ساده است (و در زمان خطی اجرا می‌شود) خود روش دچار پیچیدگی پیدا کردن ساخت دنباله است.

منابع 

گراف‌های مسطح
مسئله‌های محاسباتی در نظریه گراف