Geodesic
Map genus, forbidden maps, and monadic second-order logic
The electronic journal of combinatorics, Tome 9 (2002)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A map is a graph equipped with a circular order of edges around each vertex. These circular orders represent local planar embeddings. The genus of a map is the minimal genus of an orientable surface in which it can be embedded. The maps of genus at most $g$ are characterized by finitely many forbidden maps, relatively to an appropriate ordering related to the minor ordering of graphs. This yields a "noninformative" characterization of these maps, that is expressible in monadic second-order logic. We give another one, which is more informative in the sense that it specifies the relevant surface embedding, in addition to stating its existence.
DOI : 10.37236/1656
Classification : 05C10, 03B70 
@article{10_37236_1656,
     author = {B. Courcelle and V. Dussaux},
     title = {Map genus, forbidden maps, and monadic second-order logic},
     journal = {The electronic journal of combinatorics},
     year = {2002},
     volume = {9},
     doi = {10.37236/1656},
     zbl = {1016.05026},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1656/}
}
TY  - JOUR
AU  - B. Courcelle
AU  - V. Dussaux
TI  - Map genus, forbidden maps, and monadic second-order logic
JO  - The electronic journal of combinatorics
PY  - 2002
VL  - 9
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1656/
DO  - 10.37236/1656
ID  - 10_37236_1656
ER  - 
%0 Journal Article
%A B. Courcelle
%A V. Dussaux
%T Map genus, forbidden maps, and monadic second-order logic
%J The electronic journal of combinatorics
%D 2002
%V 9
%U http://geodesic.mathdoc.fr/articles/10.37236/1656/
%R 10.37236/1656
%F 10_37236_1656
B. Courcelle; V. Dussaux. Map genus, forbidden maps, and monadic second-order logic. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1656

Cité par Sources :