Parameterized algorithms for book embedding problems

DOI10.1007/978-3-030-35802-0_28zbMath1482.68170arXiv1908.08911OpenAlexW2990669808MaRDI QIDQ2206870

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

Publication date: 26 October 2020

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

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

Grid recognition: classical and parameterized computational perspectives ⋮ On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering ⋮ On fixed-order book thickness parameterized by the pathwidth of the vertex ordering ⋮ Orthogonal planarity testing of bounded treewidth graphs ⋮ Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis

Cites Work

• 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
• 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)\)