TY - JOUR

T1 - Good drawings and rotation systems of complete graphs

AU - Aichholzer, Oswin

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2014.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Discrete and Computational Geometry

UR - http://www.scopus.com/inward/record.url?scp=84915755782&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84915755782

SN - 0302-9743

VL - 8871

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -