文章基本信息

标题：Layouts of Expander Graphs
本地全文：下载
作者：Vida Dujmovič ; Anastasios Sidiropoulos ; David R. Wood 等
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2016
卷号：2016
页码：1-21
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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
关键词：expander graph; monotone layout; book embedding; stack layout; queue layout;track layout; thickness