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	doi conference
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:	Institut Teoretické Informatiky