Layouts of Expander Graphs

DOI10.4086/cjtcs.2016.001zbMath1347.68282arXiv1501.05020OpenAlexW2962908332MaRDI QIDQ3466402

David R. Wood, Anastasios Sidiropoulos, Vida Dujmović

Publication date: 1 February 2016

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.05020

zbMATH Keywords

thicknessbook embeddingexpander graphqueue layoutstack layouttrack layoutmonotone layout

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Stack-number is not bounded by queue-number, Layered separators in minor-closed graph classes with applications, Structure of Graphs with Locally Restricted Crossings, Two Results on Layered Pathwidth and Linear Layouts, Track layouts, layered path decompositions, and leveled planarity, Defective and clustered choosability of sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expansion in SL\(_2(\mathbb R)\) and monotone expanders
• Crossings in grid drawings
• Towards dimension expanders over finite fields
• Characterisations and examples of graph classes with bounded expansion
• Volume requirements of 3D upward drawings
• Expanders and dimensional expansion
• On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines
• The book thickness of a graph
• A new way to represent links. One-dimensional formalism and untangling technology
• The thickness of graphs: A survey
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• On 3-pushdown graphs with large separators
• Graph treewidth and geometric thickness parameters
• Layered separators in minor-closed graph classes with applications
• Grad and classes with bounded expansion. II: Algorithmic aspects
• On tree width, bramble size, and expansion
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Expander graphs and their applications
• An Elementary Construction of Constant-Degree Expanders
• Unraveling k-page graphs
• A Separator Theorem for Planar Graphs
• Laying Out Graphs Using Queues
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Geometric Thickness of Complete Graphs
• Layout of Graphs with Bounded Tree-Width
• On the book thickness of $k$-trees
• On the Queue Number of Planar Graphs