Complete Graph Drawings up to Triangle Mutations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2005

Complete Graph Drawings up to Triangle Mutations

Emeric Gioan


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 and versions

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



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 View
0 Download



Gmail Facebook X LinkedIn More