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

• 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
• 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