The crossing number of a projective graph is quadratic in the face--width (Extended abstract)

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Průsečíkové číslo projektivních grafů je kvadratické ve stěnové šířce
Autoři

HLINĚNÝ Petr SALAZAR Gelasio GITLER Isidoro LEANOS Jesus

Rok publikování 2007
Druh Článek v odborném periodiku
Časopis / Zdroj Electronic Notes in Discrete Mathematics
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.