Connecting the dots (with minimum crossings)

DOI10.4230/LIPIcs.SoCG.2019.7OpenAlexW2946078147MaRDI QIDQ5088932

Meirav Zehavi, Akanksha Agrawal, Grzegorz Guśpiel, Jayakrishnan Madathil, Saket Saurabh

Publication date: 18 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.7

zbMATH Keywords

crossing minimizationparameterized complexitypolynomial kernelFPT algorithmW[1-hardness]

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

Parameterized analysis and crossing minimization problems ⋮ Grid recognition: classical and parameterized computational perspectives

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Bottleneck non-crossing matching in the plane
• Approximating the bottleneck plane perfect matching of a point set
• On the parameterized complexity of multiple-interval graph problems
• The complexity of detecting crossingfree configurations in the plane
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• Algorithms for drawing graphs: An annotated bibliography
• Graph drawing software
• The graph crossing number and its variants: a survey
• Swapping labeled tokens on graphs
• Crossing number is hard for cubic graphs
• A Bottleneck Matching Problem with Edge-Crossing Constraints
• Counting crossing-free structures
• Crossing Number is Hard for Kernelization
• Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
• Crossing Number is NP-Complete
• Noncrossing Subgraphs in Topological Layouts
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
• Node-Deletion NP-Complete Problems
• Kernelization
• Computing crossing numbers in quadratic time
• Paths, Trees, and Flowers
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• Algorithms for Multi-criteria One-Sided Boundary Labeling
• Parameterized Algorithms
• Counting and enumerating crossing-free geometric graphs
• Graph Drawing
• Optimal crossing-free Hamiltonian circuit drawings of \(K_n\)

This page was built for publication: Connecting the dots (with minimum crossings)