Crossing Numbers Turn Useful
Dan Archdeacon, Gelasio Salazar · 2011
A graph G represents a relation between pairs of items. The items are commonly called vertices and the set of vertices is denoted V (G). A relation is a pair of vertices {v1, v2}. Each relation is called an edge, and the set of all edges is denoted E(G). For example, G = K5 is the graph with 5 vertices, every pair of which are together in an edge. This is called the complete graph of order 5. Graphs are important models in many contexts because of their generality. For example, the vertices may represent people and the edges represent when a pair of people are friends. Analysis of this abstracted graph can reveal an underlying structure of the social relationship. Or the vertices may represent processors in a computer network and the edges represent communication networks. The analysis of this graph can reveal the connectivity of the underlying network. An important class of graphs are those that can be drawn on a plane so that edges do not cross. Continuing the application where the graph represents a computer network, such a graph can be laid out on a circuit board so that communication channels do not cross, so no insulation is needed to avoid electrical shorts. Graphs so drawn without edge crossings are called planar graphs. Not every graph is planar; for example, the graph K5 described above is not planar. In this case the next best thing would be to draw the graph G in the plane with as few crossings as possible. This minimum taken