In a good drawing of a complete graph the vertices are drawn as distinct points in the plane, edges are drawn as non-self-intersecting continuous arcs connecting its two end points, but not passing through any other point representing a vertex. Moreover, any pair of edges intersects at most once, either in their interior or at a common endpoint, no tangencies are allowed and no three edges pass through a single crossing. These drawings are also called simple topological graphs.
A rotation system (of a good drawing of a complete graph) gives, for each vertex v of the graph, the circular ordering around v of all edges incident to v. In combinatorial mathematics, rotation systems were first used by Hefner in 1891 to encode embeddings of graphs onto orientable surfaces, determining its genus. In the plane (or equivalently on the sphere) the rotation system of a good drawing does not fully determine the drawing, but contains combinatorial information like all pairs of edges which intersect.
We present basic properties of these two concepts, as well as recent progress. This includes results on the number of realizable rotation systems, the crossing number of complete graphs (including the recent concept of shellability of a good drawing), relations to other systems like the order type of a point set, etc.
|Journal||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Publication status||Published - 2014|
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)