Parameterized algorithms for book embedding problems

DOI10.7155/JGAA.00526MaRDI QIDQ5141644zbMATH OpenOpenAlexFDO

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

Publication date 18 December 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

Recommendations

• Parameterized algorithms for book embedding problems
• 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
• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• An improved fixed-parameter algorithm for one-page crossing minimization

Cites work

• 1-page and 2-page drawings with bounded number of crossings per edge
• An improved fixed-parameter algorithm for one-page crossing minimization
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Crossing minimization in linear embeddings of graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar graphs in four pages
• Fundamentals of parameterized complexity
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph theory
• Graph treewidth and geometric thickness parameters
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• scientific article; zbMATH DE number 3499787 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Linear ordering based MIP formulations for the vertex separation or pathwidth problem
• On the book thickness of k-trees
• Parameterized algorithms
• Parameterized complexity of 1-planarity
• RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties
• SAT-encodings for special treewidth and pathwidth
• Sparsity. Graphs, structures, and algorithms
• The book thickness of a graph
• The complexity landscape of decompositional parameters for ILP
• The complexity of colouring circle graphs (extended abstract)
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• The pagenumber of k-trees is O(k)
• The vertex separation number of a graph equals its path-width
• Two-page book embeddings of 4-planar graphs

Cited in

(34)

• 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
• 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
• Parameterized algorithms for book embedding problems
• Parameterized complexity of graph planarity with restricted cyclic orders
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Degree constrained book embeddings
• Parameterized Algorithms for Queue Layouts
• Parameterized algorithms for queue layouts
• An improved fixed-parameter algorithm for one-page crossing minimization
• On the upward book thickness problem: combinatorial and complexity results
• On the upward book thickness problem: combinatorial and complexity results
• Parameterized complexity of graph planarity with restricted cyclic orders
• Untangling circular drawings: algorithms and complexity
• Parameterized approaches to orthogonal compaction
• Parameterized algorithms for fixed-order book drawing with few crossings per edge
• Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover
• Fixed-parameter algorithms for computing RAC drawings of graphs
• Parameterized complexity of simultaneous planarity
• The parametrized complexity of the segment number
• Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
• Weakly leveled planarity with bounded span
• A tight subexponential-time algorithm for two-page book embedding
• Eliminating crossings in ordered graphs
• Weakly leveled planarity with bounded span
• The parameterized complexity of extending stack layouts
• Parameterized approaches to orthogonal compaction
• Drawn tree decomposition: new approach for graph drawing problems
• The parameterized complexity landscape of the unsplittable flow problem
• Recognizing 2-layer and outer k-planar graphs
• Linear layouts revisited: stacks, queues, and exact algorithms
• The parameterized complexity of extending stack layouts

This page was built for publication: Parameterized algorithms for book embedding problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5141644)