A survey of graphs with known or bounded crossing numbers

zbMath1453.05024arXiv1901.05155MaRDI QIDQ5139701

Kieran Clancy, Michael Haythorpe, Alex Newcombe

Publication date: 10 December 2020

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

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)

Related Items (6)

The crossing numbers of join products of paths with three graphs of order five ⋮ The crossing numbers of join products of four graphs of order five with paths and cycles ⋮ Domination and independence number of large 2-crossing-critical graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the crossing numbers of join products of W_{4}+P_{n} and W_{4}+C_{n}

Uses Software

• OGDF

Cites Work

• The crossing number of \(P^2_n \square C_3\)
• On the crossing number of \(K_{13}\)
• On the crossing numbers of Cartesian products of wheels and trees
• On crossing numbers of hypercubes and cube connected cycles
• The crossing number of the complement of a circuit
• Improving the crossing lemma by finding more crossings in sparse graphs
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• On the crossing numbers of Cartesian products with paths
• The crossing numbers of products of 5-vertex graphs with cycles
• On the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\)
• The crossing numbers of join of the special graph on six vertices with path and cycle
• Towards the Albertson conjecture
• On the crossing number of \(K_{ m } \square P_{n}\)
• The crossing number of \(K_{1,m,n}\)
• The crossing number of \(C(8,2)\square P_{n}\)
• The crossing numbers of generalized Petersen graphs with small order
• Crossings, colorings, and cliques
• Coloring graphs with crossings
• On the crossing numbers of certain generalized Petersen graphs
• The crossing number of \(C_3\times C_n\)
• Graphs drawn with few crossings per edge
• Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)
• Intersection of curves and crossing number of \(C_m\times C_n\) on surfaces
• On the crossing number of \(K_{m,n}\)
• Infinite families of crossing-critical graphs with given average degree
• Arrangements, circular arrangements and the crossing number of \(C_{7} \times C_{n}\).
• The crossing number of \(P(N,3)\)
• The crossing number of \(K_{2,3}{\times}C_{3}\)
• The crossing numbers of join of some graphs with \(n\) isolated vertices
• 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 number of \(C(n; \{1,3\})\)
• The crossing number of \(C(mk;\{1,k\})\)
• An improved bound for the crossing number of \(C_m\times C_n\): a self-contained proof using mostly combinatorial arguments
• Zarankiewicz's conjecture is finite for each fixed \(m\)
• The graph crossing number and its variants: a survey
• Determining crossing number of join of the discrete graph with two symmetric graphs of order five
• On topological graphs with at most four crossings per edge
• The crossing number of Cartesian product of 5-wheel with any tree
• The early history of the brick factory problem
• The crossing number of the Cartesian product of paths with complete graphs
• The crossing number of \(C(3k+1;\{1,k\})\)
• The crossing number of \(K_{1,4,n}\)
• The crossing number of Cartesian products of complete bipartite graphs \(K_{2,m}\) with paths \(P_{n}\)
• On the crossing numbers of loop networks and generalized Petersen graphs
• The crossing number of the circular graph \(C(2m+2,m)\)
• The crossing number of folded hypercubes
• The crossing numbers of products of path with graphs of order six
• On the crossing numbers of Cartesian products of stars and graphs of order six
• An upper bound for the crossing number of augmented cubes
• On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs
• On the crossing numbers of G□ Cn for graphs G on six vertices
• The crossing numbers of join products of paths with graphs of order four
• The crossing number of G ▭ C n for the graph G on six vertices
• An effective crossing minimisation heuristic based on star insertion
• [https://portal.mardi4nfdi.de/wiki/Publication:3156923 The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)]
• Crossing Number is NP-Complete
• The Join of Graphs and Crossing Numbers
• On the crossing number of some complete multipartite graphs
• An improved upper bound on the crossing number of the hypercube
• On the Crossing Numbers of Cartesian Products of Stars and Graphs on Five Vertices
• The crossing number ofK1,3,n andK2,3,n
• A group-theoretic model for symmetric interconnection networks
• The crossing numbers of some generalized Petersen graphs.
• New lower bound techniques for VLSI
• Crossing-Free Subgraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• On the crossing numbers of products of cycles and graphs of order four
• The crossing numbers of products of a 5-vertex graph with paths and cycles
• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• The crossing numbers of products of paths and stars with 4‐vertex graphs
• The crossing number of c₄ × c₄
• [https://portal.mardi4nfdi.de/wiki/Publication:4521491 A lower bound for the crossing number ofCm � Cn]
• DETERMINING CROSSING NUMBERS OF GRAPHS OF ORDER SIX USING CYCLIC PERMUTATIONS
• Crossing Numbers of Graphs
• An ILP-based Proof System for the Crossing Number Problem
• The locally twisted cubes
• Augmented cubes
• The crossing numbers of certain Cartesian products
• [https://portal.mardi4nfdi.de/wiki/Publication:4888117 The crossing number ofC5 �Cn]
• ON THE CROSSING NUMBER OF THE CARTESIAN PRODUCT OF A SUNLET GRAPH AND A STAR GRAPH
• <italic>K</italic><sub>1,1,<italic>m</italic></sub>□<italic>P</italic><sub><italic>n</italic></sub> 的交叉数
• Closing in on Hill's Conjecture
• 一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数
• Some crossing numbers of products of cycles
• An improvement of the crossing number bound
• THE MINIMUM NUMBER OF INTERSECTIONS IN COMPLETE GRAPHS
• Permutation Groups, Complexes, and Rearrangeable Connecting Networks
• The crossing number of pancake graph $P_4$ is six
• The crossing number of K₁₁ is 100
• On the crossing numbers of Cartesian products with trees
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• On the Möbius Ladders
• A theorem on tait colorings with an application to the generalized Petersen graphs
• The crossing number of K5,n
• Über die Kreuzungszahl vollständiger, n‐geteilter Graphen
• Crossing Number Problems
• Crossing numbers of Sierpiński‐like graphs
• On the Number of Crossings in a Complete Graph
• Bounds for the crossing number of the N‐cube
• Self-dual configurations and regular graphs
• On a problem of P. Turan concerning graphs
• Proofs from THE BOOK
• The crossing numbers of Cartesian products of paths with 5-vertex graphs
• On the crossing numbers of products of stars and graphs of order five

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