2007
The crossing number of a projective graph is quadratic in the face--width (Extended abstract)
HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER a Jesus LEANOSZákladní údaje
Originální název
The crossing number of a projective graph is quadratic in the face--width (Extended abstract)
Název česky
Průsečíkové číslo projektivních grafů je kvadratické ve stěnové šířce
Autoři
HLINĚNÝ, Petr (203 Česká republika, garant), Gelasio SALAZAR (484 Mexiko), Isidoro GITLER (484 Mexiko) a Jesus LEANOS (484 Mexiko)
Vydání
Electronic Notes in Discrete Mathematics, Elsevier, 2007, 1571-0653
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Kód RIV
RIV/00216224:14330/07:00020424
Organizační jednotka
Fakulta informatiky
UT WoS
000254150200003
Klíčová slova anglicky
crossing number; projective plane; face-width; grid
Štítky
Příznaky
Mezinárodní význam, Recenzováno
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.
Česky
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.
Návaznosti
| GA201/05/0050, projekt VaV |
| ||
| 1M0545, projekt VaV |
|