Professional page of Emeric Gioan

Searcher CNRS
Laboratory: LIRMM
Address: LIRMM (UMR 5506 - CC 477), 161 rue Ada 34095 Montpellier Cedex 5 - France
Group: AlGCo (Algorithms, Graphs and Combinatorics)
Phone: 0 (033) 4 67 41 86 76
Fax: 0 (033) 4 67 41 85 00

Last update of this page : in progress.

I work in combinatorics, at the meeting between mathematics and computer science.

Research topics
Publications
More ressources are available IN FRENCH

Research topics
- Matroid, oriented matroid, and hyperplane arrangement theories.
  
  Some presentations of matroid and oriented matroid theories are available IN FRENCH: here.
  
  Note. Since matroids and oriented matroids generalize space cycles of graphs, results in these theories applie in particular to graphs.
  - Tutte polynomial.
    This polynomial, coming from graph theory (1950') and extending the chromatic polynomial to two dual variables, generalizes very well to matroids and contains a lot of structural and enumerative information. This object is underlying in several of my research: [J4] (polynomial complexity of its evaluation at a point left partially open in Jaeger's paper), [J5][J6] (link with edge reversing dynamical systems) and overall those below.
  - The (attr)active mapping of ordered oriented matroids.
    With Michel Las Vergnas, we have defined and studied a general and natural mapping which associates an ordered oriented matroid with one of its bases, and which induces an activity (state models of the Tutte polynomial) preserving correspondence between bases and reorientations of a given ordered oriented matroid. Several bijections, called active bijections appear as refinements or particular cases in several contexts. It uses on the one hand duality and decompositions of activities, and extends on the other hand the combinatorial formulation of linear programming. For a more precise abstract taken from my thesis, click here . See [C4] for a recent sum up of the whole construction in 7 pages, [C8] for a recent sum up of the linear programming construction, [C2] for an older but more complete survey (except linear programming). For the detailed constructions, see [J7][R2-4], and also [J1] in the uniform case, [J2][R1] in the graphical case, et [J3] in the supersolvable case. These constructions have been described or sketched in french in my thesis [T].
  top
- Graph decompositions and algorithms.
  My research on this topic is actually part of the French ANR Grant "Graph Decompositions and Algorithms" (GRAAL).
  - Split decomposition.
    With Christophe Paul, we work on reformulations, applications, and generalizations of the split decomposition of a graph introduced by Cunningham. We introduce a new representation of it in terms of graph-labeled trees, capturing also the modular decomposition. In this setting, we obtained an optimal (linear) dynamic recognition algorithm for distance hereditary graphs, for vertex/edge insertion/deletion, as well as an intersection model for these graphs (answering an open question by Jeremy Spinrad), and similar algorithm for subclasses (cographs and 3-leaf power graphs). See [C5][J8].
  - Enumeration and structure of orientations of a graph.
    The oriented matroid point of view using no vertex, and an intrinsic notion of duality (even for non planar graphs) helps to make appear original structural and enumerative properties fo directed graphs. For example, one can use the decomposition in acyclic and totally cyclic (or strongly connected) minors. This decomposition can be refined to decompose orientations of an ordered graph into bipolar orientations. This generalizes the decomposition of acyclic orientations into components for a linear ordering of the vertices by Viennot, studied for example by Bodo Lass. And a similar decomposition exists for trees. Thus, the active correspondence presented above, studied with Michel Las Vergnas, gives in particular active bijections, linked to the Tutte polynomial, between spanning trees and orientations of an ordered graph, or also between (no broken circuit) edge-subsets and (acyclic) orientations, see [J2][C4].
  top
- Combinatorial encoding of graph drawings, spatial graphs and 3D objects.
  - Logical structure of graph drawings.
    I have studied a logical structure, intermediate between the planar map and the 'sketch' used by Bruno Courcelle, axiomatizing complete graph drawings up to triangle mutations (or triangle switchs). This extends Ringel's theorem from pseudoline arrangements, and applies in particular to projections of spatial graphs encoded with oriented matroids. See [C3].
  - 3D objects and oriented matroids.
    I work, notably with Gérard Subsol and Kevin Sol, on some properties of 3D objects encoded by their associated oriented matroids. An example is given by the previous subject.
  top
- Miscellaneous.
  - Discrete dynamical systems on graphs (sandpile model, chip firing game, edge firing game...).
    I have studied configurations of discrete dynamical systems of directed graphs (and regular matroids) through a new principle, which is generalizing reversing sinks to self-dual cycle an cocycle reversings, making appear certain structural and enumerative properties for htese systems, see [J5][J6]. The point of view is similar to the point of view presented above on directed graph decompositions and linked again to the Tutte polynomial polynomial. See also recent works by Olivier Bernardi, notably for a nice answer to a bijective question that I asked in [J5] on a link with the sandpile model. These systems were born to try to modelize complex phenomenon with cellular automata. Indeed we observe similarities with the behaviour of physical phenomenons as sandpiles, crumbligns, earthquakes... For more information, see for example the site of Dominique Rossin.
  - Mapping computation with no memory.
    With Serge Burckel, who initiated this research in his past works, and with Emmanuel Thomé, we worked on techniques of which principle is to implement a mapping on a finite product set by modifying coordinates one by one, without using other variables than the input ones. We call in situ computation this way of computing a mapping. We prove that it is always possible with a number of assignments linear in the exponent. See [R5][C7] for the detailed constructions, or [C6] for a short note intended for an electronic scientist audience.
  top
Publications
- Current
  - [R9] With Kevin Sol and Gérard Subsol. Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices.
    Submitted. See [C9] for a preliminary conference version.
    Thematic link: 3D shapes.
  - [R8] With Christophe Crespelle, Christophe Paul. Dynamic circle graph recognition.
    In preparation. Thematic links: split decomposition.
  - [R7] With Christophe Paul, Marc Tedder, Derek Corneil. Circle Graph Recognition in Time O(n+m).\alpha(n+m).
    Submitted. Download: in arXiv. Thematic links: split decomposition.
  - [R6] With Christophe Paul, Marc Tedder, Derek Corneil. Practical and Efficient Split Decomposition via Graph-Labelled Trees.
    Submitted. Download: in arXiv. Thematic links: split decomposition.
  - [R5] With Serge Burckel and Emmanuel Thomé. Mapping computation with no memory, and Rearrangeable Nonblocking Multicast Networks based on Concatenation of Butterflies.
    Submitted. See [C7] for a preliminary conference version of this paper. See [C6] for a short note intended for an electronic scientist audience. See [B] for a patent on these techniques.
    Thematic links: in situ computation .
  - [R2-4] With Michel Las Vergnas. The active bijection in graphs, hyperplane arrangements, and oriented matroids.
    - 2. Decomposition of activities.
    - 3. Linear programming construction of fully optimal bases.
    - 4. Deletion/contraction constructions and universality.
    Series of papers in preparation. See [J7] for n°1 in the series. See [C4] for a recent sum up of the whole set in 7 pages. See [C8] for an extended abstract of n°3.
    Thematic links: Tutte polynomial , active bijections.
  - [R1] With Michel Las Vergnas. Activity preserving bijections between spanning trees and orientations in graphs 2.
    In preparation. Sequel of [J2]: complements and synthesis of recent results applied to the graphical case.
    Liens thématiques : polynôme de Tutte , bijections actives.
  top
- Journals
  - [J8] With Christophe Paul. Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs.
    Submitted. See [C5] for a short and very partial conference version.
    Abstract. Download: in arXiv. Thematic links: split decomposition.
  - [J7] With Michel Las Vergnas. The active bijection in graphs, hyperplane arrangements, and oriented matroids - 1 - The fully optimal basis of a bounded region.
    European Journal of Combinatorics, available online, in press (2009).
    Abstract. Download: ps pdf. Thematic links: Tutte polynomial , active bijections.
  - [J6] Circuit-cocircuit reversing systems in regular matroids.
    (Special issue Workshop on Tutte polynomials, Barcelona 2005) Annals of Combinatorics, Vol. 12, pp. 171-182, (2008).
    Download: ps pdf. Thematic links: Tutte polynomial , dynamical systems.
  - [J5] Enumerating degree sequences in digraphs and a cycle-cocycle reversing system.
    European Journal of Combinatorics 28 (4): 1351--1366 (2007).
    Download: ps pdf. Thematic links: Tutte polynomial , dynamical systems.
  - [J4] With Michel Las Vergnas. On the evaluation at (j,j²) of the Tutte polynomial of a ternary matroid.
    Journal of Algebraic Combinatorics 25: 1-6 (2007).
    Download: ps pdf. Thematic links: Tutte polynomial .
  - [J3] With Michel Las Vergnas. The active bijection between regions and simplices in supersolvable arrangements of hyperplanes.
    (Stanley Festschrift) Electronic Journal of Combinatorics 11(2) #R30, 39p (2006).
    Download: ps pdf. Thematic links: Tutte polynomial , active bijections.
  - [J2] With Michel Las Vergnas. Activity preserving bijections between spanning trees and orientations in graphs.
    (Special issue FPSAC 2002) Discrete Mathematics 298: 169--188 (2005).
    Download: ps pdf. Thematic links: Tutte polynomial , active bijections.
  - [J1] With Michel Las Vergnas. Bases, reorientations, and linear programming, in uniform and rank 3 oriented matroids.
    (Special issue Workshop on Tutte polynomials, Barcelona 2001) Advances in Applied Mathematics 32, 212--238 (2004)
    Download: ps pdf. ERRATA : ps pdf. Thematic links: Tutte polynomial , active bijections.
  top
- Conferences
  - [C9] With Kevin Sol and Gérard Subsol. Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices.
    Proceedings CCCG'2011, 6p. (2011). Version without proofs of [R9].
    Download: pdf. Thematic links: 3D shapes.
  - [C8] - Note/Résumé - With Michel Las Vergnas. A linear programming construction of fully optimal bases in graphs and hyperplane arrangements.
    Proceedings EuroComb 2009 (Bordeaux), Electronic Notes in Discrete Mathematics, 34, pp. 307-311, (2009).
    Abstract. Download: ps pdf. Liens thématiques : Tutte polynomial, active bijections.
  - [C7] With Serge Burckel and Emmanuel Thomé. Mapping computation with no memory
    Proceedings Unconventional Computation 2009 (Açores), LNCS 5715, pp. 85-97 (2009)
    Abstract. Donwload: ps pdf. Thematic links: in situ computation.
  - [C6] With Serge Burckel. In situ design of register operations.
    Proceedings of ISVLSI 2008, IEEE Computer Society Annual Symposium on Very-Large-Scale Integration (Montpellier).
    Download: ps pdf. Thematic links: in situ computation.
  - [C5] With Christophe Paul. Dynamic distance hereditary graphs using split decomposition.
    Proceedings ISAAC 2007 (Sendai), LNCS 4835, pp 41--51 (2007).
    Download: ps pdf. Slides of the talk: ps pdf. Thematic links: split decomposition.
  - [C4] - Note/Sum up - With Michel Las Vergnas. Fully optimal bases and the active bijection in graphs, hyperplane arrangements, and oriented matroids.
    Proceedings EuroComb 2007 (Sevilla), Electronic Notes in Discrete Mathematics 29, pp 365--371 (2007).
    Download: ps pdf. Slides of the talk: ps pdf. Thematic links: Tutte polynomial , active bijections.
  - [C3] Complete graph drawings up to triangle mutations.
    Proceedings WG 2005 (Metz), LNCS 3787, pp139-150 (2005)
    Download: ps pdf. Slides of a general talk on the subject given at CSL 06: ps pdf. Thematic links: graph drawing.
  - [C2] - Survey - With Michel Las Vergnas. On a natural correspondence between bases and reorientations, related to the Tutte polynomial and linear programming, in graphs, hyperplane arrangements, and oriented matroids.
    Proceedings FPSAC 2003 (Linköping).
    Download: ps pdf. Slides of the talk: ps pdf. Thematic links: Tutte polynomial , active bijections.
  - [C1] With Michel Las Vergnas. Activity preserving bijections between spanning trees and orientations in graphs.
    Proceedings FPSAC 2002 (Melbourne).
    This obsolete paper is a truncated version of [J2].
  top
- Miscellaneous
  - Patent
    [B] With Serge Burckel and the Université de la Réunion. Implémentation de calculs pour processeurs.
    INPI number : 07 05152. Deposit date: 2007 July 17th. Publication date: 2011 March 25th.
    Thematic links: in situ computation .
    
    haut de page
  - Abstracts (conferences without extended proceedings)
    - [A2] With K. Sol, G. Subsol, Y.Heuzé, J. Richtsmeier, J. Braga, F. Thackeray. A new 3D morphometric method based on a combinatorial encoding of 3D point confguration: application to skull anatomy for clinical research and physical antropology.
      Poster: 80th annual meeting of the American Association of physical antropologists (Minneapolis, USA, April 12-16, 2011). Abstract: American Journal of Physical Antropology 144 (S52) (2011), 280
      Thematic links: 3D shapes.
    - [A1] With K. Sol, G. Subsol, J. Braga, J. Treil. Une nouvelle méthode de morphométrie 3D par codage combinatoire de confgurations de points 3D: application à l'anatomie du crâne.
      1836èmes Journées de la Societé d'Anthropologie de Paris (26-28 janvier 2011).
      Thematic links: 3D shapes.
    top
  - Thesis IN FRENCH
    [T] Natural correspondence between bases and reorientations of oriented matroids
    Specality: computer science and discrete mathematics (december 18, 2002).
    Thesis of the University Bordeaux 1 France, codirected by Bruno Courcelle and Michel Las Vergnas.
    Download: ps.zip (702 Ko) pdf.zip (1027 Ko). Thematic links: Tutte polynomial , active bijections.
    
    Abstract: click here. Game on pseudolines induced by a particular case in french (Recreation): ps pdf
    
    Note. Papers [J1], [J2] and [J3] describe respectively particular cases 6.2, 6.1 + 6.4, and 6.3 from chapter 6, and bring some new results. The series of papers [R1-3] n°1, n°2, n°4 describe respectively chapters 3, 2, 1 + 4, and reformulate of deepen some points. Paper n°3 develops precisely a sketch from chapter 3. Paper [C2] is a genreal detailed overview of the whole construction (except optimization). And paper [C4] is a recent sum up describing the essential of the wholoe constructions.
top

Professional page of Emeric Gioan

Research topics

Publications

Abstracts (conferences without extended proceedings)