Knowledge

Crossing number inequality

Source 📝

355:
on the number of incidences that are possible between given numbers of points and lines in the plane, follows by constructing a graph whose vertices are the points and whose edges are the segments of lines between incident points. If there were more incidences than the Szemerédi–Trotter bound, this
323:
refers to the minimum number of pairs of edges that each determine one crossing, whereas the crossing number simply refers to the minimum number of crossings. (This distinction is necessary since some authors assume that in a proper drawing no two edges cross more than once.)
867:
crossings. We may assume that any two edges in this diagram with a common vertex are disjoint, otherwise we could interchange the intersecting parts of the two edges and reduce the crossing number by one. Thus every crossing in this diagram involves four distinct vertices of
1590: 1200: 1059: 219: 779: 961: 677: 1445: 321: 443: 1366: 1303: 1258: 1226: 1465: 1473: 1814: 1845: 360:, that if a finite point set does not have a linear number of collinear points, then it determines a quadratic number of distinct lines. Similarly, 1121: 356:
graph would necessarily have more crossings than the total number of pairs of lines, an impossibility. The inequality can also be used to prove
997: 157: 1943: 1897: 1775: 2006: 692: 348: 1669: 893: 1773:; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza (2006), "Improving the crossing lemma by finding more crossings in sparse graphs", 623: 1371: 138: 36: 278: 60: 357: 40: 398: 1308: 149: 2016: 81: 1263: 2011: 48: 1231: 1612: 1091: 527: 344: 89: 1645: 101: 44: 1981: 1870: 1752: 1704: 1678: 228:
is the best known to date, and is due to Ackerman. For earlier results with weaker constants see
1616: 97: 1211: 1952: 1906: 1854: 1823: 1784: 1736: 1688: 1623:, North-Holland Mathematics Studies, vol. 60, North-Holland, Amsterdam, pp. 9–12, 1205: 365: 1966: 1920: 1866: 1798: 1748: 1700: 1628: 1962: 1916: 1862: 1794: 1744: 1696: 1624: 1608: 85: 1843:
Székely, L. A. (1997), "Crossing numbers and hard Erdős problems in discrete geometry",
1450: 683: 343:
realized that this inequality yielded very simple proofs of some important theorems in
1980:
Adiprasito, Karim (2018-12-26), "Combinatorial Lefschetz theorems beyond positivity",
2000: 1934: 1770: 1727: 1722: 1667:
Ackerman, Eyal (2019), "On topological graphs with at most four crossings per edge",
93: 20: 1874: 1756: 1708: 1938: 543: 484: 480: 113: 1585:{\displaystyle {\frac {f_{d}^{d+2}(\Delta )}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta )}}.} 1692: 855:, since every crossing involves four vertices. To see this consider a diagram of 539: 352: 332:
The motivation of Leighton in studying crossing numbers was for applications to
32: 1858: 1789: 1888: 460:
crossings. Each of these crossings can be removed by removing an edge from
361: 1828: 1195:{\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.} 1957: 1911: 1812:
Pach, János; Tóth, Géza (2000), "Which crossing number is it anyway?",
1740: 1986: 1054:{\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.} 214:{\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.} 1683: 1725:; Tóth, Géza (1997), "Graphs drawn with few crossings per edge", 333: 77: 526:
To obtain the actual crossing number inequality, we now use a
112:
The crossing number inequality states that, for an undirected
1228:
is a simplicial complex that is mapped piecewise-linearly to
774:{\displaystyle \mathbf {E} \geq \mathbf {E} -3\mathbf {E} .} 1652:, Foundations of Computing Series, Cambridge, MA: MIT Press 1064:
A slight refinement of this argument allows one to replace
956:{\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.} 255:
It is important to distinguish between the crossing number
51:
of the graph. It states that, for graphs where the number
672:{\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.} 617:. By the preliminary crossing number inequality, we have 1440:{\displaystyle f_{d}(\Delta )>(d+3)f_{d-1}(\Delta )} 597:
denote the number of edges, vertices and crossings of
573:
if and only if its two vertices were chosen to lie in
316:{\displaystyle {\text{pair-cr}}(G)\leq {\text{cr}}(G)} 233: 1941:; Tóth, G. (2000), "New bounds on crossing numbers", 1476: 1453: 1374: 1311: 1266: 1234: 1214: 1124: 1000: 896: 695: 626: 401: 281: 160: 380:
We first give a preliminary estimate: for any graph
1584: 1459: 1439: 1360: 1297: 1252: 1220: 1194: 1115:demonstrated an improvement of this inequality to 1053: 955: 773: 671: 437: 315: 213: 1208:showed a generalization to higher dimensions: If 438:{\displaystyle \operatorname {cr} (G)\geq e-3n.} 55:of edges is sufficiently larger than the number 1112: 542:parameter to be chosen later, and construct a 59:of vertices, the crossing number is at least 8: 841:. Finally, every crossing in the diagram of 16:Drawings of dense graphs have many crossings 1447:, then the number of pairwise intersecting 1640: 1638: 501:, and the claim follows. (In fact we have 479:vertices with no crossings, and is thus a 1985: 1956: 1910: 1827: 1815:Journal of Combinatorial Theory, Series B 1788: 1682: 1555: 1544: 1528: 1489: 1484: 1477: 1475: 1452: 1416: 1379: 1373: 1361:{\displaystyle f_{d-1}(\Delta )\ \ (d-1)} 1316: 1310: 1271: 1265: 1241: 1236: 1233: 1213: 1175: 1159: 1153: 1147: 1123: 1039: 1025: 1019: 999: 929: 901: 895: 759: 747: 732: 720: 708: 696: 694: 660: 644: 631: 625: 464:. Thus we can find a graph with at least 400: 299: 282: 280: 199: 185: 179: 159: 1846:Combinatorics, Probability and Computing 336:design in theoretical computer science. 272: 229: 1600: 340: 84:, and was discovered independently by 824:since both endpoints need to stay in 448:To prove this, consider a diagram of 7: 1891:(1998), "Improved bounds for planar 1662: 1660: 1621:Theory and practice of combinatorics 1944:Discrete and Computational Geometry 1898:Discrete and Computational Geometry 1776:Discrete and Computational Geometry 1619:(1982), "Crossing-free subgraphs", 1298:{\displaystyle f_{d}(\Delta )\ \ d} 1570: 1504: 1431: 1388: 1331: 1280: 1215: 810:. Similarly, each of the edges in 244:, but at the expense of replacing 14: 1253:{\displaystyle \mathbf {R} ^{2d}} 364:used it to prove upper bounds on 263:and the pairwise crossing number 43:, as a function of the number of 1237: 991:), we obtain after some algebra 748: 721: 697: 37:minimum number of edge crossings 1467:-dimensional faces is at least 1113:Pach, Spencer & Tóth (2000) 561:independently with probability 275:, the pairwise crossing number 1573: 1567: 1525: 1512: 1507: 1501: 1434: 1428: 1409: 1397: 1391: 1385: 1355: 1343: 1334: 1328: 1283: 1277: 1137: 1131: 1013: 1007: 919: 913: 765: 752: 738: 725: 714: 701: 414: 408: 310: 304: 293: 287: 173: 167: 39:in a plane drawing of a given 1: 1895:-sets and related problems", 1368:-dimensional faces such that 1693:10.1016/j.comgeo.2019.101574 553:by allowing each vertex of 248:with the worse constant of 2033: 565:, and allowing an edge of 25:crossing number inequality 1859:10.1017/S0963548397002976 1790:10.1007/s00454-006-1264-9 1650:Complexity Issues in VLSI 349:Szemerédi–Trotter theorem 2007:Topological graph theory 1305:-dimensional faces and 1221:{\displaystyle \Delta } 981:(since we assumed that 76:It has applications in 1829:10.1006/jctb.2000.1978 1670:Computational Geometry 1586: 1461: 1441: 1362: 1299: 1254: 1222: 1196: 1055: 957: 775: 673: 613:contains a diagram of 601:, respectively. Since 528:probabilistic argument 439: 317: 273:Pach & Tóth (2000) 230:Pach & Tóth (1997) 215: 82:combinatorial geometry 19:In the mathematics of 1958:10.1007/s004540010011 1587: 1462: 1442: 1363: 1300: 1255: 1223: 1197: 1056: 958: 776: 674: 440: 318: 216: 108:Statement and history 1474: 1451: 1372: 1309: 1264: 1232: 1212: 1122: 998: 894: 693: 624: 399: 347:. For instance, the 279: 158: 1566: 1500: 1912:10.1007/PL00009354 1741:10.1007/BF01215922 1615:; Newborn, M. M.; 1582: 1540: 1480: 1457: 1437: 1358: 1295: 1250: 1218: 1192: 1051: 953: 845:has a probability 814:has a probability 792:had a probability 784:Since each of the 771: 669: 487:we must then have 452:which has exactly 435: 345:incidence geometry 313: 240:can be lowered to 234:Pach et al. (2006) 211: 1577: 1460:{\displaystyle d} 1342: 1339: 1291: 1288: 1187: 1046: 609:, the diagram of 605:is a subgraph of 302: 285: 206: 2024: 1992: 1990: 1989: 1977: 1971: 1969: 1960: 1931: 1925: 1923: 1914: 1894: 1885: 1879: 1877: 1840: 1834: 1832: 1831: 1809: 1803: 1801: 1792: 1767: 1761: 1759: 1719: 1713: 1711: 1686: 1664: 1655: 1653: 1642: 1633: 1631: 1605: 1591: 1589: 1588: 1583: 1578: 1576: 1565: 1554: 1539: 1538: 1510: 1499: 1488: 1478: 1466: 1464: 1463: 1458: 1446: 1444: 1443: 1438: 1427: 1426: 1384: 1383: 1367: 1365: 1364: 1359: 1340: 1337: 1327: 1326: 1304: 1302: 1301: 1296: 1289: 1286: 1276: 1275: 1259: 1257: 1256: 1251: 1249: 1248: 1240: 1227: 1225: 1224: 1219: 1201: 1199: 1198: 1193: 1188: 1186: 1185: 1170: 1169: 1154: 1152: 1151: 1110: 1100: 1090:For graphs with 1081: 1071: 1067: 1060: 1058: 1057: 1052: 1047: 1045: 1044: 1043: 1030: 1029: 1020: 990: 980: 962: 960: 959: 954: 934: 933: 906: 905: 886: 871: 866: 858: 854: 851:of remaining in 850: 844: 840: 827: 823: 820:of remaining in 819: 813: 809: 799: 795: 791: 787: 780: 778: 777: 772: 764: 763: 751: 737: 736: 724: 713: 712: 700: 678: 676: 675: 670: 665: 664: 649: 648: 636: 635: 616: 612: 608: 604: 600: 596: 587: 576: 572: 568: 564: 560: 556: 552: 548: 537: 522: 515: 500: 478: 474: 463: 459: 451: 444: 442: 441: 436: 391: 387: 383: 322: 320: 319: 314: 303: 300: 286: 283: 270: 262: 251: 247: 243: 239: 227: 220: 218: 217: 212: 207: 205: 204: 203: 190: 189: 180: 147: 136: 127:edges such that 126: 122: 118: 72: 58: 54: 2032: 2031: 2027: 2026: 2025: 2023: 2022: 2021: 1997: 1996: 1995: 1979: 1978: 1974: 1933: 1932: 1928: 1892: 1887: 1886: 1882: 1842: 1841: 1837: 1811: 1810: 1806: 1769: 1768: 1764: 1721: 1720: 1716: 1666: 1665: 1658: 1644: 1643: 1636: 1607: 1606: 1602: 1598: 1524: 1511: 1479: 1472: 1471: 1449: 1448: 1412: 1375: 1370: 1369: 1312: 1307: 1306: 1267: 1262: 1261: 1235: 1230: 1229: 1210: 1209: 1171: 1155: 1143: 1120: 1119: 1102: 1095: 1088: 1073: 1069: 1065: 1035: 1031: 1021: 996: 995: 982: 967: 925: 897: 892: 891: 873: 869: 860: 856: 852: 846: 842: 829: 825: 821: 815: 811: 801: 797: 793: 789: 785: 755: 728: 704: 691: 690: 656: 640: 627: 622: 621: 614: 610: 606: 602: 598: 595: 589: 586: 582: 578: 574: 570: 566: 562: 558: 554: 550: 546: 544:random subgraph 531: 517: 502: 488: 485:Euler's formula 476: 465: 461: 453: 449: 397: 396: 392:edges, we have 389: 385: 381: 378: 330: 277: 276: 264: 256: 249: 245: 241: 237: 236:. The constant 225: 195: 191: 181: 156: 155: 141: 139:crossing number 128: 124: 120: 116: 110: 64: 56: 52: 17: 12: 11: 5: 2030: 2028: 2020: 2019: 2014: 2009: 1999: 1998: 1994: 1993: 1972: 1951:(4): 623–644, 1926: 1905:(3): 373–382, 1880: 1853:(3): 353–358, 1835: 1822:(2): 225–246, 1804: 1783:(4): 527–552, 1762: 1735:(3): 427–439, 1714: 1677:: 101574, 31, 1656: 1634: 1599: 1597: 1594: 1593: 1592: 1581: 1575: 1572: 1569: 1564: 1561: 1558: 1553: 1550: 1547: 1543: 1537: 1534: 1531: 1527: 1523: 1520: 1517: 1514: 1509: 1506: 1503: 1498: 1495: 1492: 1487: 1483: 1456: 1436: 1433: 1430: 1425: 1422: 1419: 1415: 1411: 1408: 1405: 1402: 1399: 1396: 1393: 1390: 1387: 1382: 1378: 1357: 1354: 1351: 1348: 1345: 1336: 1333: 1330: 1325: 1322: 1319: 1315: 1294: 1285: 1282: 1279: 1274: 1270: 1247: 1244: 1239: 1217: 1203: 1202: 1191: 1184: 1181: 1178: 1174: 1168: 1165: 1162: 1158: 1150: 1146: 1142: 1139: 1136: 1133: 1130: 1127: 1087: 1084: 1062: 1061: 1050: 1042: 1038: 1034: 1028: 1024: 1018: 1015: 1012: 1009: 1006: 1003: 966:Now if we set 964: 963: 952: 949: 946: 943: 940: 937: 932: 928: 924: 921: 918: 915: 912: 909: 904: 900: 782: 781: 770: 767: 762: 758: 754: 750: 746: 743: 740: 735: 731: 727: 723: 719: 716: 711: 707: 703: 699: 680: 679: 668: 663: 659: 655: 652: 647: 643: 639: 634: 630: 591: 584: 580: 446: 445: 434: 431: 428: 425: 422: 419: 416: 413: 410: 407: 404: 377: 374: 358:Beck's theorem 341:Székely (1997) 329: 326: 312: 309: 306: 298: 295: 292: 289: 271:. As noted by 222: 221: 210: 202: 198: 194: 188: 184: 178: 175: 172: 169: 166: 163: 109: 106: 29:crossing lemma 15: 13: 10: 9: 6: 4: 3: 2: 2029: 2018: 2017:Graph drawing 2015: 2013: 2010: 2008: 2005: 2004: 2002: 1988: 1983: 1976: 1973: 1968: 1964: 1959: 1954: 1950: 1946: 1945: 1940: 1936: 1930: 1927: 1922: 1918: 1913: 1908: 1904: 1900: 1899: 1890: 1884: 1881: 1876: 1872: 1868: 1864: 1860: 1856: 1852: 1848: 1847: 1839: 1836: 1830: 1825: 1821: 1817: 1816: 1808: 1805: 1800: 1796: 1791: 1786: 1782: 1778: 1777: 1772: 1766: 1763: 1758: 1754: 1750: 1746: 1742: 1738: 1734: 1730: 1729: 1728:Combinatorica 1724: 1718: 1715: 1710: 1706: 1702: 1698: 1694: 1690: 1685: 1680: 1676: 1672: 1671: 1663: 1661: 1657: 1651: 1647: 1641: 1639: 1635: 1630: 1626: 1622: 1618: 1617:Szemerédi, E. 1614: 1610: 1604: 1601: 1595: 1579: 1562: 1559: 1556: 1551: 1548: 1545: 1541: 1535: 1532: 1529: 1521: 1518: 1515: 1496: 1493: 1490: 1485: 1481: 1470: 1469: 1468: 1454: 1423: 1420: 1417: 1413: 1406: 1403: 1400: 1394: 1380: 1376: 1352: 1349: 1346: 1323: 1320: 1317: 1313: 1292: 1272: 1268: 1260:, and it has 1245: 1242: 1207: 1189: 1182: 1179: 1176: 1172: 1166: 1163: 1160: 1156: 1148: 1144: 1140: 1134: 1128: 1125: 1118: 1117: 1116: 1114: 1109: 1105: 1099: 1093: 1085: 1083: 1080: 1076: 1048: 1040: 1036: 1032: 1026: 1022: 1016: 1010: 1004: 1001: 994: 993: 992: 989: 985: 978: 974: 970: 950: 947: 944: 941: 938: 935: 930: 926: 922: 916: 910: 907: 902: 898: 890: 889: 888: 884: 880: 876: 872:. Therefore, 864: 849: 839: 836: 832: 818: 808: 804: 768: 760: 756: 744: 741: 733: 729: 717: 709: 705: 689: 688: 687: 685: 666: 661: 657: 653: 650: 645: 641: 637: 632: 628: 620: 619: 618: 594: 545: 541: 535: 529: 524: 520: 513: 509: 505: 499: 495: 491: 486: 482: 472: 468: 457: 432: 429: 426: 423: 420: 417: 411: 405: 402: 395: 394: 393: 388:vertices and 375: 373: 371: 369: 363: 359: 354: 350: 346: 342: 337: 335: 327: 325: 307: 296: 290: 274: 268: 260: 253: 235: 231: 224:The constant 208: 200: 196: 192: 186: 182: 176: 170: 164: 161: 154: 153: 152: 151: 145: 140: 135: 131: 123:vertices and 115: 107: 105: 103: 99: 95: 91: 87: 83: 79: 74: 71: 67: 62: 50: 46: 42: 38: 34: 30: 26: 22: 21:graph drawing 2012:Inequalities 1987:1812.10454v3 1975: 1948: 1942: 1929: 1902: 1896: 1883: 1850: 1844: 1838: 1819: 1813: 1807: 1780: 1774: 1765: 1732: 1726: 1717: 1674: 1668: 1649: 1646:Leighton, T. 1620: 1603: 1204: 1107: 1103: 1097: 1094:larger than 1089: 1078: 1074: 1063: 987: 983: 976: 972: 968: 965: 887:and we have 882: 878: 874: 862: 847: 837: 834: 830: 828:, therefore 816: 806: 802: 796:of being in 788:vertices in 783: 684:expectations 681: 592: 533: 525: 518: 511: 507: 503: 497: 493: 489: 481:planar graph 470: 466: 455: 447: 379: 367: 338: 331: 328:Applications 266: 258: 254: 223: 143: 133: 129: 114:simple graph 111: 75: 69: 65: 61:proportional 28: 24: 18: 1939:Spencer, J. 1771:Pach, János 1723:Pach, János 1613:Chvátal, V. 540:probability 483:. But from 353:upper bound 80:design and 33:lower bound 2001:Categories 1889:Dey, T. K. 1684:1509.01932 1596:References 1206:Adiprasito 1086:Variations 800:, we have 686:we obtain 569:to lie in 557:to lie in 475:edges and 366:geometric 150:inequality 148:obeys the 1609:Ajtai, M. 1571:Δ 1549:− 1505:Δ 1432:Δ 1421:− 1389:Δ 1350:− 1332:Δ 1321:− 1281:Δ 1216:Δ 1141:≥ 1129:⁡ 1017:≥ 1005:⁡ 939:− 923:≥ 911:⁡ 742:− 718:≥ 651:− 638:≥ 530:. We let 424:− 418:≥ 406:⁡ 362:Tamal Dey 297:≤ 177:≥ 165:⁡ 98:Szemerédi 1935:Pach, J. 1875:36602807 1757:20480170 1709:16847443 1648:(1983), 1077:> 7.5 265:pair-cr( 102:Leighton 49:vertices 31:gives a 1967:1799605 1921:1608878 1867:1464571 1799:2267545 1749:1606052 1701:4010251 1629:0806962 682:Taking 532:0 < 339:Later, 284:pair-cr 100:and by 94:Newborn 90:Chvátal 35:on the 1965:  1919:  1873:  1865:  1797:  1755:  1747:  1707:  1699:  1627:  1341:  1338:  1290:  1287:  986:> 4 979:< 1 577:. Let 536:< 1 137:, the 132:> 7 96:, and 23:, the 1982:arXiv 1871:S2CID 1753:S2CID 1705:S2CID 1679:arXiv 1092:girth 1070:33.75 859:with 538:be a 510:) ≤ 3 506:− cr( 496:) ≤ 3 492:− cr( 469:− cr( 384:with 376:Proof 370:-sets 351:, an 119:with 86:Ajtai 45:edges 41:graph 1395:> 1101:and 1072:for 588:and 516:for 334:VLSI 232:and 78:VLSI 47:and 1953:doi 1907:doi 1855:doi 1824:doi 1785:doi 1737:doi 1689:doi 1106:≥ 4 1068:by 971:= 4 881:cr( 861:cr( 583:, n 549:of 523:). 521:≥ 3 514:− 6 454:cr( 257:cr( 142:cr( 63:to 27:or 2003:: 1963:MR 1961:, 1949:24 1947:, 1937:; 1917:MR 1915:, 1903:19 1901:, 1869:, 1863:MR 1861:, 1849:, 1820:80 1818:, 1795:MR 1793:, 1781:36 1779:, 1751:, 1745:MR 1743:, 1733:17 1731:, 1703:, 1697:MR 1695:, 1687:, 1675:85 1673:, 1659:^ 1637:^ 1625:MR 1611:; 1126:cr 1111:, 1082:. 1066:64 1033:64 1002:cr 908:cr 877:= 833:= 807:pn 805:= 706:cr 629:cr 590:cr 403:cr 372:. 301:cr 252:. 250:64 246:29 226:29 193:29 162:cr 104:. 92:, 88:, 73:. 1991:. 1984:: 1970:. 1955:: 1924:. 1909:: 1893:k 1878:. 1857:: 1851:6 1833:. 1826:: 1802:. 1787:: 1760:. 1739:: 1712:. 1691:: 1681:: 1654:. 1632:. 1580:. 1574:) 1568:( 1563:1 1560:+ 1557:d 1552:1 1546:d 1542:f 1536:2 1533:+ 1530:d 1526:) 1522:3 1519:+ 1516:d 1513:( 1508:) 1502:( 1497:2 1494:+ 1491:d 1486:d 1482:f 1455:d 1435:) 1429:( 1424:1 1418:d 1414:f 1410:) 1407:3 1404:+ 1401:d 1398:( 1392:) 1386:( 1381:d 1377:f 1356:) 1353:1 1347:d 1344:( 1335:) 1329:( 1324:1 1318:d 1314:f 1293:d 1284:) 1278:( 1273:d 1269:f 1246:d 1243:2 1238:R 1190:. 1183:1 1180:+ 1177:r 1173:n 1167:2 1164:+ 1161:r 1157:e 1149:r 1145:c 1138:) 1135:G 1132:( 1108:n 1104:e 1098:r 1096:2 1079:n 1075:e 1049:. 1041:2 1037:n 1027:3 1023:e 1014:) 1011:G 1008:( 988:n 984:e 977:e 975:/ 973:n 969:p 951:. 948:n 945:p 942:3 936:e 931:2 927:p 920:) 917:G 914:( 903:4 899:p 885:) 883:G 879:p 875:E 870:G 865:) 863:G 857:G 853:H 848:p 843:G 838:e 835:p 831:E 826:H 822:H 817:p 812:G 803:E 798:H 794:p 790:G 786:n 769:. 766:] 761:H 757:n 753:[ 749:E 745:3 739:] 734:H 730:e 726:[ 722:E 715:] 710:H 702:[ 698:E 667:. 662:H 658:n 654:3 646:H 642:e 633:H 615:H 611:G 607:G 603:H 599:H 593:H 585:H 581:H 579:e 575:H 571:H 567:G 563:p 559:H 555:G 551:G 547:H 534:p 519:n 512:n 508:G 504:e 498:n 494:G 490:e 477:n 473:) 471:G 467:e 462:G 458:) 456:G 450:G 433:. 430:n 427:3 421:e 415:) 412:G 409:( 390:e 386:n 382:G 368:k 311:) 308:G 305:( 294:) 291:G 288:( 269:) 267:G 261:) 259:G 242:4 238:7 209:. 201:2 197:n 187:3 183:e 174:) 171:G 168:( 146:) 144:G 134:n 130:e 125:e 121:n 117:G 70:n 68:/ 66:e 57:n 53:e

Index

graph drawing
lower bound
minimum number of edge crossings
graph
edges
vertices
proportional
VLSI
combinatorial geometry
Ajtai
Chvátal
Newborn
Szemerédi
Leighton
simple graph
crossing number
inequality
Pach & Tóth (1997)
Pach et al. (2006)
Pach & Tóth (2000)
VLSI
Székely (1997)
incidence geometry
Szemerédi–Trotter theorem
upper bound
Beck's theorem
Tamal Dey
geometric k-sets
planar graph
Euler's formula

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.