Using combinatorial maps for algorithms on graphs

Robert Cori
Author affiliations

Authors

  • Robert Cori Université de Bordeaux, Bordeaux, France

DOI:

https://doi.org/10.15625/1813-9663/37/3/16253

Keywords:

Graph algorithms, Topological embeddings, spanning trees Tutte polynomials.

Abstract

The aim of this paper is to come back to a data structure representation of graph by permutations. This originated in the years 1960-1970 by contributions due to J. Edmonds [7], A. Jacques [11], W. Tutte [22] in order to consider the embedding of a graph in a surface as a combinatorial object. Some algebraic developments where suggested in [4] and [12]. It was also used for implementation in different situation, like planarity testing by H. de Fraysseix and P. Rosenstiehl [6], computer vision by G. Damiand  and A. Dupas [5] or formal proofs by G. Gonthier [9].

Metrics

PDF views
8

Downloads

Published

27-09-2021

How to Cite

[1]
R. Cori, “Using combinatorial maps for algorithms on graphs”, J. Comput. Sci. Cybern., vol. 37, no. 3, p. 185–200, Sep. 2021.

Issue

Section

SPECIAL ISSUE DEDICATED TO THE MEMORY OF PROFESSOR PHAN DINH DIEU - PART A