Connecting the dots (with minimum crossings)

DOI10.4230/LIPICS.SOCG.2019.7OpenAlexW2946078147MaRDI QIDQ5088932FDOQ5088932

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

Publication date: 18 July 2022

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

Recommendations

• Some provably hard crossing number problems
• Algorithms and Computation
• Metro-line crossing minimization: hardness, approximations, and tractable cases
• On graph crossing number and edge planarization
• Graph Drawing

zbMATH Keywords

FPT algorithmparameterized complexitypolynomial kernelcrossing minimizationW[1-hardness]

Mathematics Subject Classification ID

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

Cites Work

• Graph drawing software
• Introduction to algorithms.
• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Paths, Trees, and Flowers
• Node-Deletion NP-Complete Problems
• Parameterized algorithms
• The graph crossing number and its variants: a survey
• Crossing Number is NP-Complete
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Algorithms for drawing graphs: An annotated bibliography
• Crossing number is hard for cubic graphs
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Computing crossing numbers in quadratic time
• On the parameterized complexity of multiple-interval graph problems
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• Bottleneck non-crossing matching in the plane
• Drawing graphs in two layers
• Title not available (Why is that?)
• Edge crossings in drawings of bipartite graphs
• Graph Drawing
• The complexity of detecting crossingfree configurations in the plane
• Title not available (Why is that?)
• Counting and enumerating crossing-free geometric graphs
• Noncrossing Subgraphs in Topological Layouts
• Swapping labeled tokens on graphs
• Approximation and hardness of token swapping
• A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
• Kernelization. Theory of parameterized preprocessing
• A bottleneck matching problem with edge-crossing constraints
• Approximating the bottleneck plane perfect matching of a point set
• Algorithms for Multi-criteria One-Sided Boundary Labeling
• Optimal crossing-free Hamiltonian circuit drawings of \(K_n\)
• Counting crossing-free structures
• Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
• Crossing number is hard for kernelization
• Title not available (Why is that?)

Cited In (3)

• Parameterized analysis and crossing minimization problems
• "CONNECT-THE-DOTS" TREE MAPS
• Grid recognition: classical and parameterized computational perspectives

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

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