Stack and Queue Layouts via Layered Separators

DOI10.1007/978-3-319-50106-2_39zbMath1478.68231arXiv1608.06458OpenAlexW2963134185MaRDI QIDQ2961542

Fabrizio Frati, Vida Dujmović

Publication date: 21 February 2017

Published in: Lecture Notes in Computer Science, Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

bounded stack-number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (18)

Clustered 3-colouring graphs of bounded degree ⋮ Planar drawings with few slopes of Halin graphs and nested pseudotrees ⋮ On the queue number of planar graphs ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Separating layered treewidth and row treewidth ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ The Rique-number of graphs ⋮ An improved upper bound on the queue number of planar graphs ⋮ Linear layouts of bipartite planar graphs ⋮ Lazy queue layouts of posets ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Track layouts, layered path decompositions, and leveled planarity ⋮ Queue layouts of planar 3-trees ⋮ Queue layouts of planar 3-trees ⋮ Planar Graphs of Bounded Degree Have Bounded Queue Number ⋮ On mixed linear layouts of series-parallel graphs ⋮ Lazy Queue Layouts of Posets ⋮ On Mixed Linear Layouts of Series-Parallel Graphs

Cites Work

• Unnamed Item
• Graph layouts via layered separators
• Embedding planar graphs in four pages
• Graphs drawn with few crossings per edge
• Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
• Layered separators in minor-closed graph classes with applications
• The book thickness of 1-planar graphs is constant
• Approximation Algorithms for Independent Sets in Map Graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Genus, Treewidth, and Local Crossing Number
• Map graphs
• New bounds on the edge number of ak-map graph
• A Separator Theorem for Planar Graphs
• Graphs with E Edges Have Pagenumber O(√E)
• Genus g Graphs Have Pagenumber O(√g)
• Layout of Graphs with Bounded Tree-Width
• On the Queue Number of Planar Graphs

This page was built for publication: Stack and Queue Layouts via Layered Separators