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

DOI10.1016/S0012-365X(03)00317-0zbMATH Open1035.05034OpenAlexW2116517722MaRDI QIDQ1422437FDOQ1422437

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)

Cites Work

• Convexity and sumsets
• Bounds for rectilinear crossing numbers
• On the number of sums and products
• Graphs drawn with few crossings per edge
• Title not available (Why is that?)
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On the Number of Incidences Between Points and Curves
• Improved bounds for planar \(k\)-sets and related problems
• Crossing Number is NP-Complete
• Crossing-Free Subgraphs
• Title not available (Why is that?)
• A combinatorial problem on polynomials and rational functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• The crossing number ofC5 �Cn
• Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• The crossing number of K5,n
• Title not available (Why is that?)
• On a problem of P. Turan concerning graphs
• The crossing number of \(C_3\times C_n\)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Crossing Number Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The crossing numbers of Cartesian products of paths with 5-vertex graphs
• Toward a theory of crossing numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• New bounds on crossing numbers
• Improved approximations of crossings in graph drawings
• Determining the thickness of graphs is NP-hard
• The crossing number of a graph on a compact 2-manifold
• Title not available (Why is that?)
• Title not available (Why is that?)
• The crossing numbers of some generalized Petersen graphs.
• An upper bound for the rectilinear crossing number of the complete graph
• Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)
• Title not available (Why is that?)
• On the crossing numbers of certain generalized Petersen graphs
• Title not available (Why is that?)
• New results on rectilinear crossing numbers and plane embeddings
• Drawings of graphs on surfaces with few crossings
• The Set of Differences of a Given Set

Cited In (31)

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

   Recommendations

• A successful concept for measuring non-planarity of graphs: the crossing number 👍 👎
• Crossing Numbers of Beyond-Planar Graphs Revisited 👍 👎
• Crossing numbers of beyond-planar graphs 👍 👎
• Crossing numbers of beyond-planar graphs 👍 👎
• On the crossing number of almost planar graphs 👍 👎
• On the Crossing Number of Almost Planar Graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• On the size of planarly connected crossing graphs 👍 👎
• On the Size of Planarly Connected Crossing Graphs 👍 👎
• Title not available (Why is that?) 👍 👎

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

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