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 | |
Rok publikování | 2007 |
Druh | Článek v odborném periodiku |
Časopis / Zdroj | Electronic Notes in Discrete Mathematics |
Fakulta / Pracoviště MU | |
Citace | HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER a Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width (Extended abstract). Electronic Notes in Discrete Mathematics. Elsevier, 2007, roč. 29, C, s. 219-223. ISSN 1571-0653. |
www | |
Obor | Obecná matematika |
Klíčová slova | crossing number; projective plane; face-width; grid |
Popis | 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. |
Související projekty: |