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

MaRDI QIDQ1010759zbMATH OpenFDO

Authors Isidoro Gitler, Petr Hliněný, J. Leaños, Gelasio Salazar

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/129757, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r46.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

approximantion algorithmcrossing numberface-widthgenusgraph embeddingorientable surfaceprojective graphsprojective plane

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• The crossing number of a projective graph is quadratic in the face–width
• Approximating the crossing number of graphs embeddable in any orientable surface
• Planar crossing numbers of graphs of bounded genus
• The crossing number of \(K_{4,n}\) on the real projective plane
• The projective plane crossing numbers of circular graphs

Cited in

(7)

• Crossing number for graphs with bounded pathwidth
• The crossing number of a projective graph is quadratic in the face–width
• scientific article; zbMATH DE number 7278018 (Why is no real title available?)
• Approximating the crossing number of graphs embeddable in any orientable surface
• Inserting Multiple Edges into a Planar Graph
• The projective plane crossing numbers of circular graphs
• Vertex insertion approximates the crossing number of apex graphs

This page was built for publication: The crossing number of a projective graph is quadratic in the face-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010759)