Improvement on the crossing number of crossing-critical graphs

DOI10.1007/S00454-020-00264-2MaRDI QIDQ6336027arXivFDO

Authors János Barát, Géza Tóth

Publication date 3 March 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00454-020-00264-2

Mathematics Subject Classification ID

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

arXiv classification

math.CO

Abstract: The crossing number of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. A graph $G$ is $k$-crossing-critical if its crossing number is at least $k$, but if we remove any edge of $G$, its crossing number drops below $k$. There are examples of $k$-crossing-critical graphs that do not have drawings with exactly $k$ crossings. Richter and Thomassen proved in 1993 that if $G$ is $k$-crossing-critical, then its crossing number is at most $2.5k+16$. We improve this bound to $2k+6sqrtk+44$.

This page was built for publication: Improvement on the crossing number of crossing-critical graphs

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