Průsečíkové číslo téměř planárních grafů

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00024654" target="_blank" >RIV/00216224:14330/06:00024654 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On the Crossing Number of Almost Planar Graphs

Popis výsledku v původním jazyce

Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, and it has strong ties with graph drawing applications. Despite long history of intensive research, there is still no practical ``good'' algorithm forcrossing minimization known. (The problem itself is $NP$-complete.) It is even surprising how little we know about a seemingly simple particular problem --- to minimize the number of crossings in a planar graph plus one edge, which is a building block ina so-called edge-insertion heuristic for crossing minimization. We shall show few examples demonstrating that this particular problem is indeed deeply nontrivial. Unfortunately, the important question of its computational complexity is left open for future research.

Název v anglickém jazyce

On the Crossing Number of Almost Planar Graphs

Popis výsledku anglicky

Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, and it has strong ties with graph drawing applications. Despite long history of intensive research, there is still no practical ``good'' algorithm forcrossing minimization known. (The problem itself is $NP$-complete.) It is even surprising how little we know about a seemingly simple particular problem --- to minimize the number of crossings in a planar graph plus one edge, which is a building block ina so-called edge-insertion heuristic for crossing minimization. We shall show few examples demonstrating that this particular problem is indeed deeply nontrivial. Unfortunately, the important question of its computational complexity is left open for future research.

Druh

O - Ostatní výsledky

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F05%2F0050" target="_blank" >GA201/05/0050: Strukturální vlastnosti a algoritmická složitost diskrétních problémů</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2006

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů