A successful concept for measuring non-planarity of graphs: The crossing number.

DOI10.1016/S0012-365X(03)00317-0zbMath1035.05034OpenAlexW2116517722MaRDI QIDQ1422437

László A. Székely

Publication date: 14 February 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(03)00317-0

zbMATH Keywords

Graph drawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Two recursive inequalities for crossing numbers of graphs, The \(\mathbb{Z}_2\)-genus of Kuratowski minors, On quasi-planar graphs: clique-width and logical description, The crossing number of \(K_{5,n+1} \setminus e\), Removing even crossings, Crossings between non-homotopic edges, A crossing lemma for multigraphs, Simple realizability of complete abstract topological graphs simplified, Removing Even Crossings on Surfaces, Note on \(k\)-planar crossing numbers, Treewidth, Circle Graphs, and Circular Drawings, Rotation and crossing numbers for join products, ON THE ADDITIVITY OF CROSSING NUMBERS OF GRAPHS, Characterisations and examples of graph classes with bounded expansion, Odd crossing number and crossing number are not the same, Crossing numbers of graphs with rotation systems, Crossing number and weighted crossing number of near-planar graphs, Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method, Crossing and Weighted Crossing Number of Near-Planar Graphs, The crossing number of \(K_{1,m,n}\), The conjecture on the crossing number of \(K_{1, m, n}\) is true if Zarankiewicz's conjecture holds, Adjacent Crossings Do Matter, The Crossing Number of Graphs: Theory and Computation, Removing even crossings on surfaces, Crossing lemma for the odd-crossing number, Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill, On the crossing numbers of loop networks and generalized Petersen graphs, Crossings Between Non-homotopic Edges, A crossing lemma for multigraphs

Cites Work

• 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
• 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\)
• The crossing number of a graph on a compact 2-manifold
• Improved bounds for planar \(k\)-sets and related problems
• Convexity and sumsets
• New bounds on crossing numbers
• Drawings of graphs on surfaces with few crossings
• A combinatorial problem on polynomials and rational functions
• An upper bound for the rectilinear crossing number of the complete graph
• The Set of Differences of a Given Set
• Improved approximations of crossings in graph drawings
• Crossing Number is NP-Complete
• The crossing numbers of some generalized Petersen graphs.
• Crossing-Free Subgraphs
• Determining the thickness of graphs is NP-hard
• New results on rectilinear crossing numbers and plane embeddings
• On the crossing numbers of products of cycles and graphs of order four
• Bounds for rectilinear crossing numbers
• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• The crossing numbers of products of paths and stars with 4‐vertex graphs
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On the number of sums and products
• On the Number of Incidences Between Points and Curves
• [https://portal.mardi4nfdi.de/wiki/Publication:4888117 The crossing number ofC5 �Cn]
• Toward a theory of crossing numbers
• The crossing number of K5,n
• Crossing Number Problems
• On a problem of P. Turan concerning graphs
• The crossing numbers of Cartesian products of paths with 5-vertex graphs