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

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