On the Crossing Numbers of Cartesian Products of Small Graphs with Paths, Cycles and Stars

2019/02/21 by K. B. Clancy, Clancy, Kieran, Michael Haythorpe +3
Computer Science · #05C10 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1902.07873

openalex publication_date 2019/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

There has been significant research dedicated towards computing the crossing numbers of families of graphs resulting from the Cartesian products of small graphs with arbitrarily large paths, cycles and stars. For graphs with four or fewer vertices, these have all been computed, but there are still various gaps for graphs with five or more vertices. We contribute to this field by determining the crossing numbers for fifteen such families.

Related

• A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
• On the Crossing Number of the Cartesian Product of a Sunlet Graph and a Star Graph
• A survey of graphs with known or bounded crossing numbers
• On the Orchard crossing number of prisms, ladders and other related graphs
• Tight Upper Bounds on the Crossing Number in a Minor-Closed Class