A successful concept for measuring non-planarity of graphs: The crossing number. (Q1422437): Difference between revisions

This survey paper reviews foundational, historical, and philosophical issues concerning crossing numbers, while arguing for the significance of this graph-theoretical parameter. It also establishes a new lower bound for crossing numbers, potentially useful in their estimation.

0 references

Mathematics Subject Classification ID

05C10

0 references

zbMATH DE Number

2041917

0 references

zbMATH Keywords

Graph drawing

0 references

reviewed by

Arthur T. White

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q3840854

0 references

Crossing-Free Subgraphs

0 references

On the crossing numbers of products of cycles and graphs of order four

0 references

New results on rectilinear crossing numbers and plane embeddings

0 references

Bounds for rectilinear crossing numbers

0 references

Q5543311

0 references

Q5523467

0 references

Improved bounds for planar \(k\)-sets and related problems

0 references

Q3699704

0 references

On the number of sums and products

0 references

Convexity and sumsets

0 references

A combinatorial problem on polynomials and rational functions

0 references

Crossing Number Problems

0 references

Improved approximations of crossings in graph drawings

0 references

The crossing numbers of some generalized Petersen graphs.

0 references

Q5786239

0 references

Q3726144

0 references

Crossing Number is NP-Complete

0 references

The Set of Differences of a Given Set

0 references

0 references

0 references

0 references

0 references

An upper bound for the rectilinear crossing number of the complete graph

0 references

The crossing number of K5,n

0 references

The crossing numbers of products of paths and stars with 4‐vertex graphs

0 references

The crossing numbers of Cartesian products of paths with 5-vertex graphs

0 references

Q4888117

0 references

Q4099559

0 references

Q4701026

0 references

Determining the thickness of graphs is NP-hard

0 references

On the crossing numbers of certain generalized Petersen graphs

0 references

Q4504030

0 references

On the Number of Incidences Between Points and Curves

0 references

New bounds on crossing numbers

0 references

Graphs drawn with few crossings per edge

0 references

Q4484691

0 references

Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)

0 references

Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs

0 references

The crossing number of \(C_3\times C_n\)

0 references

Q4273877

0 references

The crossing number of a graph on a compact 2-manifold

0 references

Drawings of graphs on surfaces with few crossings

0 references

Q4352316

0 references

Crossing Numbers and Hard Erdős Problems in Discrete Geometry

0 references

Toward a theory of crossing numbers

0 references

Q3880860

0 references

Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture

0 references

On a problem of P. Turan concerning graphs

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1422437

@@ Property / reviewed by @@
-Arthur T. White
@@ Property / reviewed by: Arthur T. White / rank @@
-Normal rank
@@ Property / reviewed by @@
+Arthur T. White
@@ Property / reviewed by: Arthur T. White / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3840854
@@ Property / cites work: Q3840854 / rank @@
+Normal rank
@@ Property / cites work @@
+Crossing-Free Subgraphs
@@ Property / cites work: Crossing-Free Subgraphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the crossing numbers of products of cycles and graphs of order four
+Normal rank
@@ Property / cites work @@
+New results on rectilinear crossing numbers and plane embeddings
+Normal rank
@@ Property / cites work @@
+Bounds for rectilinear crossing numbers
@@ Property / cites work: Bounds for rectilinear crossing numbers / rank @@
+Normal rank
@@ Property / cites work @@
+Q5543311
@@ Property / cites work: Q5543311 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5523467
@@ Property / cites work: Q5523467 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved bounds for planar \(k\)-sets and related problems
+Normal rank
@@ Property / cites work @@
+Q3699704
@@ Property / cites work: Q3699704 / rank @@
+Normal rank
@@ Property / cites work @@
+On the number of sums and products
@@ Property / cites work: On the number of sums and products / rank @@
+Normal rank
@@ Property / cites work @@
+Convexity and sumsets
@@ Property / cites work: Convexity and sumsets / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial problem on polynomials and rational functions
+Normal rank
@@ Property / cites work @@
+Crossing Number Problems
@@ Property / cites work: Crossing Number Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximations of crossings in graph drawings
+Normal rank
@@ Property / cites work @@
+The crossing numbers of some generalized Petersen graphs.
+Normal rank
@@ Property / cites work @@
+Q5786239
@@ Property / cites work: Q5786239 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3726144
@@ Property / cites work: Q3726144 / rank @@
+Normal rank
@@ Property / cites work @@
+Crossing Number is NP-Complete
@@ Property / cites work: Crossing Number is NP-Complete / rank @@
+Normal rank
@@ Property / cites work @@
+The Set of Differences of a Given Set
@@ Property / cites work: The Set of Differences of a Given Set / rank @@
+Normal rank
@@ Property / cites work @@
+Q5587734
@@ Property / cites work: Q5587734 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5661522
@@ Property / cites work: Q5661522 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4770978
@@ Property / cites work: Q4770978 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4748171
@@ Property / cites work: Q4748171 / rank @@
+Normal rank
@@ Property / cites work @@
+An upper bound for the rectilinear crossing number of the complete graph
+Normal rank
@@ Property / cites work @@
+The crossing number of K5,n
@@ Property / cites work: The crossing number of K5,n / rank @@
+Normal rank
@@ Property / cites work @@
+The crossing numbers of products of paths and stars with 4‐vertex graphs
+Normal rank
@@ Property / cites work @@
+The crossing numbers of Cartesian products of paths with 5-vertex graphs
+Normal rank
@@ Property / cites work @@
+Q4888117
@@ Property / cites work: Q4888117 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4099559
@@ Property / cites work: Q4099559 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4701026
@@ Property / cites work: Q4701026 / rank @@
+Normal rank
@@ Property / cites work @@
+Determining the thickness of graphs is NP-hard
@@ Property / cites work: Determining the thickness of graphs is NP-hard / rank @@
+Normal rank
@@ Property / cites work @@
+On the crossing numbers of certain generalized Petersen graphs
+Normal rank
@@ Property / cites work @@
+Q4504030
@@ Property / cites work: Q4504030 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Number of Incidences Between Points and Curves
+Normal rank
@@ Property / cites work @@
+New bounds on crossing numbers
@@ Property / cites work: New bounds on crossing numbers / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs drawn with few crossings per edge
@@ Property / cites work: Graphs drawn with few crossings per edge / rank @@
+Normal rank
@@ Property / cites work @@
+Q4484691
@@ Property / cites work: Q4484691 / rank @@
+Normal rank
@@ Property / cites work @@
+Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)
+Normal rank
@@ Property / cites work @@
+Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+The crossing number of \(C_3\times C_n\)
@@ Property / cites work: The crossing number of \(C_3\times C_n\) / rank @@
+Normal rank
@@ Property / cites work @@
+Q4273877
@@ Property / cites work: Q4273877 / rank @@
+Normal rank
@@ Property / cites work @@
+The crossing number of a graph on a compact 2-manifold
+Normal rank
@@ Property / cites work @@
+Drawings of graphs on surfaces with few crossings
@@ Property / cites work: Drawings of graphs on surfaces with few crossings / rank @@
+Normal rank
@@ Property / cites work @@
+Q4352316
@@ Property / cites work: Q4352316 / rank @@
+Normal rank
@@ Property / cites work @@
+Crossing Numbers and Hard Erdős Problems in Discrete Geometry
+Normal rank
@@ Property / cites work @@
+Toward a theory of crossing numbers
@@ Property / cites work: Toward a theory of crossing numbers / rank @@
+Normal rank
@@ Property / cites work @@
+Q3880860
@@ Property / cites work: Q3880860 / rank @@
+Normal rank
@@ Property / cites work @@
+Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
+Normal rank
@@ Property / cites work @@
+On a problem of P. Turan concerning graphs
@@ Property / cites work: On a problem of P. Turan concerning graphs / rank @@
+Normal rank