Chicago Journal of Theoretical Computer Science

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


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

January 14, 2016


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.

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

DOI: 10.4086/cjtcs.2016.001

[] Volume 2015, Article 4 [] Article 2
[back] Volume 2016 [back] Published articles
[CJCTS home]