A survey of graphs with known or bounded crossing numbers

zbMATH Open1453.05024arXiv1901.05155MaRDI QIDQ5139701FDOQ5139701

Authors: Kieran Clancy, Michael Haythorpe, Alex Newcombe 

Publication date: 10 December 2020

Abstract: We present, to the best of the authors' knowledge, all known results for the (planar) crossing numbers of specific graphs and graph families. The results are separated into various categories; specifically, results for general graph families, results for graphs arising from various graph products, and results for recursive graph constructions.

Full work available at URL: https://arxiv.org/abs/1901.05155

Recommendations

• The Crossing Number of Graphs: Theory and Computation
• scientific article; zbMATH DE number 1054768
• Crossing numbers
• Survey of the crossing number of graphs
• The graph crossing number and its variants: a survey

zbMATH Keywords

graph productsplanar crossing numbers

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Title not available (Why is that?)
• The crossing number of \(K_{1,m,n}\)
• On the crossing number of the complete tripartite graph \(K_{1,8,n}\)
• Title not available (Why is that?)
• <italic>K</italic><sub>1,1,<italic>m</italic></sub>□<italic>P</italic><sub><italic>n</italic></sub> 的交叉数
• Über die Kreuzungszahl vollständiger, n‐geteilter Graphen
• On the crossing number of \(K_{ m } \square P_{n}\)
• The crossing number of \(C(8,2)\square P_{n}\)
• The crossing number of \(K_{3,3}\times P_n\)
• The crossing numbers of generalized Petersen graphs with small order
• Coloring graphs with crossings
• On the crossing numbers of certain generalized Petersen graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The crossing number of the strong product of two paths
• An improvement of the crossing number bound
• A lower bound for the crossing number ofCm � Cn
• On Eggleton and Guy's conjectured upper bound for the crossing number of the \(n\)-cube
• The early history of the brick factory problem
• The crossing numbers of join of some graphs with \(n\) isolated vertices
• An upper bound for the crossing number of augmented cubes
• THE MINIMUM NUMBER OF INTERSECTIONS IN COMPLETE GRAPHS
• The crossing number of join of the generalized Petersen graph \(P(3, 1)\) with path and cycle
• The crossing number of the hexagonal graph \(H_{3,n}\)
• The crossing numbers of products of path with graphs of order six
• Determining crossing number of join of the discrete graph with two symmetric graphs of order five
• DETERMINING CROSSING NUMBERS OF GRAPHS OF ORDER SIX USING CYCLIC PERMUTATIONS
• Closing in on Hill's conjecture
• An effective crossing minimisation heuristic based on star insertion
• Title not available (Why is that?)
• On the crossing numbers of Cartesian products of paths with special graphs
• The crossing number of Cartesian product of 5-wheel with any tree
• The crossing number of Cartesian products of complete bipartite graphs \(K_{2,m}\) with paths \(P_{n}\)
• Improved bounds on the crossing number of butterfly network
• The crossing numbers of a 6-vertex graph \(G\) and products \(S_n\)
• On the crossing numbers of \(G\square C_n\) for graphs \(G\) on six vertices
• The crossing number of \(G \mathbin{\square} C_n\) for the graph \(G\) on six vertices
• The crossing number of the join product of \({C_6}+3{K_2}\) with \({P_n}\) and \({C_n}\)
• On the crossing number of the Cartesian product of a 6-vertex graph with \(S_n\)
• On the crossing numbers of Cartesian products of stars and graphs of order six
• Crossing number of \(K_{2,3}\vee P_n\)
• The crossing number of Cartesian product of circulant graph \(C(9,2)\) with path \(P_n\)
• The crossing numbers of Cartesian product of cone graph \(C_{m}+K_l\) with path \(P_{n}\).
• The crossing number of Cartesian product of \(P_n\) with circulant graph \(C(10,2)\)
• The crossing numbers of Cartesian products of path with some graphs.
• The crossing number of Petersen graph \(P(4,1)\) with paths \(P_n\)
• The crossing numbers of Cartesian products of stars with 5-vertex graphs II
• On the crossing numbers of \(K_5\times S_n\)
• On the crossing number of products of a graph of order 6 and the star
• Title not available (Why is that?)
• The crossing number of the circulant graph \(C(3k-1;\{1,k\})\)
• The crossing number of flower snarks and related graphs
• Title not available (Why is that?)
• The crossing number of \(K_{2, 2, 2, n}\)
• The crossing number of Cartesian products of the special graph on six vertices with stars
• Title not available (Why is that?)
• Crossing numbers of Cartesian products of stars with 5-vertex graphs
• The crossing number of \(C(n;\{1,\lfloor n/2\rfloor-1\})\)
• The crossing number of \(W_4\times S_n\)
• On the crossing numbers of the joins of the special graph on six vertices with \(nK_1, P_n\) or \(C_n\)
• On the crossing number of the join product of a path and a graph of order six
• The crossing number of the complete quadruple graph
• On the crossing number of the join of some 5-vertex graphs and \(P_n\)
• The crossing number of the Cartesian product of a star with a 6-vertex graph
• Title not available (Why is that?)
• The strong product of graphs and crossing numbers.
• The crossing number of the join product of \({K_{1,1,1,2}} + {P_n}\)
• Crossing number of class of generalized fat trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Crossing number of the complete tripartite graph \(K_{1,10,n}\)
• On the crossing number of the Cartesian product of a sunlet graph and a star graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on isomorphic generalized Petersen graphs with an application to the crossing number of \(GP[3k-1,k]\) and \(GP[3k+1,k]\)
• Crossing number of the star graph \(S_4\)
• The crossing number of pancake graph \(P_4\) is six.
• An upper bound for the crossing number of locally twisted cubes.
• The crossing number of the joint graph of a small graph and a path or a cycle
• Title not available (Why is that?)
• Title not available (Why is that?)
• Crossing numbers of Sierpiński‐like graphs
• A group-theoretic model for symmetric interconnection networks
• On the Möbius Ladders
• Title not available (Why is that?)
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Graphs drawn with few crossings per edge
• The locally twisted cubes
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Improving the crossing lemma by finding more crossings in sparse graphs
• The graph crossing number and its variants: a survey
• Crossing Number is NP-Complete
• Crossing-Free Subgraphs
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Title not available (Why is that?)
• Self-dual configurations and regular graphs
• Proofs from THE BOOK
• The crossing number of \(P(N,3)\)
• The crossing number of \(C(n; \{1,3\})\)
• The crossing number of \(C(mk;\{1,k\})\)
• The crossing number of \(C(3k+1;\{1,k\})\)
• On the crossing numbers of loop networks and generalized Petersen graphs
• On the crossing number of honeycomb related networks
• The crossing number of Knödel graph \(W_{3,n}\)
• Title not available (Why is that?)
• Crossing numbers of graphs
• Title not available (Why is that?)
• Augmented cubes
• The crossing number of \(P^2_5\times C_n\)
• Title not available (Why is that?)
• The crossing number ofC5 �Cn
• Crossings, colorings, and cliques
• On topological graphs with at most four crossings per edge
• The crossing number of \(K_{1,4,n}\)
• New lower bound techniques for VLSI
• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• Title not available (Why is that?)
• The crossing number of K5,n
• Title not available (Why is that?)
• Towards the Albertson conjecture
• On the crossing number of \(K_{m,n}\)
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• On a problem of P. Turan concerning graphs
• The crossing number of \(C_3\times C_n\)
• Intersection of curves and crossing number of \(C_m\times C_n\) on surfaces
• Arrangements, circular arrangements and the crossing number of \(C_{7} \times C_{n}\).
• An improved bound for the crossing number of \(C_m\times C_n\): a self-contained proof using mostly combinatorial arguments
• On the crossing numbers of the \(k\)-th power of \(P_n\)
• Title not available (Why is that?)
• The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)
• On the crossing numbers of Cartesian products of stars and graphs on five vertices
• Title not available (Why is that?)
• On the crossing numbers of products of cycles and graphs of order four
• The crossing numbers of products of paths and stars with 4‐vertex graphs
• The crossing number of c₄ × c₄
• The crossing number of \(P^2_n \square C_3\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The crossing numbers of certain Cartesian products
• Some crossing numbers of products of cycles
• On the crossing numbers of products of stars and graphs of order five
• On the crossing numbers of Cartesian products with paths
• The crossing numbers of products of 5-vertex graphs with cycles
• The crossing numbers of join of the special graph on six vertices with path and cycle
• Crossing Number Problems
• Survey of the crossing number of graphs
• Zarankiewicz's conjecture is finite for each fixed \(m\)
• Title not available (Why is that?)
• The crossing numbers of join products of paths with graphs of order four
• The Join of Graphs and Crossing Numbers
• On the crossing number of some complete multipartite graphs
• The crossing number ofK1,3,n andK2,3,n
• Title not available (Why is that?)
• On the crossing number of \(K_{13}\)
• The crossing number of K₁₁ is 100
• The crossing number of the Cartesian product of paths with complete graphs
• An ILP-based Proof System for the Crossing Number Problem
• On the crossing numbers of Cartesian products of wheels and trees
• On the crossing numbers of Cartesian products with trees
• Title not available (Why is that?)
• The crossing numbers of Cartesian products of paths with 5-vertex graphs
• On the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\)
• Permutation Groups, Complexes, and Rearrangeable Connecting Networks
• The crossing number of the circular graph \(C(2m+2,m)\)
• On crossing numbers of hypercubes and cube connected cycles
• Crossing numbers of nearly complete graphs and nearly complete bipartite graphs.
• An improved upper bound on the crossing number of the hypercube
• The crossing number of folded hypercubes
• Bounds for the crossing number of the N‐cube
• On the Number of Crossings in a Complete Graph
• The crossing number of the complement of a circuit
• Infinite families of crossing-critical graphs with given average degree
• On crossing numbers of complete tripartite and balanced complete multipartite graphs
• The crossing numbers of some generalized Petersen graphs.
• The crossing number of \(K_{2,3}{\times}C_{3}\)
• Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)
• The crossing number of \(C_6\times C_n\)
• The crossing numbers of products of a 5-vertex graph with paths and cycles
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (14)

• The crossing numbers of join products of paths with three graphs of order five
• On the average crosscap number. II: Bounds for a graph
• The crossing numbers of join products of four graphs of order five with paths and cycles
• On the crossing numbers of Cartesian products of small graphs with paths, cycles and stars
• The crossing numbers of join product of four graphs on six vertices with discrete graphs
• On the crossing numbers of join products of four graphs of order six with the discrete graph
• On the crossing numbers of join products of \(W_4+P_n\) and \(W_4+C_n\)
• The influence of separating cycles in drawings of \(K_5 \setminus e\) in the join product with paths and cycles
• The tripartite-circle crossing number of graphs with two small partition classes
• Survey of the crossing number of graphs
• Domination and independence number of large 2-crossing-critical graphs
• Two recursive inequalities for crossing numbers of graphs
• Title not available (Why is that?)
• Disconnected spanning subgraphs of paths in the join products with cycles

Uses Software

• OGDF

This page was built for publication: A survey of graphs with known or bounded crossing numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5139701)