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

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

معیارهای مسطح بودن

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

قضیه Kuratowski که می‌گوید یک گراف مسطح است اگر و تنها اگر شامل یک زیر گراف که زیر بخشی از K₅ (گراف کامل با پنج راس) یا K_3,3 (گراف دو بخشی با ۶ راس که ۳ راس در یک بخش و ۳ بخش در بخش دیگر و هیچ دو یال در یک بخش به هم وصل نیستند) نباشد.
قضیه واگنر که می‌گوید یک گراف مسطح است اگر و تنها اگر شامل یک جزء (زیرگراف انقباضی) که هم ریخت با K₅ یا K_{3,3 است نباشد.}
معیار مسطح بودن Fraysseix–Rosenstiehl گراف‌های مسطح را در اصطلاح چیدن از چپ به راست راس‌ها در جستجوی اول عمق درخت مشخص می‌کند.

معیار مسطح بودن Fraysseix–Rosenstiehl می‌تواند به‌طور مستقیم به عنوان بخشی از الگوریتم برای آزمون مسطح بودن مورد استفاده قرار گیرد در حالی که قضایای Kuratowski و واگنر کاربرد غیرمستقیم دارند: اگر یک الگوریتم می‌توانید یک کپی از K₅ یا K_3,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 (یا K₅ یا K_3,3) محاسبه می‌شود. امروزه این یکی از دو وضعیت فعلی الگوریتم هنری است (یک دیگر از الگوریتم‌های آزمون مسطح بودن الگوریتم de Fraysseix، د مندز و Rosenstiehl^[۱۱]^[۱۲] است).^[۱۳] را برای یک مقایسه عملی با مدل مقدماتی از آزمون بویر و Myrvold planarity ببینید. بعلاوه آزمون بویر–Myrvold برای استخراج چند زیربخش Kuratowski از یک گراف ورودی غیر مسطح در یک زمان در حال اجرا خطی وابسته به خروجی اندازه گسترش یافت.^[۱۴] منبع کد برای آزمون مسطح بودن^[۱۵]^[۱۶] و استخراج متعدد زیربخش‌های Kuratowski^[۱۵] در دسترس عموم است. الگوریتم‌هایی که یک زیرگراف Kuratowski در زمان خطی در راس‌ها پیدا می‌کنند، توسط ویلیامسون در دهه ۱۹۸۰ توسعه یافتند.^[۱۷]

روش ساخت دنباله

یک روش متفاوت از ساخت القایی گراف ۳ بخشی استفاده می‌کند تا به صورت صعودی یک زیر گراف بسازد از گراف G(در نتیجه یک جاسازی مسطح از گراف G).^[۱۸] ساخت و ساز با K_{4 شروع می‌شود} و در چنین راهی تعریف شده‌است که هر گراف حد واسط در راه کامل شدن اجزا که دوباره ۳ بخشی می‌شود قرار می‌گیرد. به خاطر اینکه این نوع گراف‌ها یک جاسازی یکتا دارند، گراف بزرگتر بعدی اگر باز سطحی باشد باید بهبودی از گراف قبلی باشد. این کاهش آزمون مسطح بودن برای در هر مرحله را اجازه می‌دهد که آیا یال اضافه شده بعدی دو انتها در هر دو وجه خروجی زیر گراف فعلی دارد یا خیر. در حالی که این یک مفهوم بسیار ساده است (و در زمان خطی اجرا می‌شود) خود روش دچار پیچیدگی پیدا کردن ساخت دنباله است.

منابع

↑ Hopcroft, John; Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, doi:10.1145/321850.321852.
↑ Mehlhorn, Kurt; Mutzel, Petra (1996), "On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm", Algorithmica, 16: 233–242
↑ Mehlhorn, Kurt; Mutzel, Petra; Näher, Stefan (1993), An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm
↑ Mehlhorn, Kurt; Näher, Stefan (1995), "LEDA: A library of efficient data types and algorithms", CACM, 38 (1): 96–102
↑ Taylor, Martyn G. (2012). Planarity Testing by Path Addition (Ph.D.). University of Kent. Archived from the original on 5 March 2016. Retrieved 26 June 2016.
↑ Lempel, A.; Even, S.; Cederbaum, I. (1967), "An algorithm for planarity testing of graphs", in Rosenstiehl, P. (ed.), Theory of Graphs, New York: Gordon and Breach, pp. 215–232.
↑ (Boyer و Myrvold 2004), p. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms. ”
↑ Chiba, N.; Nishizeki, T.; Abe, A.; Ozawa, T. (1985), "A linear algorithm for embedding planar graphs using PQ–trees", Journal of Computer and Systems Sciences, 30 (1): 54–76, doi:10.1016/0022-0000(85)90004-2.
↑ Shih, W. K.; Hsu, W. L. (1999), "A new planarity test", Theoretical Computer Science, 223 (1–2): 179–191, doi:10.1016/S0304-3975(98)00120-0.
↑ Boyer, John M.; Myrvold, Wendy J. (2004), "On the cutting edge: simplified O(n) planarity by edge addition" (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273, doi:10.7155/jgaa.00091, archived from the original (PDF) on 15 July 2006, retrieved 26 June 2016.
↑ de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1030, doi:10.1142/S0129054106004248.
↑ Brandes, Ulrik (2009), The left-right planarity test (PDF).
↑ Boyer, John M.; Cortese, P. F.; Patrignani, M.; Battista, G. D. (2003), "Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm", Proc. 11th Int. Symp. Graph Drawing (GD '03), Lecture Notes in Computer Science, vol. 2912, Springer-Verlag, pp. 25–36
↑ Chimani, M.; Mutzel, P.; Schmidt, J. M. (2008), "Efficient extraction of multiple Kuratowski subdivisions", Proc. 15th Int. Symp. Graph Drawing (GD'07), Lecture Notes in Computer Science, vol. 4875, Sydney, Australia: Springer-Verlag, pp. 159–170
↑ ^۱۵٫۰ ^۱۵٫۱ http://www.ogdf.net
↑ http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/boyer_myrvold.html
↑ Williamson, S. G. (1984), "Depth First Search and Kuratowski Subgraphs", Journal Association of Computing Machinery, 31: 681–693, doi:10.1145/1634.322451
↑ Schmidt, Jens M. (2014), The Mondshein Sequence, pp. 967–978, doi:10.1007/978-3-662-43948-7_80 {{citation}}: Unknown parameter |conference= ignored (help)

[1] Hopcroft, John; Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, doi:10.1145/321850.321852.

[2] Mehlhorn, Kurt; Mutzel, Petra (1996), "On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm", Algorithmica, 16: 233–242

[3] Mehlhorn, Kurt; Mutzel, Petra; Näher, Stefan (1993), An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm

[4] Mehlhorn, Kurt; Näher, Stefan (1995), "LEDA: A library of efficient data types and algorithms", CACM, 38 (1): 96–102

[5] Taylor, Martyn G. (2012). Planarity Testing by Path Addition (Ph.D.). University of Kent. Archived from the original on 5 March 2016. Retrieved 26 June 2016.

[6] Lempel, A.; Even, S.; Cederbaum, I. (1967), "An algorithm for planarity testing of graphs", in Rosenstiehl, P. (ed.), Theory of Graphs, New York: Gordon and Breach, pp. 215–232.

[Ref_a-7] (Boyer و Myrvold 2004), p. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms. ”

[8] Chiba, N.; Nishizeki, T.; Abe, A.; Ozawa, T. (1985), "A linear algorithm for embedding planar graphs using PQ–trees", Journal of Computer and Systems Sciences, 30 (1): 54–76, doi:10.1016/0022-0000(85)90004-2.

[9] Shih, W. K.; Hsu, W. L. (1999), "A new planarity test", Theoretical Computer Science, 223 (1–2): 179–191, doi:10.1016/S0304-3975(98)00120-0.

[10] Boyer, John M.; Myrvold, Wendy J. (2004), "On the cutting edge: simplified O(n) planarity by edge addition" (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273, doi:10.7155/jgaa.00091, archived from the original (PDF) on 15 July 2006, retrieved 26 June 2016.

[11] Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1030, doi:10.1142/S0129054106004248.

[Brandes2009-12] Brandes, Ulrik (2009), The left-right planarity test (PDF).

[13] Boyer, John M.; Cortese, P. F.; Patrignani, M.; Battista, G. D. (2003), "Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm", Proc. 11th Int. Symp. Graph Drawing (GD '03), Lecture Notes in Computer Science, vol. 2912, Springer-Verlag, pp. 25–36

[14] Chimani, M.; Mutzel, P.; Schmidt, J. M. (2008), "Efficient extraction of multiple Kuratowski subdivisions", Proc. 15th Int. Symp. Graph Drawing (GD'07), Lecture Notes in Computer Science, vol. 4875, Sydney, Australia: Springer-Verlag, pp. 159–170

[Ref_-15] ۱۵٫۰ ^۱۵٫۱ http://www.ogdf.net

[Ref_b-16] ttp://www.boost.org/doc/libs/1_40_0/libs/graph/doc/boyer_myrvold.html

[17] Williamson, S. G. (1984), "Depth First Search and Kuratowski Subgraphs", Journal Association of Computing Machinery, 31: 681–693, doi:10.1145/1634.322451

[18] Schmidt, Jens M. (2014), The Mondshein Sequence, pp. 967–978, doi:10.1007/978-3-662-43948-7_80 {{citation}}: Unknown parameter |conference= ignored (help)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]

[۱۴]

[۱۵]

[۱۶]

[۱۷]

[۱۸]