Abstract
We consider the two problems of embedding graphs in a minimum number of pages and ordering the vertices of graphs in the form of queue layouts. We show that the class of 2-trees requires 2-pages for a book embedding and 3-queues for a queue layout. The first result is new and the latter result extends known results on subclasses of planar graphs.
Preview
Unable to display preview. Download preview PDF.
References
A.L.Rosenberg, “The DIOGENES approach to testable fault-tolerant arrays”, IEEE Transaction on Computer, C-32, 1983, pp.902–910.
F.Chung, T.Leighton, A.L.Rosenberg, “Embedding graphs in books: A Lay-out problem with applications to VLSI Design”, SIAM Jl. on Algebraic and Discrete Methods, 8, 1987, pp.33–58.
F.Bernhart, P.C.Kainen, “The book thickness of a graph”, J. Comb. Theory, Ser.B, 27, 1979, pp.320–331.
L.S. Heath, A. Rosenberg, “Laying out graphs using queues”, SIAM Jl. on Computing, 21, 1992, pp.927–958.
S.M.Malitz, “Graphs with E edges have pagenumber O(√E)”, J. Algorithms, 17, 1994, pp. 71–84, 85–109.
S. Moran and Y. Wolfsthal, “Two-page book embedding of trees under vertex-neighborhood constraints”, Discrete Appl. Math., 43, 1993, pp. 233–41.
B.Obrenic, “Embedding deBruijn and shuffle-exchange graphs in five pages”, Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pp.137–146, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rengarajan, S., Veni Madhavan, C.E. (1995). Stack and queue number of 2-trees. In: Du, DZ., Li, M. (eds) Computing and Combinatorics. COCOON 1995. Lecture Notes in Computer Science, vol 959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0030834
Download citation
DOI: https://doi.org/10.1007/BFb0030834
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60216-3
Online ISBN: 978-3-540-44733-7
eBook Packages: Springer Book Archive