We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Improvement on the Crossing Number of Crossing-Critical Graphs.
- Authors
Barát, János; Tóth, Géza
- 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.5 k + 16 . We improve this bound to 2 k + 8 k + 47 .
- Subjects
CHARTS, diagrams, etc.; EDGES (Geometry)
- Publication
Discrete & Computational Geometry, 2022, Vol 67, Issue 2, p595
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-020-00264-2