Parameterized algorithms for book embedding problems
From MaRDI portal
Publication:2206870
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
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)\)