Detailed Information on Publication Record
2006
On the Crossing Number of Almost Planar Graphs
HLINĚNÝ, Petr and Gelasio SALAZARBasic information
Original name
On the Crossing Number of Almost Planar Graphs
Name in Czech
Průsečíkové číslo téměř planárních grafů
Authors
HLINĚNÝ, Petr (203 Czech Republic, guarantor) and Gelasio SALAZAR (484 Mexico)
Edition
14th International Symposium on Graph Drawing, GD 2006, 2006
Other information
Language
English
Type of outcome
Konferenční abstrakt
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:
RIV identification code
RIV/00216224:14330/06:00024654
Organization unit
Faculty of Informatics
UT WoS
000245272300017
Keywords in English
graph; crossing number; approximation algorithm
Tags
International impact
Změněno: 27/6/2008 12:42, Ing. Dana Komárková
V originále
Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, and it has strong ties with graph drawing applications. Despite long history of intensive research, there is still no practical ``good'' algorithm for crossing minimization known. (The problem itself is $NP$-complete.) It is even surprising how little we know about a seemingly simple particular problem --- to minimize the number of crossings in a planar graph plus one edge, which is a building block in a so-called edge-insertion heuristic for crossing minimization. We shall show few examples demonstrating that this particular problem is indeed deeply nontrivial. Unfortunately, the important question of its computational complexity is left open for future research.
In Czech
Věnujeme se zdánlivě lehkému a přesto překvapivě obtížnému problému minimalizace průsečíků planárního grafu s jednou hranou navíc. Podáváme aproximační algoritmus.
Links
| GA201/05/0050, research and development project |
| ||
| MSM0021622419, plan (intention) |
|