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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00024698" target="_blank" >RIV/00216224:14330/08:00024698 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
The crossing number of a projective graph is quadratic in the face--width
Original language description
We show that for each integer g there is a constant Cg such that every graph that embeds in the projective plane with sufficiently large face-width r has crossing number at least Cgr^2 in the orientable surface Sg 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.
Czech name
Prusecikove cislo projektivniho grafu je kvadraticke ve stenove sirce
Czech description
Ukazeme, ze prusecikove cislo projektivniho grafu na kteremkoliv orientovatelnem povrchu roste kvadraticky se stenovou sirkou jeho projektivniho nakresleni. Dusledkem je take aproximacni algoritmus.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GA201%2F08%2F0308" target="_blank" >GA201/08/0308: Utilization of structural and "Width" parameters in combinatorics and algorithmic complexity</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)