2006
On the Crossing Number of Almost Planar Graphs
HLINĚNÝ, Petr a Gelasio SALAZARZákladní údaje
Originální název
On the Crossing Number of Almost Planar Graphs
Název česky
Průsečíkové číslo téměř planárních grafů
Autoři
HLINĚNÝ, Petr ORCID a Gelasio SALAZAR
Vydání
14th International Symposium on Graph Drawing, GD 2006, 2006
Další údaje
Jazyk
angličtina
Typ výsledku
Konferenční abstrakt
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
Kód RIV
RIV/00216224:14330/06:00024654
Organizační jednotka
Fakulta informatiky
UT WoS
000245272300017
Klíčová slova anglicky
graph; crossing number; approximation algorithm
Štítky
Příznaky
Mezinárodní význam
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.
Česky
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.
Návaznosti
| GA201/05/0050, projekt VaV |
| ||
| MSM0021622419, záměr |
|