D
2015
On Hardness of the Joint Crossing Number
HLINĚNÝ, Petr and Gelasio SALAZAR
Basic information
Original name
On Hardness of the Joint Crossing Number
Authors
HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Gelasio SALAZAR (484 Mexico)
Edition
LNCS 9472. Berlin, International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472, p. 603-613, 11 pp. 2015
Publisher
Springer Verlag
Other information
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Germany
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
Impact factor
Impact factor: 0.402 in 2005
RIV identification code
RIV/00216224:14330/15:00081412
Organization unit
Faculty of Informatics
Keywords in English
joint crossing number; crossing minimization
Tags
International impact, Reviewed
V originále
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.
In Czech
Dokazujeme těžkost problému souběžného nakreslení dvou grafů na stejnou plochu rodu 6 s minimem vzájemných průsečíků.
Links
| GBP202/12/G061, research and development project | | Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI) | | Investor: Czech Science Foundation |
|
Displayed: 1/11/2024 21:29