Complete Graph Drawings up to Triangle Mutations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete and Computational Geometry Year : 2022

Complete Graph Drawings up to Triangle Mutations

Emeric Gioan


The main result of the paper can be stated in the following way: a complete graph drawing in the sphere, where two edges have at most one common point, which is either a crossing or a common endpoint, and no three edges share a crossing, is determined by the circular ordering of edges at each vertex, or equivalently by the set of pairs of edges that cross, up to homeomorphism and a sequence of triangle mutations. A triangle mutation (or switch, or flip) consists in passing an edge across the intersection of two other edges, assuming the three edges cross each other and the region delimited by the three edges has an empty intersection with the drawing. Equivalently, the result holds for a drawing in the plane assuming the drawing is given with a pair of edges indicating where the unbounded region is. The proof is constructive, based on an inductive algorithm that adds vertices and their incident edges one by one (actually yielding an extra property for the sequence of triangle mutations). This result generalizes Ringel's theorem on uniform pseudoline arrangements (or rank 3 uniform oriented matroids) to complete graph drawings. We also apply this result to plane projections (or visualizations) of a geometric spatial complete graph, in terms of the rank 4 uniform oriented matroid defined by its vertices. Independently, we prove that, for a complete graph drawing, the set of pairs of edges that cross determine, by first order logic formulas, the circular ordering of edges at each vertex, as well as further information.
Fichier principal
Vignette du fichier
Gioan - Complete graph drawings up to triangle mutations - SOURCE FOR DCG.pdf (475.83 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03371693 , version 1 (08-10-2021)



Emeric Gioan. Complete Graph Drawings up to Triangle Mutations. Discrete and Computational Geometry, 2022, 67, pp.985-1022. ⟨10.1007/s00454-021-00339-8⟩. ⟨lirmm-03371693⟩
47 View
96 Download



Gmail Mastodon Facebook X LinkedIn More