Published by the Department of Computer Science, The University of Chicago.
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
david DOT wood AT monash DOT edu
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.