On Hardness of the Joint Crossing Number

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr SALAZAR Gelasio

Year of publication 2015
Type Article in Proceedings
Conference International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-662-48971-0_51
Field Informatics
Keywords joint crossing number; crossing minimization
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.