Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1323060,
author = {Hliněný, Petr and Salazar, Gelasio},
address = {Berlin},
booktitle = {International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472},
doi = {http://dx.doi.org/10.1007/978-3-662-48971-0_51},
edition = {LNCS 9472},
editor = {Khaled Elbassioni, Kazuhisa Makino},
keywords = {joint crossing number; crossing minimization},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin},
isbn = {978-3-662-48970-3},
pages = {603-613},
publisher = {Springer Verlag},
title = {On Hardness of the Joint Crossing Number},
year = {2015}
}
TY - JOUR
ID - 1323060
AU - Hliněný, Petr - Salazar, Gelasio
PY - 2015
TI - On Hardness of the Joint Crossing Number
PB - Springer Verlag
CY - Berlin
SN - 9783662489703
KW - joint crossing number
KW - crossing minimization
N2 - 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.
ER -
HLINĚNÝ, Petr and Gelasio SALAZAR. On Hardness of the Joint Crossing Number. In Khaled Elbassioni, Kazuhisa Makino. \textit{International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472}. LNCS 9472. Berlin: Springer Verlag, 2015, p.~603-613. ISBN~978-3-662-48970-3. Available from: https://dx.doi.org/10.1007/978-3-662-48971-0\_{}51.
|
