Detailed Information on Publication Record
2007
The crossing number of a projective graph is quadratic in the face--width (Extended abstract)
HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER and Jesus LEANOSBasic information
Original name
The crossing number of a projective graph is quadratic in the face--width (Extended abstract)
Name in Czech
Průsečíkové číslo projektivních grafů je kvadratické ve stěnové šířce
Authors
HLINĚNÝ, Petr (203 Czech Republic, guarantor), Gelasio SALAZAR (484 Mexico), Isidoro GITLER (484 Mexico) and Jesus LEANOS (484 Mexico)
Edition
Electronic Notes in Discrete Mathematics, Elsevier, 2007, 1571-0653
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10101 Pure mathematics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
RIV identification code
RIV/00216224:14330/07:00020424
Organization unit
Faculty of Informatics
UT WoS
000254150200003
Keywords in English
crossing number; projective plane; face-width; grid
Tags
International impact, Reviewed
Změněno: 22/11/2007 13:25, prof. RNDr. Petr Hliněný, Ph.D.
V originále
We show that for each integer $g\geq0$ there is a constant $c>0$ such that every graph that embeds in the projective plane with sufficiently large face--width $r$ has crossing number at least $c.r^2$ in the orientable surface of genus $g$. As a corollary, we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree.
In Czech
Dokážeme, že pro každé g existuje konstanta c>0 taková, že každý graf nakreslený v projektivní rovině se stěnovou šířkou r má průsečíkové číslo c.r^2 na orientovaném povrchu rodu g. Důsledkem je také aproximační algoritmus.
Links
| GA201/05/0050, research and development project |
| ||
| 1M0545, research and development project |
|