Crossing number of almost planar graphs

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Crossing number of almost planar graphs

Original language description

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.

Czech name

Crossing number of almost planar graphs

Czech description

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.

Type

M - Conference organization

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2006

Confidentiality

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

Event location

Canada

Event country

CA - CANADA

Event starting date

—

Event ending date

—

Total number of attendees

37

Foreign attendee count

35

Type of event by attendee nationality

WRD - Celosvětová akce