Layouts of expander graphs

Vida Dujmovic, Anastasios Sidiropoulos, David R Wood

Research output: Contribution to journalArticleResearchpeer-review

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.
Original languageEnglish
Article number1
Number of pages21
JournalChicago Journal of Theoretical Computer Science
Volume2016
DOIs
Publication statusPublished - 2016

Keywords

  • expander graph
  • monotone layout
  • book embedding
  • stack layout
  • queue layout
  • track layout
  • thickness

Cite this