The crossing number of a projective graph is quadratic in the face--width

Varování

Publikace nespadá pod Lékařskou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Prusecikove cislo projektivniho grafu je kvadraticke ve stenove sirce
Autoři	HLINĚNÝ Petr SALAZAR Gelasio GITLER Isidoro LEANOS Jesus
Rok publikování	2008
Druh	Článek v odborném periodiku
Časopis / Zdroj	Electronic Journal of Combinatorics
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	online paper
Obor	Obecná matematika
Klíčová slova	crossing number; projective plane; face-width
Popis	Ukazeme, ze prusecikove cislo projektivniho grafu na kteremkoliv orientovatelnem povrchu roste kvadraticky se stenovou sirkou jeho projektivniho nakresleni. Dusledkem je take aproximacni algoritmus.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti