On the Crossing Number of Almost Planar Graphs

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

Basic information

Original name

On the Crossing Number of Almost Planar Graphs

Name in Czech

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

Authors

HLINĚNÝ, Petr (203 Czech Republic, guarantor) and Gelasio SALAZAR (484 Mexico)

Edition

4372. vyd. Berlin, Graph Drawing, Symposium GD2006, p. 162-173, 12 pp. 2007

Publisher

Springer Verlag

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

References:

conference

RIV identification code

RIV/00216224:14330/07:00021694

Organization unit

Faculty of Informatics

ISBN

3-540-70903-7

UT WoS

000245272300017

Keywords in English

crossing number; crossing minimization; planarization; crossing critical graphs

Tags

crossing critical graphs, crossing minimization, crossing number, planarization

Tags

International impact, Reviewed

---

Abstract

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.

In Czech

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

---

Links

MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science