Approximating the Crossing Number of Toroidal Graphs

HLINĚNÝ, Petr a Gelasio SALAZAR. Approximating the Crossing Number of Toroidal Graphs. In International Symposium on Algorithms and Computation (ISAAC 2007). Berlin: Springer Verlag, 2007, s. 148-159. ISBN 978-3-540-77118-0.

Základní údaje

• Originální název: Approximating the Crossing Number of Toroidal Graphs
• Název česky: Aproximace průsečíkového čísla toroidálních grafů
• Autoři: HLINĚNÝ, Petr (203 Česká republika, garant) a Gelasio SALAZAR (484 Mexiko).
• Vydání: Berlin, International Symposium on Algorithms and Computation (ISAAC 2007), s. 148-159, 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 doi
• Kód RIV: RIV/00216224:14330/07:00020423
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-3-540-77118-0
• UT WoS: 000252881000015
• Klíčová slova anglicky: crossing number; crossing minimization; approximation
• Štítky: APPROXIMATION, crossing minimization, crossing number
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

CrossingNumber is one of the most challenging algorithmic problems in topological graph theory, with applications to graph drawing and VLSI layout. No polynomial time constant approximation algorithm is known for this NP-complete problem. We prove that a natural approach to planar drawing of toroidal graphs (used already by Pach and T\'oth) gives a polynomial time constant approximation algorithm for the crossing number of toroidal graphs with bounded degree. In this proof we present a new ``grid'' theorem on toroidal graphs.

Anotace česky

Dokážeme polynomiální aproximační algoritmus pro výpočet průsečíkového čísla toroidálních grafů s omezeným stupněm.

Návaznosti

• GA201/05/0050, projekt VaV: Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů