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

zbMath1159.05016MaRDI QIDQ1010759

Isidoro Gitler, Jesús Leaños, Gelasio Salazar, Petr Hliněný

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

zbMATH Keywords

projective planecrossing numbergenusface-widthgraph embeddingorientable surfaceprojective graphsapproximantion algorithm

Mathematics Subject Classification ID

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

Related Items (5)

Inserting Multiple Edges into a Planar Graph ⋮ Vertex insertion approximates the crossing number of apex graphs ⋮ Crossing number for graphs with bounded pathwidth ⋮ A tighter insertion-based approximation of the crossing number ⋮ Unnamed Item

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