| Identifikační kód | RIV/00216224:14330/15:00081412 |
|---|
| Název v anglickém jazyce | On Hardness of the Joint Crossing Number |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 2 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646)
Gelasio Salazar (státní příslušnost: MX - Spojené státy mexické) |
|---|
| Popis výsledku v anglickém jazyce | 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 froma special variant of the anchored crossing number problem of Cabello and Mohar. |
|---|
| Klíčová slova oddělená středníkem | joint crossing number; crossing minimization |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/978-3-662-48971-0_51 |
|---|