طرح‌بندی گراف: تبدیل طرح یک-پشته به طرح دو-صف

محورهای موضوعی : آمار

سپهر مرادی ¹ , زاهد رحمتی ²

1 - فارغ التحصیل ارشد، دانشکده ریاضی و علوم کامپیوتر، دانشگاه امیرکبیر
2 - استادیار دانشکده ریاضی و علوم کامپیوتر، دانشگاه امیرکبیر

تاریخ دریافت : 1400/07/18 تاریخ پذیرش : 1401/03/11 تاریخ انتشار : 1401/08/01

کلید واژه: Graph Drawing, Graph Queue Layout, Graph Layout, Graph Stack layout,

چکیده مقاله :

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

چکیده انگلیسی:

The layout of a graph is finding a linear order for the vertices of the graph such that each of its edges is assigned to exactly one of the stacks (resp. queues) based on the properties of the stack (resp. queue). In this paper, we find a relationship between the stack layout and the queue layout of a graph. In particular, we provide an algorithm for converting a 1-stack layout of any graph into a 2-queue layout of the same graph, and we prove the correction of our algorithm. This method obtains the queue layout from a given stack layout without considering the graph itself and its properties. We hope by generalizing and developing this method one would achieve a queue number (i.e., the smallest number of the queues required by the queue layout of the graph) for some graph categories with almost the same upper and lower bound on their stack number.

منابع و مأخذ:

 

[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.‏