Graph Layout: Converting 1-Stack Layout to 2-Queue Layout
Subject Areas : Statistics
Seehr Moradi
1
(Graduated student, Department of Mathematics and Computer Science
Amirkabir University of Technology - Tehran Polytechnic)
Zahed Rahmati
2
(Assistant Professor,
Department of Mathematics and Computer Science, Amirkabir University of Technology)
Keywords: ترسیم گراف, طرحبندی گراف, طرح پشته گراف, طرح صف گراف,
Abstract :
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.
