Parameterized Algorithms for Book Embedding Problems

DOI10.7155/jgaa.00526zbMath1451.05222OpenAlexW3021553782MaRDI QIDQ5141644

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

Publication date: 18 December 2020

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00526

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

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 analysis and crossing minimization problems ⋮ Untangling circular drawings: algorithms and complexity ⋮ Parameterized approaches to orthogonal compaction ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Parameterized Algorithms for Queue Layouts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two-page book embeddings of 4-planar graphs
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• Improved upper bounds for vertex cover
• RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties
• Graph minors. I. Excluding a forest
• Embedding planar graphs in four pages
• The book thickness of a graph
• The vertex separation number of a graph equals its path-width
• 1-page and 2-page drawings with bounded number of crossings per edge
• SAT-encodings for special treewidth and pathwidth
• The complexity landscape of decompositional parameters for ILP
• Graph treewidth and geometric thickness parameters
• Graph Theory
• The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. II. Algorithmic aspects of tree-width
• Parameterized Complexity of 1-Planarity
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• The complexity of colouring circle graphs
• Crossing minimization in linear embeddings of graphs
• On the book thickness of $k$-trees
• Parameterized Algorithms
• Linear ordering based MIP formulations for the vertex separation or pathwidth problem
• The pagenumber of \(k\)-trees is \(O(k)\)

This page was built for publication: Parameterized Algorithms for Book Embedding Problems