Complete Graph Drawings up to Triangle Mutations

Emeric Gioan 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Communication dans un congrès
WG'05: 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2005, Metz, France. LNCS (3787), pp.139-150, 2005, 〈10.1007/11604686_13〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00154522
Contributeur : Emeric Gioan <>
Soumis le : jeudi 14 juin 2007 - 00:00:52
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Emeric Gioan. Complete Graph Drawings up to Triangle Mutations. WG'05: 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2005, Metz, France. LNCS (3787), pp.139-150, 2005, 〈10.1007/11604686_13〉. 〈lirmm-00154522〉

Partager

Métriques

Consultations de la notice

101