Parameterized Algorithms for Queue Layouts

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

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)

Cites Work

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

Cited In (5)

• A \(2n-2\) step algorithm for routing in an \(n \times n\) array with constant-size queues
• 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
• Parameterized Algorithms for Queue Layouts

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5014103)