Complete Graph Drawings up to Triangle Mutations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

Complete Graph Drawings up to Triangle Mutations

Emeric Gioan

Résumé

The logical structure we introduce here to describe a (topological) graph drawing, called subsketch, is intermediate between the map (determining the drawing when it is planar), and the sketch introduced by Courcelle (determining the drawing in general but assuming we know the order of the crossings on each edge). For a complete graph drawing, the subsketch is determined, through first order logic formulas, by the size, a corner of the drawing and the crossings of the edges. We prove, constructively, that two complete graph drawings have the same subsketch if and only if they can be transformed into each other by a sequence of triangle mutations - or triangle switches. This construction generalizes Ringel's theorem on uniform pseudoline arrangements. Moreover, it applies to plane projections of spatial graphs encoded by rank 4 uniform oriented matroids.

Dates et versions

lirmm-00106049 , version 1 (13-10-2006)

Identifiants

Citer

Emeric Gioan. Complete Graph Drawings up to Triangle Mutations. 31st International Workshop on Graph-Theoretical Concepts in Computer Science (WG 2005), Jun 2005, Metz, France. pp.139-150, ⟨10.1007/11604686_13⟩. ⟨lirmm-00106049⟩
167 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More