The crossing number is the minimum number of crossing points among plane graph drawings of a finite graph. Use drawings with vertices at distinct points, edge interiors avoiding vertices, finitely many crossings, and no three edge interiors meeting at one crossing. A crossing is a point where two edge interiors pass through one another.
Count crossing points, rather than just pairs of edges that cross: if the same pair crosses twice, it contributes twice. A graph is a planar graph exactly when its crossing number is zero. Deleting one selected edge at each crossing leaves a planar graph, so a drawing with crossings can be made planar by deleting at most edges. The crossing lemma gives a quantitative lower bound for dense simple graphs.
If a simple graph has vertices and edges, every plane drawing has at leastcrossings. Apply the linear planar bound to the random induced subgraph obtained by retaining vertices independently with probability .
Here a loopless multigraph has vertices, edges, and at most parallel edges per pair. In a minimum-crossing drawing, crossings between incident edges can be removed by exchanging their initial segments, so every crossing involves four distinct vertices. For each parallel class choose an edge with probability per edge, with the remaining probability choosing none. Retain vertices independently with probability . The sampled simple graph has expected edge count , expected vertex count , and expected crossing count . Deleting one edge per crossing and using the planar graph edge bound gives . Choose .
Articles by others on the same topic
There are currently no matching articles.