The crossing number of a projective graph is quadratic in the face-width
type: Item
instance of: scholarly article
title: The crossing number of a projective graph is quadratic in the face-width
zbMATH Open document ID: 1159.05016
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129757
full work available at URL: v15i1r46.html
review text: Summary: We show that for each integer \(g\geq 0\) there is a constant \(c_g > 0\) such that every graph that embeds in the projective plane with sufficiently large face--width \(r\) has crossing number at least \(c_g r^2\) in the orientable surface \(\Sigma_g\) 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.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5540951
zbMATH Keywords: graph embedding
zbMATH Keywords: projective plane
zbMATH Keywords: face-width
zbMATH Keywords: crossing number
zbMATH Keywords: orientable surface
zbMATH Keywords: genus
zbMATH Keywords: projective graphs
zbMATH Keywords: approximantion algorithm
author: Isidoro Gitler
author: Petr Hliněný
author: J. Leaños
author: Gelasio Salazar
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540951