Geodesic
Edge-Maximal Graphs on Surfaces
Canadian journal of mathematics, Tome 70 (2018) no. 4, pp. 925-942

Voir la notice de l'article provenant de la source Cambridge

DOI

We prove that for every surface $\Sigma $ of Euler genus $g$ , every edge-maximal embedding of a graph in $\Sigma $ is at most $O(g)$ edges short of a triangulation of $\Sigma $ . This provides the first answer to an open problem of Kainen (1974).
DOI : 10.4153/CJM-2017-028-0
Mots-clés : 05C10, graph, surface, embedding 
McDiarmid, Colin; Wood, David R. Edge-Maximal Graphs on Surfaces. Canadian journal of mathematics, Tome 70 (2018) no. 4, pp. 925-942. doi: 10.4153/CJM-2017-028-0
@article{10_4153_CJM_2017_028_0,
     author = {McDiarmid, Colin and Wood, David R.},
     title = {Edge-Maximal {Graphs} on {Surfaces}},
     journal = {Canadian journal of mathematics},
     pages = {925--942},
     year = {2018},
     volume = {70},
     number = {4},
     doi = {10.4153/CJM-2017-028-0},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-028-0/}
}
TY  - JOUR
AU  - McDiarmid, Colin
AU  - Wood, David R.
TI  - Edge-Maximal Graphs on Surfaces
JO  - Canadian journal of mathematics
PY  - 2018
SP  - 925
EP  - 942
VL  - 70
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-028-0/
DO  - 10.4153/CJM-2017-028-0
ID  - 10_4153_CJM_2017_028_0
ER  - 
%0 Journal Article
%A McDiarmid, Colin
%A Wood, David R.
%T Edge-Maximal Graphs on Surfaces
%J Canadian journal of mathematics
%D 2018
%P 925-942
%V 70
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-028-0/
%R 10.4153/CJM-2017-028-0
%F 10_4153_CJM_2017_028_0

Cité par Sources :