On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering

DOI10.1016/j.tcs.2021.04.021zbMath1482.68178OpenAlexW3157354915MaRDI QIDQ2034395

Jingui Huang, Jianxin Wang, Yunlong Liu, Jie Chen

Publication date: 22 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.04.021

zbMATH Keywords

parameterized algorithmkernel lower boundfixed-order book thicknesspathwidth of the vertex ordering

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

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 analysis and crossing minimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The vertex separation number of a graph equals its path-width
• Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
• Parameterized algorithms for book embedding problems
• The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
• New Limits to Classical and Quantum Instance Compression
• The Complexity of Coloring Circular Arcs and Chords
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Experimental Evaluation of Book Drawing Algorithms
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Kernelization Lower Bounds by Cross-Composition
• Parameterized (Approximate) Defective Coloring
• Parameterized Algorithms for Book Embedding Problems

This page was built for publication: On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering