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 (29)

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

This page was built for publication: A successful concept for measuring non-planarity of graphs: The crossing number.