CJTCS Volume 2016 Article 1

Volume 2016

Article 1

Published by the Department of Computer Science, The University of Chicago.

Layouts of Expander Graphs

Vida Dujmovič
School of Computer Science and Electrical Engineering
University of Ottawa
Ottawa, Canada
vida DOT dujmovic AT uottawa DOT ca

Anastasios Sidiropoulos
Department of Computer Science and Engineering, and Department of Mathematics
Ohio State University
Columbus, Ohio, USA
spirodopoulos AT gmail DOT com

and

David R. Wood
School of Mathematical Sciences
Monash University
Melbourne, Australia
david DOT wood AT monash DOT edu

January 14, 2016

Abstract

Bourgain and Yehudayoff recently constructed $O(1)$-monotone bipartite expanders. By combining this result with a generalisation of the unraveling method of Kannan, we construct 3-monotone bipartite expanders, which is best possible. We then show that the same graphs admit 3-page book embeddings, 2-queue layouts, 4-track layouts, and have simple thickness 2. All these results are best possible.

The article: PDF (386 KB)
Source material: ZIP (148 KB)
BibTeX entry for this article (291 bytes)

Submitted January 20, 2015, revised November 26, 2015 and January 3, 2016, published January 14, 2016.

DOI: 10.4086/cjtcs.2016.001

Licensed under a Creative Commons Attribution License

Volume 2015, Article 4

Article 2

Volume 2016 [back]

Published articles