Parameterized Algorithms for Queue Layouts

DOI10.1007/978-3-030-68766-3_4OpenAlexW3134198176MaRDI QIDQ5014103

Martin Nöllenburg, Fabrizio Montecchiani, Robert Ganian, Sujoy Bhore

Publication date: 1 December 2021

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexitykernelizationvertex cover numberqueue numbertreedepth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (4)

Parameterized Algorithms for Queue Layouts ⋮ Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number ⋮ Fixed-parameter tractability for book drawing with bounded number of crossings per edge ⋮ Parameterized approaches to orthogonal compaction

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• Graph layouts via layered separators
• On the queue-number of graphs with bounded tree-width
• Improved upper bounds for vertex cover
• Embedding planar graphs in four pages
• Track layouts, layered path decompositions, and leveled planarity
• The complexity landscape of decompositional parameters for ILP
• Mixed linear layouts: complexity, heuristics, and experiments
• Computing straight-line 3D grid drawings of graphs in linear volume
• Layered separators in minor-closed graph classes with applications
• The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
• Laying Out Graphs Using Queues
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Mixed Linear Layouts of Planar Graphs
• Planar Graphs Have Bounded Queue-Number
• Parameterized Algorithms for Book Embedding Problems
• A Faster Parameterized Algorithm for Treedepth
• Planar Graphs of Bounded Degree Have Bounded Queue Number
• Layout of Graphs with Bounded Tree-Width
• On the Queue Number of Planar Graphs
• Parameterized Algorithms
• Sorting Using Networks of Queues and Stacks

This page was built for publication: Parameterized Algorithms for Queue Layouts