194:
edges with multiple intersection points. If two edges with a shared endpoint cross, the drawing can be changed locally at the crossing point, leaving the rest of the drawing unchanged, to produce a different drawing with one fewer crossing. And similarly, if two edges cross two or more times, the drawing can be changed locally at two crossing points to make a different drawing with two fewer crossings. However, these constraints are relevant for variant definitions of the crossing number that, for instance, count only the numbers of pairs of edges that cross rather than the number of crossings.
20:
212:
589:
399:
1018:, or an estimate of it is known. In addition, this inequality has algorithmic application. Specifically, Bhat and Leighton used it (for the first time) for deriving an upper bound on the number of edge crossings in a drawing which is obtained by a divide and conquer approximation algorithm for computing
242:
was forced to work in a brick factory, pushing wagon loads of bricks from kilns to storage sites. The factory had tracks from each kiln to each storage site, and the wagons were harder to push at the points where tracks crossed each other, from which Turán was led to ask his brick factory problem:
193:
Some authors add more constraints to the definition of a drawing, for instance that each pair of edges have at most one intersection point (a shared endpoint or crossing). For the crossing number as defined above, these constraints make no difference, because a crossing-minimal drawing cannot have
1357:
is defined to be the minimum number of crossings of a drawing of this type. It is always at least as large as the crossing number, and is larger for some graphs. It is known that, in general, the rectilinear crossing number can not be bounded by a function of the crossing number. The rectilinear
445:
185:
is a mapping from the vertices of the graph to disjoint points in the plane, and from the edges of the graph to curves connecting their two endpoints. No vertex should be mapped onto an edge that it is not an endpoint of, and whenever two edges have curves that intersect (other than at a shared
202:
As of April 2015, crossing numbers are known for very few graph families. In particular, except for a few initial cases, the crossing number of complete graphs, bipartite complete graphs, and products of cycles all remain unknown, although there has been some progress on lower bounds.
267:
73:
if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.
1154:
algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. These algorithms are used in the
Rectilinear Crossing Number
584:{\displaystyle {\textrm {cr}}(K_{p})\leq {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor }
190:. A crossing is counted separately for each of these crossing points, for each pair of edges that cross. The crossing number of a graph is then the minimum, over all such drawings, of the number of crossings in a drawing.
1435:(the number of pairs of edges that cross an odd number of times in any drawing). The odd crossing number is at most equal to the pairwise crossing number, which is at most equal to the crossing number. However, by the
394:{\displaystyle {\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor }
1268:
1866:
85:
asked for a factory plan that minimized the number of crossings between tracks connecting brick kilns to storage sites. Mathematically, this problem can be formalized as asking for the crossing number of a
613:. The conjecture is that there can be no better drawing, so that this formula gives the optimal number of crossings for the complete graphs. An independent formulation of the same conjecture was made by
247:, with the tracks as its edges. A factory layout can be represented as a drawing of this graph, so the problem becomes: what is the minimum possible number of crossings in a drawing of a
935:
243:
how can the kilns, storage sites, and tracks be arranged to minimize the total number of crossings? Mathematically, the kilns and storage sites can be formalized as the vertices of a
1588:
The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.
1148:
1048:
987:
1016:
862:
833:
782:
1074:
and to near-planar graphs (graphs that become planar after removal of a single edge). A closely related problem, determining the rectilinear crossing number, is
955:
802:
150:
Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, the
2518:
1321:
design in theoretical computer science. Later, Székely also realized that this inequality yielded very simple proofs of some important theorems in
720:, with 20 vertices. None of the four 7-crossing cubic graphs, with 22 vertices, are well known. The smallest 8-crossing cubic graphs include the
1677:
154:, requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a
655:
has the minimum number of crossings. That is, if the conjectured formula for the crossing number of the complete graph is correct, then every
804:
is the minimum number of edges whose removal results in a partition of the vertex set into two separated sets so that no set has more than
435:
fascinated by mathematics. They not only formulated this problem but also originated a conjectural formula for this crossing number, which
98:. Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous formula for the
2579:
1206:
1491:
Purchase, Helen C.; Cohen, Robert F.; James, Murray I. (1995). "Validating graph drawing aesthetics". In
Brandenburg, Franz-Josef (ed.).
224:
showing that Turán's brick factory problem with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots)
1353:
If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings. The
685:
610:
2605:
2352:
2781:
2392:
27:
with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number
1085:
On the positive side, there are efficient algorithms for determining whether the crossing number is less than a fixed constant
2465:
2370:
1607:(1994). "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability".
1510:
1696:
659:-chromatic graph has crossing number at least equal to the same formula. The Albertson conjecture is now known to hold for
2661:
229:
78:
1150:
on graphs of bounded degree which use the general and previously developed framework of Bhat and
Leighton. In practice
2832:
2449:
1402:
requiring either 7233 or 7234 crossings. Further values are collected by the
Rectilinear Crossing Number project.
2847:
2522:
2254:
1079:
871:
2852:
1753:
1609:
957:
has bounded vertex degrees. This fundamental inequality can be used to derive an asymptotic lower bound for
126:
1326:
411:. This bound has been conjectured to be the optimal number of crossings for all complete bipartite graphs.
257:
attempted to solve Turán's brick factory problem; his proof contained an error, but he established a valid
187:
55:
1330:
2559:. Theory and Practice of Combinatorics. North-Holland Mathematics Studies. Vol. 60. pp. 9–12.
2811:
2441:
1288:
1168:
106:
2353:
Graph
Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers
1493:
Graph
Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings
2837:
2776:
2487:
2297:
1090:
186:
endpoint) their intersections should form a finite set of proper crossings, where the two curves are
1810:
Proof
Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)
2071:
1436:
689:
248:
244:
87:
1936:
1776:
1532:
1462:
1109:
740:
739:
In 2009, Pegg and Exoo conjectured that the smallest cubic graph with crossing number 13 is the
2842:
2586:
2437:
1767:
1275:
This relation between edges, vertices, and the crossing number was discovered independently by
258:
254:
709:
2699:
1156:
1115:
1075:
424:
169:
points in general position. The problem of determining this number is closely related to the
122:
2753:
2684:
2626:
2564:
2423:
2277:
2234:
2102:
1957:
1875:
1817:
1322:
1021:
960:
638:
432:
170:
992:
838:
807:
758:
8:
2548:
2146:
2005:
1559:
1280:
865:
114:
2603:
Székely, L. A. (1997). "Crossing numbers and hard Erdős problems in discrete geometry".
2485:(2003). "Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas".
2355:. Lecture Notes in Computer Science. Vol. 5849. Springer-Verlag. pp. 334–344.
1879:
2757:
2630:
2401:
2324:
2306:
2295:(2013). "Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard".
2106:
2080:
1981:
1961:
1723:
1705:
1654:
Proceedings of the 39th Annual
Symposium on Foundations of Computer Science (FOCS 1998)
1626:
1579:
940:
787:
144:
2552:
2168:
1898:
1861:
1284:
2761:
2461:
2366:
2188:
2184:
2110:
2002:
1903:
1506:
2634:
1965:
2790:
2741:
2711:
2670:
2614:
2496:
2453:
2411:
2356:
2328:
2316:
2263:
2222:
2210:
2180:
2090:
2045:
1945:
1893:
1883:
1785:
1727:
1715:
1657:
1618:
1571:
1541:
1496:
1338:
1063:
642:
620:
Saaty further verified that this formula gives the optimal number of crossings for
182:
2531:
on the
Institute for Software Technology at Graz, University of Technology (2009).
2069:(2020). "There are no cubic graphs on 26 vertices with crossing number 10 or 11".
2749:
2680:
2622:
2560:
2482:
2419:
2361:
2343:
2273:
2230:
2125:
2098:
1953:
1857:
1813:
1495:. Lecture Notes in Computer Science. Vol. 1027. Springer. pp. 435–446.
717:
641:, formulated by Michael O. Albertson in 2007, states that, among all graphs with
614:
2544:
1317:
The motivation of
Leighton in studying crossing numbers was for applications to
1276:
2729:
2415:
2268:
2249:
2094:
1867:
Proceedings of the National Academy of Sciences of the United States of America
1835:
1805:
1600:
1527:
1406:
701:
439:
published in 1960. Namely, it is known that there always exists a drawing with
436:
420:
239:
162:
159:
155:
99:
82:
2618:
2500:
1719:
1676:
de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. (2006).
2826:
2206:
2192:
1661:
1456:
1416:
crossings per edge, but not fewer. The graphs that can be drawn with at most
1059:
744:
733:
705:
62:
24:
2543:
2457:
1790:
1771:
1750:
Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures
1741:
1649:
2715:
2387:
2029:
1907:
1745:
1604:
1545:
1174:
713:
235:
70:
40:
19:
1888:
2292:
2066:
1431:(the minimum number of pairs of edges that cross in any drawing) and the
1071:
725:
721:
675:
428:
2745:
2675:
2652:
2050:
2033:
1630:
1583:
1501:
729:
94:
at approximately the same time, in connection with the construction of
2320:
1949:
1439:, whenever one of these numbers is zero, they all are. Schaefer (
732:, with 24 vertices. The smallest 11-crossing cubic graphs include the
2648:
2010:
1980:
Barát, János; Tóth, Géza (2009). "Towards the Albertson Conjecture".
1710:
1334:
1151:
1070:
problem. In fact the problem remains NP-hard even when restricted to
95:
91:
2226:
1622:
1575:
1263:{\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}
211:
2734:
Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
2528:
2450:
Proceedings of the 29th Annual ACM Symposium on Theory of Computing
2406:
2085:
2795:
2311:
1986:
1459:, a planar graph formed by replacing each crossing by a new vertex
181:
For the purposes of defining the crossing number, a drawing of an
1921:
Pan, Shengjun; Richter, R. Bruce (2007). "The crossing number of
1067:
1298:
is the best known to date, and is due to Ackerman. The constant
1058:
In general, determining the crossing number of a graph is hard;
1675:
716:, with 18 vertices. The smallest 6-crossing cubic graph is the
712:, with 16 vertices. The smallest 5-crossing cubic graph is the
708:, with 14 vertices. The smallest 4-crossing cubic graph is the
704:, with 10 vertices. The smallest 3-crossing cubic graph is the
2000:
700:, with 6 vertices. The smallest 2-crossing cubic graph is the
743:
and the smallest cubic graph with crossing number 170 is the
2580:"On topological graphs with at most four crossings per edge"
2153:. Foundations of Computing Series. Cambridge, MA: MIT Press.
2064:
1652:; TĂłth, G. (1998). "Which crossing number is it, anyway?".
1381:
1318:
680:
606:
427:, and appeared in print in 1960. Hill and his collaborator
140:
2205:
1808:(1969). "The decline and fall of Zarankiewicz's theorem".
2167:
Bhatt, Sandeep N.; Leighton, Frank Thomson (1984-04-01).
2390:(2005). "Computing crossing numbers in quadratic time".
1862:"The minimum number of intersections in complete graphs"
1562:(1944). "The graphic presentation of sociometric data".
404:
for the crossing number of the complete bipartite graph
2290:
627:
and Pan and Richter showed that it also is optimal for
2777:"The graph crossing number and its variants: a survey"
1752:. Mathematical Surveys and Monographs. Vol. 152.
419:
The problem of determining the crossing number of the
2345:
Complexity of some geometric and topological problems
1209:
1118:
1024:
995:
963:
943:
874:
841:
810:
790:
761:
750:
678:
with crossing numbers 1–8 and 11 are known (sequence
448:
414:
270:
2169:"A framework for solving VLSI graph layout problems"
2065:
Clancy, Kieran; Haythorpe, Michael; Newcombe, Alex;
1840:
Nabla (Bulletin of the Malayan Mathematical Society)
1748:(2009). "5.1 Crossings—the Brick Factory Problem".
1490:
1427:Other variants of the crossing number include the
1262:
1142:
1042:
1010:
981:
949:
929:
856:
827:
796:
776:
583:
393:
61:is the lowest number of edge crossings of a plane
2436:
1162:
158:is essentially the same as the minimum number of
2824:
2732:(1965). "Ein Sechsfarbenproblem auf der Kugel".
2698:Bienstock, Daniel; Dean, Nathaniel (July 1993).
2480:
1599:
1053:
2602:
2215:SIAM Journal on Algebraic and Discrete Methods
1558:
688:). The smallest 1-crossing cubic graph is the
2697:
2166:
1678:"Improved bounds for the crossing numbers of
2516:
2145:
1812:. Academic Press, New York. pp. 63–69.
1772:"On a Problem of P. Turán Concerning Graphs"
1766:
206:
77:The study of crossing numbers originated in
2247:
2141:
2139:
2137:
2135:
16:Fewest edge crossings in drawing of a graph
2647:
2250:"Crossing number is hard for cubic graphs"
2213:(1983). "Crossing number is NP-complete".
1920:
1740:
90:. The same problem arose independently in
2794:
2700:"Bounds for rectilinear crossing numbers"
2674:
2405:
2360:
2310:
2267:
2084:
2049:
1994:
1985:
1979:
1897:
1887:
1789:
1709:
1500:
930:{\displaystyle cr(G)+n=\Omega (b^{2}(G))}
611:On-line Encyclopedia of Integer Sequences
109:states that, for graphs where the number
2809:
2774:
2768:
2606:Combinatorics, Probability and Computing
2577:
2571:
2446:Computing crossing number in linear time
2341:
2132:
2028:
1830:
1828:
1648:
1444:
1440:
594:crossings. This formula gives values of
210:
18:
2782:The Electronic Journal of Combinatorics
2596:
2539:
2537:
2512:
2510:
2393:Journal of Computer and System Sciences
2241:
2173:Journal of Computer and System Sciences
2126:"Rectilinear Drawings of Famous Graphs"
1644:
1642:
1640:
1287:, and by Leighton . It is known as the
1198:the crossing number is always at least
117:is sufficiently larger than the number
2825:
2728:
2722:
2519:"Rectilinear Crossing Number project"
2386:
2380:
2162:
2160:
2024:
2022:
2001:
1856:
1825:
1526:
2803:
2534:
2507:
2117:
1850:
1697:SIAM Journal on Discrete Mathematics
1669:
1637:
1520:
2662:Discrete and Computational Geometry
2641:
2474:
1838:(1960). "A combinatorial problem".
1834:
1804:
1798:
1552:
1420:crossings per edge are also called
13:
2430:
2335:
2284:
2199:
2157:
2058:
2019:
1973:
1914:
1484:
1306:, but at the expense of replacing
1093:. It remains difficult for larger
899:
751:Connections to the bisection width
415:Complete graphs and graph coloring
125:, the crossing number is at least
14:
2864:
1734:
1593:
1337:used it to prove upper bounds on
1089:. In other words, the problem is
2123:
1760:
1412:if it can be drawn with at most
197:
2691:
2255:Journal of Combinatorial Theory
1465:, the puzzle that asks whether
1080:existential theory of the reals
669:
1447:) surveys many such variants.
1222:
1216:
1163:The crossing number inequality
1131:
1125:
1037:
1031:
1005:
999:
976:
970:
924:
921:
915:
902:
887:
881:
851:
845:
771:
765:
469:
456:
297:
278:
176:
1:
1754:American Mathematical Society
1610:American Mathematical Monthly
1530:(1977). "A Note of Welcome".
1478:
1474:can be drawn with 0 crossings
1378:1, 3, 9, 19, 36, 62, 102, 153
1348:
1066:showed in 1983 that it is an
596:1, 3, 9, 18, 36, 60, 100, 150
230:Turán's brick factory problem
79:Turán's brick factory problem
2653:"Improved bounds for planar
2362:10.1007/978-3-642-11805-0_32
2185:10.1016/0022-0000(84)90071-0
1054:Complexity and approximation
7:
2657:-sets and related problems"
2529:Rectilinear Crossing Number
1450:
1355:rectilinear crossing number
1310:with the worse constant of
1108:. There are also efficient
152:rectilinear crossing number
69:. For instance, a graph is
10:
2869:
2813:Crossing Numbers of Graphs
2481:Even, Guy; Guha, Sudipto;
2416:10.1016/j.jcss.2003.07.008
2269:10.1016/j.jctb.2005.09.009
2095:10.1007/s00373-020-02204-6
1289:crossing number inequality
1169:Crossing number inequality
1166:
238:, Hungarian mathematician
227:
107:crossing number inequality
2810:Schaefer, Marcus (2018).
2775:Schaefer, Marcus (2014).
2619:10.1017/S0963548397002976
2501:10.1137/S0097539700373520
2488:SIAM Journal on Computing
2342:Schaefer, Marcus (2010).
2298:SIAM Journal on Computing
2151:Complexity Issues in VLSI
1720:10.1137/S0895480104442741
1331:Szemerédi-Trotter theorem
1091:fixed-parameter tractable
207:Complete bipartite graphs
139:. It has applications in
2833:Topological graph theory
2072:Graphs and Combinatorics
2034:"Crossing Number Graphs"
1662:10.1109/SFCS.1998.743512
1429:pairwise crossing number
1110:approximation algorithms
755:The 2/3-bisection width
690:complete bipartite graph
249:complete bipartite graph
245:complete bipartite graph
88:complete bipartite graph
2704:Journal of Graph Theory
2578:Ackerman, Eyal (2013).
2557:Crossing-free subgraphs
2458:10.1145/1250790.1250848
2438:Kawarabayashi, Ken-ichi
2006:"Graph Crossing Number"
1937:Journal of Graph Theory
1791:10.4064/fm-41-1-137-145
1777:Fundamenta Mathematicae
1533:Journal of Graph Theory
1463:Three utilities problem
1143:{\displaystyle cr(G)+n}
433:constructionist artists
165:determined by a set of
2848:Geometric intersection
2716:10.1002/jgt.3190170308
1601:Scheinerman, Edward R.
1546:10.1002/jgt.3190010105
1264:
1144:
1044:
1012:
983:
951:
931:
858:
829:
798:
778:
585:
395:
255:Kazimierz Zarankiewicz
225:
215:An optimal drawing of
36:
1889:10.1073/pnas.52.3.688
1407:local crossing number
1358:crossing numbers for
1265:
1157:distributed computing
1145:
1045:
1043:{\displaystyle cr(G)}
1013:
984:
982:{\displaystyle cr(G)}
952:
932:
859:
830:
799:
779:
648:, the complete graph
586:
396:
214:
22:
2853:NP-complete problems
2452:. pp. 382–390.
2248:Hliněný, P. (2006).
1656:. pp. 617–626.
1560:Bronfenbrenner, Urie
1437:Hanani–Tutte theorem
1207:
1116:
1022:
1011:{\displaystyle b(G)}
993:
961:
941:
872:
857:{\displaystyle b(G)}
839:
835:vertices. Computing
828:{\displaystyle 2n/3}
808:
788:
777:{\displaystyle b(G)}
759:
639:Albertson conjecture
446:
268:
171:happy ending problem
2038:Mathematica Journal
2032:; Exoo, G. (2009).
1880:1964PNAS...52..688S
1756:. pp. 126–127.
1433:odd crossing number
1384:) and values up to
1291:or crossing lemma.
741:Tutte–Coxeter graph
710:Möbius-Kantor graph
423:was first posed by
2746:10.1007/BF02996313
2676:10.1007/PL00009354
2517:Oswin Aichholzer.
2051:10.3888/tmj.11.2-2
2003:Weisstein, Eric W.
1502:10.1007/BFb0021827
1323:incidence geometry
1302:can be lowered to
1260:
1173:For an undirected
1140:
1112:for approximating
1040:
1008:
979:
947:
927:
854:
825:
794:
784:of a simple graph
774:
736:with 28 vertices.
581:
391:
226:
145:incidence geometry
37:
2467:978-1-59593-631-8
2372:978-3-642-11804-3
2321:10.1137/120872310
1950:10.1002/jgt.20249
1512:978-3-540-60723-6
1255:
950:{\displaystyle G}
797:{\displaystyle G}
575:
549:
523:
497:
483:
453:
385:
359:
341:
315:
275:
23:A drawing of the
2860:
2838:Graph invariants
2818:
2817:
2807:
2801:
2800:
2798:
2772:
2766:
2765:
2740:(1–2): 107–117.
2726:
2720:
2719:
2695:
2689:
2688:
2678:
2645:
2639:
2638:
2600:
2594:
2593:
2591:
2585:. Archived from
2584:
2575:
2569:
2568:
2541:
2532:
2526:
2521:. Archived from
2514:
2505:
2504:
2483:Schieber, Baruch
2478:
2472:
2471:
2434:
2428:
2427:
2409:
2384:
2378:
2376:
2364:
2350:
2339:
2333:
2332:
2314:
2305:(5): 1803–1829.
2288:
2282:
2281:
2271:
2245:
2239:
2238:
2203:
2197:
2196:
2164:
2155:
2154:
2143:
2130:
2129:
2121:
2115:
2114:
2088:
2079:(6): 1713–1721.
2062:
2056:
2055:
2053:
2026:
2017:
2016:
2015:
1998:
1992:
1991:
1989:
1977:
1971:
1969:
1933:
1929:
1918:
1912:
1911:
1901:
1891:
1854:
1848:
1847:
1832:
1823:
1821:
1802:
1796:
1795:
1793:
1768:Zarankiewicz, K.
1764:
1758:
1757:
1738:
1732:
1731:
1713:
1673:
1667:
1665:
1646:
1635:
1634:
1605:Wilf, Herbert S.
1597:
1591:
1590:
1556:
1550:
1549:
1524:
1518:
1516:
1504:
1488:
1473:
1423:
1419:
1415:
1411:
1401:
1393:are known, with
1392:
1379:
1375:
1366:
1313:
1309:
1305:
1301:
1297:
1269:
1267:
1266:
1261:
1256:
1254:
1253:
1252:
1239:
1238:
1229:
1197:
1188:edges such that
1187:
1183:
1179:
1149:
1147:
1146:
1141:
1107:
1096:
1088:
1049:
1047:
1046:
1041:
1017:
1015:
1014:
1009:
988:
986:
985:
980:
956:
954:
953:
948:
937:, provided that
936:
934:
933:
928:
914:
913:
863:
861:
860:
855:
834:
832:
831:
826:
821:
803:
801:
800:
795:
783:
781:
780:
775:
699:
683:
665:
658:
654:
647:
643:chromatic number
633:
626:
604:
597:
590:
588:
587:
582:
580:
576:
571:
560:
554:
550:
545:
534:
528:
524:
519:
508:
502:
498:
490:
484:
476:
468:
467:
455:
454:
451:
410:
400:
398:
397:
392:
390:
386:
381:
370:
364:
360:
352:
346:
342:
337:
326:
320:
316:
308:
296:
295:
277:
276:
273:
223:
183:undirected graph
168:
138:
120:
112:
68:
60:
53:
34:
2868:
2867:
2863:
2862:
2861:
2859:
2858:
2857:
2823:
2822:
2821:
2808:
2804:
2773:
2769:
2730:Ringel, Gerhard
2727:
2723:
2696:
2692:
2646:
2642:
2601:
2597:
2589:
2582:
2576:
2572:
2551:; Newborn, M.;
2542:
2535:
2515:
2508:
2479:
2475:
2468:
2435:
2431:
2385:
2381:
2373:
2348:
2340:
2336:
2291:Cabello S. and
2289:
2285:
2246:
2242:
2227:10.1137/0604033
2204:
2200:
2165:
2158:
2144:
2133:
2122:
2118:
2063:
2059:
2027:
2020:
1999:
1995:
1978:
1974:
1931:
1928:
1922:
1919:
1915:
1855:
1851:
1833:
1826:
1806:Guy, Richard K.
1803:
1799:
1765:
1761:
1739:
1735:
1690:
1683:
1674:
1670:
1647:
1638:
1623:10.2307/2975158
1617:(10): 939–943.
1598:
1594:
1576:10.2307/2785096
1557:
1553:
1525:
1521:
1513:
1489:
1485:
1481:
1472:
1466:
1453:
1421:
1417:
1413:
1409:
1400:
1394:
1391:
1385:
1377:
1374:
1368:
1365:
1359:
1351:
1311:
1307:
1303:
1299:
1295:
1283:, Newborn, and
1248:
1244:
1240:
1234:
1230:
1228:
1208:
1205:
1204:
1189:
1185:
1181:
1177:
1171:
1165:
1117:
1114:
1113:
1098:
1094:
1086:
1056:
1023:
1020:
1019:
994:
991:
990:
962:
959:
958:
942:
939:
938:
909:
905:
873:
870:
869:
840:
837:
836:
817:
809:
806:
805:
789:
786:
785:
760:
757:
756:
753:
718:Desargues graph
698:
692:
679:
672:
660:
656:
653:
649:
645:
628:
621:
615:Thomas L. Saaty
605:; see sequence
599:
595:
561:
559:
555:
535:
533:
529:
509:
507:
503:
489:
485:
475:
463:
459:
450:
449:
447:
444:
443:
417:
409:
405:
371:
369:
365:
351:
347:
327:
325:
321:
307:
303:
285:
281:
272:
271:
269:
266:
265:
232:
222:
216:
209:
200:
179:
166:
130:
118:
110:
100:complete graphs
66:
58:
47:
45:crossing number
28:
17:
12:
11:
5:
2866:
2856:
2855:
2850:
2845:
2840:
2835:
2820:
2819:
2802:
2767:
2721:
2710:(3): 333–348.
2690:
2669:(3): 373–382.
2640:
2613:(3): 353–358.
2595:
2592:on 2014-07-14.
2570:
2533:
2525:on 2012-12-30.
2506:
2495:(1): 231–252.
2473:
2466:
2429:
2400:(2): 285–302.
2379:
2371:
2334:
2283:
2262:(4): 455–471.
2240:
2221:(3): 312–316.
2211:Johnson, D. S.
2198:
2179:(2): 300–343.
2156:
2131:
2116:
2057:
2018:
1993:
1972:
1944:(2): 128–134.
1926:
1913:
1874:(3): 688–690.
1849:
1824:
1797:
1759:
1733:
1704:(1): 189–202.
1688:
1681:
1668:
1636:
1592:
1570:(3): 283–289.
1551:
1519:
1511:
1482:
1480:
1477:
1476:
1475:
1470:
1460:
1452:
1449:
1398:
1389:
1372:
1363:
1350:
1347:
1327:Beck's theorem
1273:
1272:
1271:
1270:
1259:
1251:
1247:
1243:
1237:
1233:
1227:
1224:
1221:
1218:
1215:
1212:
1167:Main article:
1164:
1161:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1055:
1052:
1039:
1036:
1033:
1030:
1027:
1007:
1004:
1001:
998:
978:
975:
972:
969:
966:
946:
926:
923:
920:
917:
912:
908:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
853:
850:
847:
844:
824:
820:
816:
813:
793:
773:
770:
767:
764:
752:
749:
702:Petersen graph
696:
671:
668:
651:
592:
591:
579:
574:
570:
567:
564:
558:
553:
548:
544:
541:
538:
532:
527:
522:
518:
515:
512:
506:
501:
496:
493:
488:
482:
479:
474:
471:
466:
462:
458:
437:Richard K. Guy
421:complete graph
416:
413:
407:
402:
401:
389:
384:
380:
377:
374:
368:
363:
358:
355:
350:
345:
340:
336:
333:
330:
324:
319:
314:
311:
306:
302:
299:
294:
291:
288:
284:
280:
228:Main article:
220:
208:
205:
199:
196:
178:
175:
163:quadrilaterals
156:complete graph
15:
9:
6:
4:
3:
2:
2865:
2854:
2851:
2849:
2846:
2844:
2843:Graph drawing
2841:
2839:
2836:
2834:
2831:
2830:
2828:
2815:
2814:
2806:
2797:
2796:10.37236/2713
2792:
2788:
2784:
2783:
2778:
2771:
2763:
2759:
2755:
2751:
2747:
2743:
2739:
2736:(in German).
2735:
2731:
2725:
2717:
2713:
2709:
2705:
2701:
2694:
2686:
2682:
2677:
2672:
2668:
2664:
2663:
2658:
2656:
2650:
2644:
2636:
2632:
2628:
2624:
2620:
2616:
2612:
2608:
2607:
2599:
2588:
2581:
2574:
2566:
2562:
2558:
2554:
2553:Szemerédi, E.
2550:
2546:
2540:
2538:
2530:
2524:
2520:
2513:
2511:
2502:
2498:
2494:
2490:
2489:
2484:
2477:
2469:
2463:
2459:
2455:
2451:
2447:
2443:
2439:
2433:
2425:
2421:
2417:
2413:
2408:
2403:
2399:
2395:
2394:
2389:
2383:
2374:
2368:
2363:
2358:
2354:
2347:
2346:
2338:
2330:
2326:
2322:
2318:
2313:
2308:
2304:
2300:
2299:
2294:
2287:
2279:
2275:
2270:
2265:
2261:
2257:
2256:
2251:
2244:
2236:
2232:
2228:
2224:
2220:
2216:
2212:
2208:
2202:
2194:
2190:
2186:
2182:
2178:
2174:
2170:
2163:
2161:
2152:
2148:
2142:
2140:
2138:
2136:
2127:
2120:
2112:
2108:
2104:
2100:
2096:
2092:
2087:
2082:
2078:
2074:
2073:
2068:
2061:
2052:
2047:
2043:
2039:
2035:
2031:
2025:
2023:
2013:
2012:
2007:
2004:
1997:
1988:
1983:
1976:
1967:
1963:
1959:
1955:
1951:
1947:
1943:
1939:
1938:
1925:
1917:
1909:
1905:
1900:
1895:
1890:
1885:
1881:
1877:
1873:
1869:
1868:
1863:
1859:
1853:
1845:
1841:
1837:
1831:
1829:
1819:
1815:
1811:
1807:
1801:
1792:
1787:
1783:
1779:
1778:
1773:
1769:
1763:
1755:
1751:
1747:
1746:Sharir, Micha
1743:
1737:
1729:
1725:
1721:
1717:
1712:
1707:
1703:
1699:
1698:
1693:
1691:
1684:
1672:
1663:
1659:
1655:
1651:
1645:
1643:
1641:
1632:
1628:
1624:
1620:
1616:
1612:
1611:
1606:
1602:
1596:
1589:
1585:
1581:
1577:
1573:
1569:
1565:
1561:
1555:
1547:
1543:
1539:
1535:
1534:
1529:
1523:
1514:
1508:
1503:
1498:
1494:
1487:
1483:
1469:
1464:
1461:
1458:
1457:Planarization
1455:
1454:
1448:
1446:
1442:
1438:
1434:
1430:
1425:
1408:
1403:
1397:
1388:
1383:
1371:
1362:
1356:
1346:
1344:
1342:
1336:
1332:
1328:
1324:
1320:
1315:
1294:The constant
1292:
1290:
1286:
1282:
1278:
1257:
1249:
1245:
1241:
1235:
1231:
1225:
1219:
1213:
1210:
1203:
1202:
1201:
1200:
1199:
1196:
1192:
1184:vertices and
1176:
1170:
1160:
1158:
1153:
1137:
1134:
1128:
1122:
1119:
1111:
1105:
1101:
1092:
1083:
1081:
1077:
1073:
1069:
1065:
1061:
1051:
1034:
1028:
1025:
1002:
996:
973:
967:
964:
944:
918:
910:
906:
896:
893:
890:
884:
878:
875:
867:
848:
842:
822:
818:
814:
811:
791:
768:
762:
748:
746:
745:Tutte 12-cage
742:
737:
735:
734:Coxeter graph
731:
727:
723:
719:
715:
711:
707:
706:Heawood graph
703:
695:
691:
687:
682:
677:
674:The smallest
667:
663:
644:
640:
635:
631:
624:
618:
616:
612:
608:
602:
577:
572:
568:
565:
562:
556:
551:
546:
542:
539:
536:
530:
525:
520:
516:
513:
510:
504:
499:
494:
491:
486:
480:
477:
472:
464:
460:
442:
441:
440:
438:
434:
430:
426:
422:
412:
387:
382:
378:
375:
372:
366:
361:
356:
353:
348:
343:
338:
334:
331:
328:
322:
317:
312:
309:
304:
300:
292:
289:
286:
282:
264:
263:
262:
260:
256:
252:
250:
246:
241:
237:
231:
219:
213:
204:
198:Special cases
195:
191:
189:
184:
174:
172:
164:
161:
157:
153:
148:
146:
142:
137:
133:
128:
124:
116:
108:
103:
101:
97:
93:
89:
84:
80:
75:
72:
65:of the graph
64:
57:
51:
46:
42:
32:
26:
25:Heawood graph
21:
2816:. CRC Press.
2812:
2805:
2786:
2780:
2770:
2737:
2733:
2724:
2707:
2703:
2693:
2666:
2660:
2654:
2643:
2610:
2604:
2598:
2587:the original
2573:
2556:
2523:the original
2492:
2486:
2476:
2445:
2432:
2397:
2391:
2382:
2344:
2337:
2302:
2296:
2286:
2259:
2258:. Series B.
2253:
2243:
2218:
2214:
2207:Garey, M. R.
2201:
2176:
2172:
2150:
2147:Leighton, T.
2119:
2076:
2070:
2067:Pegg, Ed Jr.
2060:
2041:
2037:
2009:
1996:
1975:
1941:
1935:
1923:
1916:
1871:
1865:
1852:
1843:
1839:
1809:
1800:
1781:
1775:
1762:
1749:
1736:
1711:math/0404142
1701:
1695:
1686:
1679:
1671:
1653:
1614:
1608:
1595:
1587:
1567:
1563:
1554:
1537:
1531:
1522:
1492:
1486:
1467:
1432:
1428:
1426:
1405:A graph has
1404:
1395:
1386:
1369:
1360:
1354:
1352:
1340:
1316:
1293:
1274:
1194:
1190:
1175:simple graph
1172:
1103:
1099:
1084:
1072:cubic graphs
1057:
868:proved that
864:is NP-hard.
754:
738:
714:Pappus graph
693:
676:cubic graphs
673:
670:Cubic graphs
661:
636:
629:
622:
619:
603:= 5, ..., 12
600:
593:
425:Anthony Hill
418:
403:
253:
236:World War II
233:
217:
201:
192:
180:
151:
149:
135:
131:
127:proportional
104:
76:
49:
44:
41:graph theory
38:
30:
2549:Chvátal, V.
2442:Reed, Bruce
2030:Pegg, E. T.
1858:Saaty, T.L.
1784:: 137–145.
1742:Pach, János
726:McGee graph
722:Nauru graph
429:John Ernest
259:upper bound
177:Definitions
143:design and
81:, in which
2827:Categories
2649:Dey, T. K.
2407:cs/0009010
2086:1804.10336
1836:Guy, R. K.
1564:Sociometry
1479:References
1349:Variations
1339:geometric
1325:, such as
1097:, such as
730:cage graph
188:transverse
96:sociograms
2762:123286264
2545:Ajtai, M.
2388:Grohe, M.
2312:1203.5944
2193:0022-0000
2124:Exoo, G.
2111:253889498
2011:MathWorld
1987:0909.0413
1528:Turán, P.
1424:-planar.
1335:Tamal Dey
1285:Szemerédi
1226:≥
1214:
1159:project.
1152:heuristic
900:Ω
728:or (3,7)-
617:in 1964.
566:−
540:−
514:−
473:≤
431:were two
376:−
332:−
301:≤
240:Pál Turán
92:sociology
83:Pál Turán
2789:. DS21.
2651:(1998).
2635:36602807
2555:(1982).
2444:(2007).
2293:Mohar B.
2149:(1983).
1966:37155969
1908:16591215
1860:(1964).
1846:: 68–72.
1770:(1954).
1650:Pach, J.
1451:See also
1367:through
1329:and the
1078:for the
1076:complete
866:Leighton
724:and the
632:= 11, 12
578:⌋
557:⌊
552:⌋
531:⌊
526:⌋
505:⌊
500:⌋
487:⌊
388:⌋
367:⌊
362:⌋
349:⌊
344:⌋
323:⌊
318:⌋
305:⌊
123:vertices
2754:0187232
2685:1608878
2627:1464571
2565:0806962
2424:2059096
2329:6535755
2278:2232384
2235:0711340
2103:4163409
1958:2350621
1876:Bibcode
1818:0253931
1728:1509054
1631:2975158
1584:2785096
1540:: 7–9.
1382:A014540
1281:Chvátal
1068:NP-hard
1064:Johnson
989:, when
684:in the
681:A110507
609:in the
607:A000241
234:During
63:drawing
2760:
2752:
2683:
2633:
2625:
2563:
2527:, and
2464:
2422:
2369:
2327:
2276:
2233:
2191:
2109:
2101:
1964:
1956:
1906:
1899:300329
1896:
1816:
1726:
1629:
1582:
1509:
1333:, and
1193:> 7
160:convex
71:planar
43:, the
2758:S2CID
2631:S2CID
2590:(PDF)
2583:(PDF)
2402:arXiv
2349:(PDF)
2325:S2CID
2307:arXiv
2107:S2CID
2081:arXiv
2044:(2).
1982:arXiv
1962:S2CID
1724:S2CID
1706:arXiv
1627:JSTOR
1580:JSTOR
1343:-sets
1277:Ajtai
1180:with
1060:Garey
115:edges
56:graph
54:of a
33:) = 3
2787:1000
2462:ISBN
2367:ISBN
2189:ISSN
1904:PMID
1685:and
1507:ISBN
1445:2018
1441:2014
1376:are
1319:VLSI
1062:and
1050:.
686:OEIS
664:≤ 16
637:The
625:≤ 10
598:for
141:VLSI
105:The
2791:doi
2742:doi
2712:doi
2671:doi
2615:doi
2497:doi
2454:doi
2412:doi
2357:doi
2317:doi
2264:doi
2223:doi
2181:doi
2091:doi
2046:doi
1946:doi
1934:".
1932:100
1930:is
1894:PMC
1884:doi
1786:doi
1716:doi
1682:m,n
1658:doi
1619:doi
1615:101
1572:doi
1542:doi
1497:doi
1471:3,3
1380:, (
1106:|/2
1102:= |
697:3,3
408:m,n
261:of
221:4,7
129:to
121:of
113:of
48:cr(
39:In
29:cr(
2829::
2785:.
2779:.
2756:.
2750:MR
2748:.
2738:29
2708:17
2706:.
2702:.
2681:MR
2679:.
2667:19
2665:.
2659:.
2629:.
2623:MR
2621:.
2609:.
2561:MR
2547:;
2536:^
2509:^
2493:32
2491:.
2460:.
2448:.
2440:;
2420:MR
2418:.
2410:.
2398:68
2396:.
2365:.
2351:.
2323:.
2315:.
2303:42
2301:.
2274:MR
2272:.
2260:96
2252:.
2231:MR
2229:.
2217:.
2209:;
2187:.
2177:28
2175:.
2171:.
2159:^
2134:^
2105:.
2099:MR
2097:.
2089:.
2077:36
2075:.
2042:11
2040:.
2036:.
2021:^
2008:.
1960:.
1954:MR
1952:.
1942:56
1940:.
1927:11
1902:.
1892:.
1882:.
1872:52
1870:.
1864:.
1842:.
1827:^
1814:MR
1782:41
1780:.
1774:.
1744:;
1722:.
1714:.
1702:20
1700:.
1694:.
1639:^
1625:.
1613:.
1603:;
1586:.
1578:.
1566:.
1536:.
1505:.
1443:,
1399:28
1390:27
1373:12
1345:.
1314:.
1312:64
1308:29
1296:29
1279:,
1242:29
1211:cr
1082:.
747:.
666:.
634:.
452:cr
274:cr
251:?
173:.
147:.
102:.
2799:.
2793::
2764:.
2744::
2718:.
2714::
2687:.
2673::
2655:k
2637:.
2617::
2611:6
2567:.
2503:.
2499::
2470:.
2456::
2426:.
2414::
2404::
2377:.
2375:.
2359::
2331:.
2319::
2309::
2280:.
2266::
2237:.
2225::
2219:4
2195:.
2183::
2128:.
2113:.
2093::
2083::
2054:.
2048::
2014:.
1990:.
1984::
1970:.
1968:.
1948::
1924:K
1910:.
1886::
1878::
1844:7
1822:.
1820:.
1794:.
1788::
1730:.
1718::
1708::
1692:"
1689:n
1687:K
1680:K
1666:.
1664:.
1660::
1633:.
1621::
1574::
1568:7
1548:.
1544::
1538:1
1517:.
1515:.
1499::
1468:K
1422:k
1418:k
1414:k
1410:k
1396:K
1387:K
1370:K
1364:5
1361:K
1341:k
1304:4
1300:7
1258:.
1250:2
1246:n
1236:3
1232:e
1223:)
1220:G
1217:(
1195:n
1191:e
1186:e
1182:n
1178:G
1138:n
1135:+
1132:)
1129:G
1126:(
1123:r
1120:c
1104:V
1100:k
1095:k
1087:k
1038:)
1035:G
1032:(
1029:r
1026:c
1006:)
1003:G
1000:(
997:b
977:)
974:G
971:(
968:r
965:c
945:G
925:)
922:)
919:G
916:(
911:2
907:b
903:(
897:=
894:n
891:+
888:)
885:G
882:(
879:r
876:c
852:)
849:G
846:(
843:b
823:3
819:/
815:n
812:2
792:G
772:)
769:G
766:(
763:b
694:K
662:n
657:n
652:n
650:K
646:n
630:p
623:p
601:p
573:2
569:3
563:p
547:2
543:2
537:p
521:2
517:1
511:p
495:2
492:p
481:4
478:1
470:)
465:p
461:K
457:(
406:K
383:2
379:1
373:m
357:2
354:m
339:2
335:1
329:n
313:2
310:n
298:)
293:n
290:,
287:m
283:K
279:(
218:K
167:n
136:n
134:/
132:e
119:n
111:e
67:G
59:G
52:)
50:G
35:.
31:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
