Back to Search Start Over

Improvement on the crossing number of crossing-critical graphs

Authors :
Barát, János
Tóth, Géza
Publication Year :
2020

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+6\sqrt{k}+44$.<br />Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2003.01477
Document Type :
Working Paper