Parameterized Algorithms for Queue Layouts

DOI10.1007/978-3-030-68766-3_4MaRDI QIDQ5014103zbMATH OpenOpenAlexFDO

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

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

• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• A faster parameterized algorithm for treedepth
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Computing straight-line 3D grid drawings of graphs in linear volume
• Embedding planar graphs in four pages
• Fundamentals of parameterized complexity
• Graph layouts via layered separators
• Improved upper bounds for vertex cover
• Layered separators in minor-closed graph classes with applications
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Mixed linear layouts of planar graphs
• Mixed linear layouts: complexity, heuristics, and experiments
• On the Queue Number of Planar Graphs
• On the queue-number of graphs with bounded tree-width
• Parameterized algorithms
• Parameterized algorithms for book embedding problems
• Planar graphs have bounded queue-number
• Planar graphs of bounded degree have bounded queue number
• Sorting Using Networks of Queues and Stacks
• Sparsity. Graphs, structures, and algorithms
• Stacks, queues and tracks: layouts of graph subdivisions
• The complexity landscape of decompositional parameters for ILP
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• Track layouts, layered path decompositions, and leveled planarity

Cited in

(5)

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

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)