Detailed Information on Publication Record
2007
Approximating the Crossing Number of Toroidal Graphs
HLINĚNÝ, Petr and Gelasio SALAZARBasic information
Original name
Approximating the Crossing Number of Toroidal Graphs
Name in Czech
Aproximace průsečíkového čísla toroidálních grafů
Authors
HLINĚNÝ, Petr (203 Czech Republic, guarantor) and Gelasio SALAZAR (484 Mexico)
Edition
Berlin, International Symposium on Algorithms and Computation (ISAAC 2007), p. 148-159, 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:
RIV identification code
RIV/00216224:14330/07:00020423
Organization unit
Faculty of Informatics
ISBN
978-3-540-77118-0
UT WoS
000252881000015
Keywords in English
crossing number; crossing minimization; approximation
Tags
International impact, Reviewed
Změněno: 12/6/2008 10:56, prof. RNDr. Petr Hliněný, Ph.D.
V originále
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.
In Czech
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.
Links
| GA201/05/0050, research and development project |
|