Minimal number of crossings in strong product of paths

Marián KleščJana PetrillováMatúš Valo



The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of GG in the plane. The exact crossing number is known only for few specific families of graphs. Cartesian products of two graphs belong to the first families of graphs for which the crossing number has been studied. Some results concerning crossing numbers are also known for join products of two graphs. In the paper, we start to collect the crossing numbers for the strong product of graphs, namely for the strong product of two paths.

Additional Information


Klešč, Marián, Petrillová, Jana, Valo, Matúš