Complete Graph Drawings up to Triangle Mutations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete and Computational Geometry Année : 2022

Complete Graph Drawings up to Triangle Mutations

Emeric Gioan

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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 Consultations
91 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More