DROPS

Document

DOI: 10.4230/LIPIcs.GD.2025.20

A Systematic Approach to Crossing Numbers of Cartesian Products with Paths

Authors: Zayed Asiri, Ryan Burdett, Markus Chimani, Michael Haythorpe, Alex Newcombe, and Mirko H. Wagner

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

Determining the crossing numbers of Cartesian products of small graphs with arbitrarily large paths has been an ongoing topic of research since the 1970s. Doing so requires the establishment of coincident upper and lower bounds; the former is usually demonstrated by providing a suitable drawing procedure, while the latter often requires substantial theoretical arguments. Many such papers have been published, which typically focus on just one or two small graphs at a time, and use ad hoc arguments specific to those graphs. We propose a general approach which, when successful, establishes the required lower bound. This approach can be applied to the Cartesian product of any graph with arbitrarily large paths, and in each case involves solving a modified version of the crossing number problem on a finite number (typically only two or three) of small graphs. We demonstrate the potency of this approach by applying it to Cartesian products involving all 133 graphs of orders five or six, and show that it is successful in 128 cases. This includes 60 cases which a recent survey listed as either undetermined, or determined only in journals without adequate peer review.

Cite as

Zayed Asiri, Ryan Burdett, Markus Chimani, Michael Haythorpe, Alex Newcombe, and Mirko H. Wagner. A Systematic Approach to Crossing Numbers of Cartesian Products with Paths. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 20:1-20:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{asiri_et_al:LIPIcs.GD.2025.20,
  author =	{Asiri, Zayed and Burdett, Ryan and Chimani, Markus and Haythorpe, Michael and Newcombe, Alex and Wagner, Mirko H.},
  title =	{{A Systematic Approach to Crossing Numbers of Cartesian Products with Paths}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{20:1--20:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.20},
  URN =		{urn:nbn:de:0030-drops-250066},
  doi =		{10.4230/LIPIcs.GD.2025.20},
  annote =	{Keywords: Crossing number, Cartesian graph products, proof framework}
}

Search Results

Documents authored by Newcombe, Alex

A Systematic Approach to Crossing Numbers of Cartesian Products with Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message