Parameterized analysis and crossing minimization problems
From MaRDI portal
Publication:2172859
DOI10.1016/j.cosrev.2022.100490OpenAlexW4283217425MaRDI QIDQ2172859
Publication date: 16 September 2022
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2022.100490
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Polynomial Time and Parameterized Approximation Algorithms for Boxicity
- Reducing CMSO model checking to highly connected graphs
- Connecting the dots (with minimum crossings)
- The complexity of colouring circle graphs
- Maximum Cut Parameterized by Crossing Number
- Parameterized Algorithms for Book Embedding Problems
- Optimal Distributed Covering Algorithms
- A Practical Approach to Courcelle's Theorem
- Split Contraction
- Minimizing crossings in constrained two-sided circular graph layouts.
- Parameterized Streaming: Maximal Matching and Vertex Cover
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- On the book thickness of $k$-trees
- Data reduction and exact algorithms for clique cover
- Crossing Numbers and Parameterized Complexity
- Line Crossing Minimization on Metro Maps
- Algorithms – ESA 2004
- TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY
- Parameterized Algorithms
- Toward a theory of crossing numbers
- Graph Drawing
- Optimal crossing-free Hamiltonian circuit drawings of \(K_n\)
- The pagenumber of \(k\)-trees is \(O(k)\)
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A faster fixed parameter algorithm for two-layer crossing minimization
- Fundamentals of parameterized complexity
- Bottleneck non-crossing matching in the plane
- A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
- Crossing numbers of graphs with rotation systems
- Crossing number and weighted crossing number of near-planar graphs
- Advice classes of parametrized tractability
- Improved upper bounds for vertex cover
- A linear edge kernel for two-layer crossing minimization
- On miniaturized problems in parameterized complexity theory
- Configurations with few crossings in topological graphs
- On \(k\)-planar crossing numbers
- On low tree-depth decompositions
- Obtaining split graphs by edge contraction
- Approximating the bottleneck plane perfect matching of a point set
- Fixed parameter algorithms for one-sided crossing minimization revisited
- On the parameterized complexity of layered graph drawing
- On problems without polynomial kernels
- Embedding planar graphs in four pages
- The book thickness of a graph
- Some provably hard crossing number problems
- The complexity of detecting crossingfree configurations in the plane
- Drawing graphs in two layers
- Note on \(k\)-planar crossing numbers
- Which crossing number is it anyway?
- Edge dominating set and colorings on graphs with fixed clique-width
- A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
- Computing crossing numbers in quadratic time
- Hardness of approximation for crossing number
- The graph crossing number and its variants: a survey
- Crossing number for graphs with bounded pathwidth
- A tighter insertion-based approximation of the crossing number
- On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
- Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
- Fixed-parameter tractability for book drawing with bounded number of crossings per edge
- Bundled crossings revisited
- On the 2-colored crossing number
- Exact crossing number parameterized by vertex cover
- Sketched representations and orthogonal planarity of bounded treewidth graphs
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- Toroidal grid minors and stretch in embedded graphs
- An improved fixed-parameter algorithm for max-cut parameterized by crossing number
- Approximating the rectilinear crossing number
- Graph treewidth and geometric thickness parameters
- Narrow sieves for parameterized paths and packings
- An annotated bibliography on 1-planarity
- Algorithms for graphs embeddable with few crossings per edge
- Crossing number is hard for cubic graphs
- A fixed-parameter approach to 2-layer planarization
- Parameterized algorithms for fixed-order book drawing with bounded number of crossings per edge
- Vertex Cover: Further Observations and Further Improvements
- A Bottleneck Matching Problem with Edge-Crossing Constraints
- Bundled Crossings in Embedded Graphs
- The Rectilinear Crossing Number of K n : Closing in (or Are We?)
- Ordering Metro Lines by Block Crossings
- Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases
- Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
- Counting crossing-free structures
- FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS
- Milling a Graph with Turn Costs: A Parameterized Complexity Perspective
- Crossing Number is Hard for Kernelization
- Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
- (Meta) Kernelization
- Crossing Number is NP-Complete
- Noncrossing Subgraphs in Topological Layouts
- Two-Layer Planarization: Improving on Parameterized Algorithmics
- On the Number of Crossing‐Free Matchings, Cycles, and Partitions
- Mixing Color Coding-Related Techniques
- On Hardness of the Joint Crossing Number
- Known Algorithms for Edge Clique Cover are Probably Optimal
- The crossing number of a projective graph is quadratic in the face–width
- Complexity of Some Geometric and Topological Problems
- On the Crossing Number of Almost Planar Graphs
- Minimizing Intra-edge Crossings in Wiring Diagrams and Public Transportation Maps
- Fixed-Parameter Tractability for Non-Crossing Spanning Trees
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
- Graph minors. II. Algorithmic aspects of tree-width
- Laying Out Graphs Using Queues
- Bounds for rectilinear crossing numbers
- Nondeterminism within $P^ * $
- Color-coding
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Deciding Parity of Graph Crossing Number
- Maximum Minimal Vertex Cover Parameterized by Vertex Cover
- Crossing Numbers of Graphs
- Parameterized Complexity of 1-Planarity
- Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
- Beyond Outerplanarity
- Clique-width III
- Counting and Enumerating Crossing-free Geometric Graphs
- Matrix Rigidity from the Viewpoint of Parameterized Complexity
- Kernelization
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
This page was built for publication: Parameterized analysis and crossing minimization problems
