O průsečíkovém čísle 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%2F07%3A00021694" target="_blank" >RIV/00216224:14330/07:00021694 - 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, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical ``good'' algorithm for crossing minimizationis known (that 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 graph with an edge whose removal leaves a planar graph. This problem is in turn a building block in an ``edge insertion'' heuristic for crossing minimization. In this paper we prove a constant factor approximation algorithm for the crossing number of almostplanar graphs with bounded degree. On the other hand, we demonstrate nontriviality of the crossing minimization problem on almost planar graphs by exhibiting several examples, among them new families of crossing critical graphs which are

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, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical ``good'' algorithm for crossing minimizationis known (that 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 graph with an edge whose removal leaves a planar graph. This problem is in turn a building block in an ``edge insertion'' heuristic for crossing minimization. In this paper we prove a constant factor approximation algorithm for the crossing number of almostplanar graphs with bounded degree. On the other hand, we demonstrate nontriviality of the crossing minimization problem on almost planar graphs by exhibiting several examples, among them new families of crossing critical graphs which are

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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ů

Název statě ve sborníku

Graph Drawing, Symposium GD2006

ISBN

3-540-70903-7

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Springer Verlag

Místo vydání

Berlin

Místo konání akce

TH Karlsruhe, Germany

Datum konání akce

17. 9. 2006

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000245272300017