Crossing number inequality
id:
crossing-number-inequality-258-15002501
title:
Crossing number inequality
text:
In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of edge crossings in a plane drawing of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e3/n2. It has applications in VLSI design and combinatorial geometry,
and was discovered indepen
brand slug:
wiki
category slug:
encyclopedia
description:
Drawings of dense graphs have many crossings
original url:
https://en.wikipedia.org/wiki/Crossing_number_inequality
date created:
date modified:
2024-04-04T21:44:58Z
main entity:
{"identifier":"Q24896206","url":"https://www.wikidata.org/entity/Q24896206"}
image:
fields total:
13
integrity:
14