طرح‌بندی گراف: تبدیل طرح یک-پشته به طرح دو-صف
الموضوعات :
1 - فارغ التحصیل ارشد، دانشکده ریاضی و علوم کامپیوتر، دانشگاه امیرکبیر
2 - استادیار دانشکده ریاضی و علوم کامپیوتر، دانشگاه امیرکبیر
الکلمات المفتاحية: Graph Drawing, Graph Queue Layout, Graph Layout, Graph Stack layout,
ملخص المقالة :
طرح‌بندی یک گراف یافتن ترتیبی خطی به رئوس آن و بخش‌بندی یال‌های آن به صف‌ها یا پشته‌ها با توجه به ترتیب اتخاذ شده می‌باشد. در این مقاله هدف ما پیدا کردن یک رابطه میان طرح پشته و طرح صف یک گراف دلخواه است و یک روش برای تبدیل این دو طرح به یکدیگر ارائه خواهیم کرد. الگوریتمی ارائه می‌کنیم که طرح یک-پشته هر گرافی را به به طرح دو-صف آن گراف تبدیل می‌کند و درستی الگوریتم را اثبات می‌کنیم. این روش، بطور مسقیم و بدون در نظر گرفتن گراف اصلی و خواص آن، طرح پشته‌ی یک گراف را تبدیل به یک طرح صف می‌کند. به عنوان نتیجه، این روش می‌تواند کمک کند که اگر برای دسته‌ای خاص از گراف‌ها عدد پشته محدود داشته باشیم، ممکن است بدون تحلیل مستقیم طرح صف برای این دسته از گراف‌ها به عدد صف مناسب و محدودی دست بیابیم. بنابراین الگوریتم ارائه شده در اینجا انگیزه‌ای برای یافتن الگوریتم‌های مشابه برای تبدیل طرح‌های خطی به یکدیگر و یافتن پارامتر‌های محدود کننده بهتر و بهینه‌تر برای آن‌ها خواهد بود.
[1] Bekos, M. A., Kaufmann, M., Klute, F., Pupyrev, S., Raftopoulou, C., & Ueckerdt, T. (2020). Four Pages Are Indeed Necessary for Planar Graphs. arXiv preprint arXiv:2004.07630.
[2] Dujmović, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., & Wood, D. R. (2020). Planar graphs have bounded queue-number. Journal of the ACM (JACM), 67(4), 1-38.
[3] Merker, L., & Ueckerdt, T. (2020). The Local Queue Number of Graphs with Bounded Treewidth. arXiv preprint arXiv:2008.05392.
[4] Pupyrev, S. (2017, September). Mixed linear layouts of planar graphs. In International Symposium on Graph Drawing and Network Visualization (pp. 197-209). Springer, Cham.
[5] Dujmović, V., & Frati, F. (2016, September). Stack and queue layouts via layered separators. In International Symposium on Graph Drawing and Network Visualization (pp. 511-518). Springer, Cham.
[6] Wiechert, V. (2016). On the queue-number of graphs with bounded tree-width. arXiv preprint arXiv:1608.06091.
[7] Dujmović, V. (2015). Graph layouts via layered separators. Journal of Combinatorial Theory, Series B, 110, 79-89.
[8] Di Battista, G., Frati, F., & Pach, J. (2013). On the queue number of planar graphs. SIAM Journal on Computing,
42(6), 2243-2285.
[9] Dujmović, V., & Wood, D. R. (2004). On linear layouts of graphs.
[10] Blankenship, R. L. (2003). Book embeddings of graphs.
[11] Ganley, J. L., & Heath, L. S. (2001). The pagenumber of k-trees is O (k). Discrete Applied Mathematics, 109(3), 215-221.
[12] Heath, L. S., & Rosenberg, A. L. (1992). Laying out graphs using queues. SIAM Journal on Computing, 21(5), 927-958.
[13] Yannakakis, M. (1989). Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38(1), 36-67.
[14] Heath, L. S. (1987). Embedding outerplanar graphs in small books. SIAM Journal on Algebraic Discrete Methods, 8(2), 198-218.
[15] Buss, J. F., & Shor, P. W. (1984, December). On the pagenumber of planar graphs. In Proceedings of the sixteenth annual ACM symposium on Theory of computing (pp. 98-100).
[16] Heath, L. (1984, October). Embedding planar graphs in seven pages. In 25th Annual Symposium onFoundations of Computer Science, 1984. (pp. 74-83). IEEE.
[17] Rosenberg, A. L. (1983). The Diogenes approach to testable fault-tolerant arrays of processors. IEEE Transactions on Computers,(10),902-910.
[18] Bernhart, F., & Kainen, P. C. (1979). The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3), 320-331.
[19] Ollmann, T., & Hoffman, F., & Levow, R., & Thomas, R. (1973). On the book thicknesses of various graphs. Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. VIII, (pp. 459)
[20] Tarjan, R. (1972). Sorting using networks of queues and stacks. Journal of the ACM (JACM), 19(2), 341-346.
