Crossing Number Problems

DOI10.2307/2319261MaRDI QIDQ5680151zbMATH OpenOpenAlexFDO

Authors Richard K. Guy, P. Erdős

Publication date 1973

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2319261

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Crossing numbers
• scientific article; zbMATH DE number 1507304
• scientific article; zbMATH DE number 1452728
• SOFSEM 2005: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 1047749
• Some provably hard crossing number problems
• Applications of the crossing number

Cited in

(66)

• Some provably hard crossing number problems
• A survey of graphs with known or bounded crossing numbers
• A central approach to bound the number of crossings in a generalized configuration
• The maximum number of halving lines and the rectilinear crossing number of for
• The crossing number of Cartesian product of 5-wheel with any tree
• Improved bounds for the crossing numbers on surfaces of genus g
• Abstract order type extension and new results on the rectilinear crossing number
• The crossing numbers of products of paths and stars with 4‐vertex graphs
• \(K_7\)-minors in optimal 1-planar graphs
• Book embeddings and crossing numbers
• scientific article; zbMATH DE number 90572 (Why is no real title available?)
• A successful concept for measuring non-planarity of graphs: The crossing number.
• On \(k\)-gons and \(k\)-holes in point sets
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• Drawings of graphs on surfaces with few crossings
• The crossing number of the Cartesian product of paths with complete graphs
• New lower bounds on crossing numbers of \(K_{m,n}\) from semidefinite programming
• Approximating the maximum rectilinear crossing number
• General lower bounds for the minor crossing number of graphs
• The 3-symmetric pseudolinear crossing number of \(K_{36}\)
• On the crossing number of complete graphs
• Empty monochromatic triangles
• Bisection width of transposition graphs
• On Eggleton and Guy's conjectured upper bound for the crossing number of the n-cube
• 2-Layer k-Planar Graphs
• Plane Spanning Trees in Edge-Colored Simple Drawings of $$K_{n}$$
• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• On structural properties and adjacency spectrum of coprime graph of integers
• The crossing number of \(C_3\times C_n\)
• A lower bound for the optimal crossing-free Hamiltonian cycle problem
• A lower bound for the crossing number ofCm � Cn
• The crossing numbers of join of some graphs with n isolated vertices
• Crossing-optimal extension of simple drawings
• The crossing number of nearly complete bipartite graphs
• On 5-gons and 5-holes
• Upper bound for the crossing number of \(Q_n \times K_3\)
• Drawing disconnected graphs on the Klein bottle
• scientific article; zbMATH DE number 7225866 (Why is no real title available?)
• The crossing number of locally twisted cubes \(L T Q_n\)
• The crossing number of \(K_{1,4,n}\)
• Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes
• On weighted sums of numbers of convex polygons in point sets
• Monotone Crossing Number
• Infinite families of crossing-critical graphs with a given crossing number
• On crossing numbers of hypercubes and cube connected cycles
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• Optimal crossing-free Hamiltonian circuit drawings of K_n
• Optimal crossing-free Hamiltonian circuit drawings of \(K_n\)
• Crossing-critical edges and Kuratowski subgraphs of a graph
• Construction of crossing-critical graphs
• On the central levels problem
• Automated mathematical discovery and verification: minimizing pentagons in the plane
• The crossing number of \(K_{5,n+1} \setminus e\)
• Zip product of graphs and crossing numbers
• Coloring drawings of bipartite graphs: A problem in automated assembly
• On the central levels problem
• An upper bound for the crossing number of augmented cubes
• Rectilinear crossing number of graphs excluding a single-crossing graph as a minor
• Note on min-k-planar drawings of graphs
• Many touchings force many crossings
• Shooting stars in simple drawings of \(K_{m,n}\)
• A new lower bound for the bipartite crossing number with applications
• Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation
• The crossing number of join of the generalized Petersen graph \(P(3, 1)\) with path and cycle
• On the crossing numbers of loop networks and generalized Petersen graphs
• Graph minors and the crossing number of graphs

This page was built for publication: Crossing Number Problems

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