Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata
Contributor : Christine Carvalho de Matos <>
Submitted on : Friday, October 13, 2006 - 10:23:00 AM
Last modification on : Monday, November 30, 2020 - 5:32:02 PM

Links full text




Emeric Gioan. Complete Graph Drawings up to Triangle Mutations. WG'05: 31st International Workshop on Graph-Theoretical Concepts in Computer Science, Jun 2005, Metz, France. pp.139-150, ⟨10.1007/11604686_1⟩. ⟨lirmm-00106049⟩



Record views