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

HLINĚNÝ, Petr; Isidoro GITLER; Gelasio SALAZAR a Jesus LEANOS. The crossing number of a projective graph is quadratic in the face-width. In Czech-Slovak Conference on Graph Theory 2007, Hradec nad Moravicí. 2007. ISBN 978-80-248-1445-2.

Základní údaje

Originální název

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

Název česky

Průsečíkové číslo projektivních grafů je kvadratické ve face-width

Autoři

HLINĚNÝ, Petr ORCID; Isidoro GITLER; Gelasio SALAZAR a Jesus LEANOS

Vydání

Czech-Slovak Conference on Graph Theory 2007, Hradec nad Moravicí, 2007

---

Další údaje

Jazyk

angličtina

Typ výsledku

Konferenční abstrakt

Obor

10101 Pure mathematics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Odkazy

conf

Kód RIV

RIV/00216224:14330/07:00024642

Organizační jednotka

Fakulta informatiky

ISBN

978-80-248-1445-2

UT WoS

000254150200003

Klíčová slova anglicky

crossing number; projective plane

Štítky

crossing number, projective plane

Příznaky

Mezinárodní význam

---

Anotace

V originále

We show that for each nonnegative integer $g$ there is a constant $\constc > 0$ such that every graph that embeds in the projective plane with face--width at least $r$ has crossing number at least $\constc r^2$ in the orientable surface of genus $g$. As a corollary, we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree.

Česky

Dokážeme, že grafy nakreslené v projektivní rovině mají rovinné průsečíkové číslo rostoucí kvadraticky ve své stěnové šířce.

---

Návaznosti

GA201/05/0050, projekt VaV	Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky