|
In graph theory, the crossing number of a graph is the lowest number of edge crossings of a plane drawing of the graph . For instance, a graph is planar if and only if its crossing number is zero. The mathematical origin of the study of crossing numbers is in Turán's brick factory problem, in which Pál Turán asked to determine the crossing number of the complete bipartite graph . However, the same problem of minimizing crossings was also considered in sociology at approximately the same time as Turán, in connection with the construction of sociograms. It continues to be of great importance in graph drawing. Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves; the rectilinear crossing number requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of points in general position, closely related to the Happy Ending problem. ==History== During World War II, Hungarian mathematician Pál Turán 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: what is the minimum possible number of crossings in a drawing of a complete bipartite graph? Zarankiewicz attempted to solve Turán's brick factory problem; his proof contained an error, but he established a valid upper bound of : for the crossing number of the complete bipartite graph . The conjecture that this inequality is actually an equality is now known as Zarankiewicz' crossing number conjecture. The gap in the proof of the lower bound was not discovered until eleven years after publication, nearly simultaneously by Gerhard Ringel and Paul Kainen. The problem of determining the crossing number of the complete graph was first posed by Anthony Hill, and appears in print in 1960. Hill and his collaborator John Ernest were two constructionist artists fascinated by mathematics, who not only formulated this problem but also originated a conjectural upper bound for this crossing number, which Richard K. Guy published in 1960.〔 Namely, the conjecture is that : which gives values of for ; see sequence () in the OEIS. An independent formulation of the conjecture was made by Thomas L. Saaty in 1964. Saaty further verified that the upper bound is achieved for and Pan and Richter showed that it also is achieved for If only straight-line segments are permitted, then one needs more crossings. The rectilinear crossing numbers for through are , () and values up to are known, with requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.〔(【引用サイトリンク】Rectilinear Crossing Number project )〕 Interestingly, it is not known whether the ordinary and rectilinear crossing numbers are the same for bipartite complete graphs. If the Zarankiewicz conjecture is correct, then the formula for the crossing number of the complete graph is asymptotically correct; that is, : 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. There has been some progress on lower bounds, as reported by .〔.〕 An extensive survey on the various crossing-number variants, including references to recently recognized subtleties in the definition, is available. 〔.〕 The Albertson conjecture, formulated by Michael O. Albertson in 2007, states that, among all graphs with chromatic number , the complete graph has the minimum number of crossings. That is, if the Guy-Saaty conjecture on the crossing number of the complete graph is valid, every -chromatic graph has crossing number at least equal to the formula in the conjecture. It is now known to hold for . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Crossing number (graph theory)」の詳細全文を読む スポンサード リンク
|