**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Crossing number (graph theory)

Summary

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar 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.
The study of crossing numbers originated in Turán's brick factory problem, in which Pál Turán 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 complete bipartite graph. The same problem arose independently in sociology at approximately the same time, in connection with the construction of sociograms. Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous formula for the complete graphs.
The crossing number inequality 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 e^3/n^2. It has applications in VLSI design and incidence geometry.
Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, 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 n points in general position. The problem of determining this number is closely related to the happy ending problem.
For the purposes of defining the crossing number, a drawing of an undirected graph 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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (27)

Related courses (2)

Graph embedding

In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.

Cage (graph theory)

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an (r, g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. An (r, g)-cage is an (r, g)-graph with the smallest possible number of vertices, among all (r, g)-graphs. A (3, g)-cage is often called a g-cage. It is known that an (r, g)-graph exists for any combination of r ≥ 2 and g ≥ 3.

Endre Szemerédi

Endre Szemerédi (ˈɛndrɛ ˈsɛmɛreːdi; born August 21, 1940) is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science at Rutgers University since 1986. He also holds a professor emeritus status at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences. Szemerédi has won prizes in mathematics and science, including the Abel Prize in 2012.

CS-448: Sublinear algorithms for big data analysis

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Related lectures (11)

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Graph Sketching: Connected ComponentsCS-448: Sublinear algorithms for big data analysis

Covers graph sketching and connected components in streaming models.

Prim's and Kruskal's AlgorithmsCS-250: Algorithms

Explores Prim's and Kruskal's algorithms for finding minimum spanning trees in a graph, covering their correctness, implementation, and analysis.