The crossing number of a projective graph is quadratic in the face--width (Extended abstract)

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00020424" target="_blank" >RIV/00216224:14330/07:00020424 - isvavai.cz</a>
Alternative codes found
RIV/61989100:27240/07:00014965
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 (Extended abstract)
Original language description
We show that for each integer $ggeq0$ there is a constant $c>0$ such that every graph that embeds in the projective plane with sufficiently large face--width $r$ has crossing number at least $c.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.
Czech name
Průsečíkové číslo projektivních grafů je kvadratické ve stěnové šířce
Czech description
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.

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

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)