موضوع مقاله: سنجش مسطح بودن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # سنجش مسطح بودن | مقدمه: در نظریه گراف، مسئله سنجش مسطح بودن، مسئله الگوریتمی است راجع به اینکه آیا یک گراف داده شده گراف مسطح است یا خیر (یعنی آیا آن را می‌توان در صفحه بدون اینکه یال‌هایش تقاطع داشته باشند رسم کرد). | ## بخش 1: سنجش مسطح بودن | این مسئله در علم کامپیوتر به خوبی بررسی شده‌است که برای آن الگوریتم‌های عملی بسیاری پدید آمده که خیلی از آن‌ها از رمان ساختارهای داده بهره گرفته‌اند. بیشتر این روش‌ها در زمانی از مرتبه n (زمان خطی) که در آن n تعداد یال (یا راس) در گراف است انجام می‌شوند که به صورت جانبی مطلوب است. به جای فقط یک مقدار بولی (صفر و یک) برای خروجی از یک آزمون الگوریتم مسطح بودن ممکن است خروجی یک گراف مسطح تعبیه شده باشد اگر گراف مسطح باشد یا یک مانع برای مسطح بودن باشد مانند یک زیرگراف کراتوفسکی اگر مسطح نباشد. معیارهای مسطح بودن الگوریتم‌های آزمون مسطح بودن به‌طور معمول از قضایا در نظریه گراف استفاده می‌کنند که در اصطلاح مجموعه‌ای از گراف‌های مسطح که مستقل از کشیدن گراف است را مشخص می‌کند. این قضایا عبارت اند از: قضیه Kuratowski که می‌گوید یک گراف مسطح است اگر و تنها اگر شامل یک زیر گراف که زیر بخشی از K5 (گراف کامل با پنج راس) یا K3,3 (گراف دو بخشی با ۶ راس که ۳ راس در یک بخش و ۳ بخش در بخش دیگر و هیچ دو یال در یک بخش به هم وصل نیستند) نباشد. قضیه واگنر که می‌گوید یک گراف مسطح است اگر و تنها اگر شامل یک جزء (زیرگراف انقباضی) که هم ریخت با K5 یا K3,3 است نباشد. | ## بخش 2: سنجش مسطح بودن | دیگر معیارهای مسطح بودن، که مسطح بودن گراف را به صورت ریاضی و کمتر به‌طور مرکزی با الگوریتم‌های آزمون مسطح بودن مشخص می‌کند، شامل معیار مسطح بودن ویتنی است که می‌گوید یک گراف مسطح است اگر و تنها اگر متروید گرافیکی آن شرکت گرافیکی نیز است. معیار مسطح بودن مک لین گراف مسطح را برمبنای چرخه فضاها مشخص می‌کند، قضیه Schnyder گراف مسطح را با ترتیب فضایی از جمع‌بندی ترتیب جزئی مشخص می‌کند و معیار مسطح بودن کالین د وردیر با استفاده از نظریه گراف طیفی است. در سال ۲۰۱۲ تیلور این الگوریتم را برای تولید تمام جایگشت‌های چرخ‌های ترتیب یال برای به صورت مسطح جاسازی شده از قطعات بدون اتصال توسعه داد. روش افزایش رئوس روش افزایش رئوس با حفظ ساختار داده‌ها که نمایش می‌دهند زیرگراف القایی محتمل موجود را و اضافه کردن رئوس در یک زمان به این ساختار داده‌ها کار می‌کند. ” با این بهتر شدن‌ها، روش‌ها در زمان خطی اجرا شدند و در عمل روش افزایش مسیر را بهتر کردند.. در سال ۱۹۹۹، Shih و Hsu این روش‌ها را با استفاده از درخت کامپیوتری (یک نوع درخت PQ) و یک پیمایش پسا ترتیب ازجست و جوی اول عمق درخت از راس‌ها ساده کردند.. | ## بخش 3: سنجش مسطح بودن | یک الگوریتم از مرتبه n را توسعه دادند، که در اصل با الهام از درخت PQ است که با خلاص شدن از درخت PQ از افزایش یال یک جاسازی مسطح را اگر ممکن باشد محاسبه می‌کند. روش ساخت دنباله یک روش متفاوت از ساخت القایی گراف ۳ بخشی استفاده می‌کند تا به صورت صعودی یک زیر گراف بسازد از گراف G(در نتیجه یک جاسازی مسطح از گراف G). ساخت و ساز با K4 شروع می‌شود و در چنین راهی تعریف شده‌است که هر گراف حد واسط در راه کامل شدن اجزا که دوباره ۳ بخشی می‌شود قرار می‌گیرد. به خاطر اینکه این نوع گراف‌ها یک جاسازی یکتا دارند، گراف بزرگتر بعدی اگر باز سطحی باشد باید بهبودی از گراف قبلی باشد. این کاهش آزمون مسطح بودن برای در هر مرحله را اجازه می‌دهد که آیا یال اضافه شده بعدی دو انتها در هر دو وجه خروجی زیر گراف فعلی دارد یا خیر. | ## جمع‌بندی | در حالی که این یک مفهوم بسیار ساده است (و در زمان خطی اجرا می‌شود) خود روش دچار پیچیدگی پیدا کردن ساخت دنباله است.