On the Crossing Number of Almost Planar Graphs

HLINĚNÝ, Petr a Gelasio SALAZAR. On the Crossing Number of Almost Planar Graphs. In Graph Drawing, Symposium GD2006. 4372. vyd. Berlin: Springer Verlag, 2007, s. 162-173. ISBN 3-540-70903-7.

Základní údaje

Originální název

On the Crossing Number of Almost Planar Graphs

Název česky

O průsečíkovém čísle téměř planárních grafů

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant) a Gelasio SALAZAR (484 Mexiko)

Vydání

4372. vyd. Berlin, Graph Drawing, Symposium GD2006, od s. 162-173, 12 s. 2007

Nakladatel

Springer Verlag

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

conference

Kód RIV

RIV/00216224:14330/07:00021694

Organizační jednotka

Fakulta informatiky

ISBN

3-540-70903-7

UT WoS

000245272300017

Klíčová slova anglicky

crossing number; crossing minimization; planarization; crossing critical graphs

Štítky

crossing critical graphs, crossing minimization, crossing number, planarization

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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 minimization is 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 almost planar 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 almost planar and projective.

Česky

Dokážeme Delta-aproximační algoritmus pro výpočet průsečíkového čísla téměř planárních grafů.

---

Návaznosti

MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky