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 ORCID (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
Article in a journal
Field of Study
10101 Pure mathematics
Country of publisher
Netherlands
Confidentiality degree
is not subject to a state or trade secret
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
Changed: 22/11/2007 13:25, prof. RNDr. Petr Hliněný, Ph.D.
In the original language
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 |
|