On 3-pushdown graphs with large separators

DOI10.1007/BF02122679zbMath0726.05042OpenAlexW2024002153WikidataQ56689196 ScholiaQ56689196MaRDI QIDQ2277467

Zvi Galil, Endre Szemerédi, Ravindran Kannan

Publication date: 1989

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02122679

zbMATH Keywords

separator3-pushdown graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)

Related Items

Stack-number is not bounded by queue-number, Characterisations and examples of graph classes with bounded expansion, Layouts of Expander Graphs, On exteriority notions in book embeddings and treewidth

Cites Work

• Unnamed Item
• On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines
• Graph-theoretic properties in computational complexity
• Characterizations of outerplanar graphs
• Unraveling k-page graphs
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• Applications of a Planar Separator Theorem
• On Time Versus Space
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design