A linear upper bound on the rectilinear crossing number

2005/12/16 by David R. Wood, Wood, David R.
Computer Science · Mathematics · #05C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C10

paper · pdf · doi:10.48550/arxiv.math/0512392

This paper has been withdrawn by the author. The results have been superseeded by the author's paper with Jan Arne Telle: "Planar decompositions and the crossing number of graphs with an excluded minor", http://arxiv.org/math/0604467

openalex publication_date 2005/12/16 · arxiv created 2006/06/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

It is proved that the rectilinear crossing number of every graph with bounded tree-width and bounded degree is linear in the number of vertices. **** This paper has been withdrawn by the author. **** The results have been superseeded by the author's paper with Jan Arne Telle: "Planar decompositions and the crossing number of graphs with an excluded minor", http://arxiv.org/math/0604467.

Related

• Rectilinear Crossing Number of Graphs Excluding Single-Crossing Graphs as Minors
• Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
• A survey of graphs with known or bounded crossing numbers
• Crossing Number for Graphs With Bounded Pathwidth
• On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs