Crossing number of almost planar graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F06%3A00013588" target="_blank" >RIV/61989100:27240/06:00013588 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical ``good'' algorithm for crossing minimizationis known (this is hardly surprising, since the problem itself is NP-complete). Even more surprising is how little we know about a seemingly simple particular pro-blem: to minimize the number of crossings in an {it almost planar} graph, that is, a graphwith an edge whose removal leaves a planar graph. This problem is in turn a building block in an edge--insertion heuristic for crossing minimization. We shall give some examples demonstrating that this particular problem is indeed deeply nontrivial. Mostremarkably, the important question of its computational complexity remains an open problem.

Název v anglickém jazyce

Crossing number of almost planar graphs

Popis výsledku anglicky

Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical ``good'' algorithm for crossing minimizationis known (this is hardly surprising, since the problem itself is NP-complete). Even more surprising is how little we know about a seemingly simple particular pro-blem: to minimize the number of crossings in an {it almost planar} graph, that is, a graphwith an edge whose removal leaves a planar graph. This problem is in turn a building block in an edge--insertion heuristic for crossing minimization. We shall give some examples demonstrating that this particular problem is indeed deeply nontrivial. Mostremarkably, the important question of its computational complexity remains an open problem.

Druh

M - Uspořádání konference

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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ů

Místo konání akce

Canada

Stát konání akce

CA - Kanada

Datum zahájení akce

—

Datum ukončení akce

—

Celkový počet účastníků

37

Počet zahraničních účastníků

35

Typ akce podle státní přísl. účastníků

WRD - Celosvětová akce