Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Start single access now
Access for companies
12th International Engine Congress 2025 | 25. + 26. February 2025

Meeting Place for the Powertrain and Sustainable Fuels Community

The congress will examine the future role of the internal combustion engine and its non-fossil fuels from a global perspective with leading experts. Be part of it! More information and booking options are available on our website.
EXTENDED SEARCH
Log in
Top
Published in:
Read chapter Read first chapter

2024 | OriginalPaper | Chapter

Deques on a Torus

Authors : Thomas McKenzie, Shannon Overbay

Published in: Combinatorics, Graph Theory and Computing

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We provide an overview of graphical representations of stacks, queues, and deques. In the case of a cylinder book, corresponding to a deque, we give edge bounds and determine the deque number of the complete graph. We extend the deque in a natural way, forming a toroidal deque. Unlike the other three structures, the toroidal deque can process certain non-planar graphs, including \(K_7\) and the Cartesian product of two cycles.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Tiling With Three Element Sets
next chapter Möbius Book Embeddings
Literature
1.
Auer C., Bachmaier, C., Brandenburg, F.J., Brunne,r W.; Gleißner, A.: Data structures and their planar layouts, Journal of Graph Algorithms and Applications, 22 (2), 207–237 (2018)
2.
Auer, C.: Planar graphs and their duals on cylinder surfaces, Ph.D. Dissertation, University of Passau, (2014)
3.
Bernhart, F., Kainen, P. C.: The book thickness of a graph, Journal of Combinatorial Theory, Series B, 27 (3), 320–331 (1979)MathSciNet
4.
Chen, Y.: Layout of planar products, J. Math. Comput. Sci., 6, 216–229 (2016)
5.
Chung, F. R. K., Leighton, F. T., Rosenberg, A. L.: Embedding graphs in books: A layout problem with applications to VLSI design, SIAM Journal on Algebraic and Discrete Methods, 8 (1), 33–58 (1987)MathSciNetCrossRef
6.
Dujmovic, V., Eppstein, D., Hickingbotham, R., Morin, R., Wood, D. R.: Stack-Number is Not Bounded by Queue-Number. Combinatorica, 42, 151–164 (2022)MathSciNetCrossRef
7.
Dujmovic, V.; Joret, G.; Micek, P.; Morin, P.; Ueckerdt, T.; Wood, D. R.: Planar graphs have bounded queue-number. Journal of the ACM, 67, 1–38 (2020)MathSciNetCrossRef
8.
Dujmovic, V., Wood, D. R.: On linear layouts of graphs, Discrete Mathematics and Theoretical Computer Science, 6 (2), 339–357 (2004)MathSciNet
9.
Harary, F.: Graph Theory, Addison Wesley, Reading, Mass. (1969)
10.
11.
Ollmann, L. T.: On the book thicknesses of various graphs, Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, 8, 459 (1973)MathSciNet
12.
Overbay, S.: Embedding graphs in cylinder and torus books, Journal of Combinatorial Mathematics and Combinatorial Computing, 91, 299–313 (2014)MathSciNet
13.
Overbay, S.: Generalized book embeddings, Ph.D. Dissertation, Colorado State University, Fort Collins, CO, (1998)
14.
Pupyrev, S.: Book embeddings of graph products, arXiv:2007.15102 (2020)
15.
Reghizzi, S. C., Pierluigi, S. P.: Deque automata, languages, and planar graph representations, Theoretical Computer Science, 834, 43–59 (2020)MathSciNetCrossRef
16.
Yang, J., Shao, Z.; Li, Z.: Embedding Cartesian products of some graphs in books, Commun. Math. Res., 34, 253–260 (2018)MathSciNet
Metadata
Title
Deques on a Torus
Authors
Thomas McKenzie
Shannon Overbay
Copyright Year
2024
Book
Combinatorics, Graph Theory and Computing

Print ISBN: 978-3-031-62165-9

Electronic ISBN: 978-3-031-62166-6

Copyright Year: 2024

DOI
https://doi.org/10.1007/978-3-031-62166-6_25

Premium Partner

    Image Credits