HLINĚNÝ, Petr a Gelasio SALAZAR. On the Crossing Number of Almost Planar Graphs. In Graph Drawing, Symposium GD2006. 4372. vyd. Berlin: Springer Verlag. s. 162-173. ISBN 3-540-70903-7. 2007.
Další formáty:   BibTeX LaTeX RIS
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
Originální 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í
WWW 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
Změnil Změnil: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Změněno: 23. 6. 2009 11:39.
Anotace
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.
Anotace č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ěrNá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 VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky
VytisknoutZobrazeno: 29. 3. 2024 14:52