Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Abstract: The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar.
Recommendations
Cited in
(6)- Parameterized analysis and crossing minimization problems
- Low-dimensional topology. Abstracts from the workshop held January 15--21, 2023
- Short topological decompositions of non-orientable surfaces
- Crossing number is NP-hard for constant path-width (and tree-width)
- Complexity of anchored crossing number and crossing number of almost planar graphs
- A unified FPT framework for crossing number problems
This page was built for publication: On hardness of the joint crossing number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459898)
