Connecting the dots (with minimum crossings)

DOI10.4230/LIPICS.SOCG.2019.7MaRDI QIDQ5088932zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

FPT algorithmparameterized complexitypolynomial kernelcrossing minimizationW[1-hardness]

Mathematics Subject Classification ID

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

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

Cites work

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

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)