Geodesic
Obstructions of Connectivity Two for Embedding Graphs into the Torus
Canadian journal of mathematics, Tome 66 (2014) no. 6, pp. 1327-1357

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

The complete set of minimal obstructions for embedding graphs into the torus is still not determined. In this paper, we present all obstructions for the torus of connectivity 2. Furthermore, we describe the building blocks of obstructions of connectivity 2 for any orientable surface.
DOI : 10.4153/CJM-2014-025-x
Mots-clés : 05C10, 05C83, torus, obstruction, minor, connectivity 2 
Mohar, Bojan; Škoda, Petr. Obstructions of Connectivity Two for Embedding Graphs into the Torus. Canadian journal of mathematics, Tome 66 (2014) no. 6, pp. 1327-1357. doi: 10.4153/CJM-2014-025-x
@article{10_4153_CJM_2014_025_x,
     author = {Mohar, Bojan and \v{S}koda, Petr},
     title = {Obstructions of {Connectivity} {Two} for {Embedding} {Graphs} into the {Torus}},
     journal = {Canadian journal of mathematics},
     pages = {1327--1357},
     year = {2014},
     volume = {66},
     number = {6},
     doi = {10.4153/CJM-2014-025-x},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-025-x/}
}
TY  - JOUR
AU  - Mohar, Bojan
AU  - Škoda, Petr
TI  - Obstructions of Connectivity Two for Embedding Graphs into the Torus
JO  - Canadian journal of mathematics
PY  - 2014
SP  - 1327
EP  - 1357
VL  - 66
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-025-x/
DO  - 10.4153/CJM-2014-025-x
ID  - 10_4153_CJM_2014_025_x
ER  - 
%0 Journal Article
%A Mohar, Bojan
%A Škoda, Petr
%T Obstructions of Connectivity Two for Embedding Graphs into the Torus
%J Canadian journal of mathematics
%D 2014
%P 1327-1357
%V 66
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-025-x/
%R 10.4153/CJM-2014-025-x
%F 10_4153_CJM_2014_025_x

[1] [1] Battle, J., Harary, F., Kodama, Y., and Youngs, J.W. T., Additivity of the genus of a graph. Bull. Amer. Math. Soc. 68(1962), 565–568. Google Scholar | DOI

[2] [2] Chambers, J., Hunting for torus obstructions. Master's thesis, Deptartment of Computer Science, University of Victoria, 2002. Google Scholar

[3] [3] Decker, R.W., Glover, H. H., and Huneke, J. P., The genus of the 2-amalgamations of graphs. J.Graph Theory 5(1981), no. 1, 95–102. Google Scholar | DOI

[4] [4] Decker, R.W., Glover, H. H., and Huneke, J. P., Computing the genus of the 2-amalgamations of graphs. Combinatorica 5(1985), no. 4, 271–282. Google Scholar | DOI

[5] [5] Gagarin, A., Myrvold, W., and Chambers, J., The obstructions for toroidal graphs with no K3,3’s. Discrete Math. 309(2009), no. 11, 3625–3631. Google Scholar | DOI

[6] [6] Mohar, B. and Thomassen, C., Graphs on surfaces. Johns Hopkins Studies in Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001. Google Scholar

[7] [7] Mohar, B. and Škoda, P., Obstructions for two-vertex alternating embeddings of graphs in surfaces. . arxiv:1112.0800 Google Scholar

[8] [8] Neufeld, E. and Myrvold, W., Practical toroidality testing. In: Proceedings of the eigth annual ACM-SIAM symposium on discrete algorithms (New Orleans, LA, 1997), ACM, New York, 1997, pp. 574–580. Google Scholar

[9] [9] Robertson, N. and Seymour, P. D., Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Combin. Theory Ser B. 48(1990), no. 2, 255–288. Google Scholar | DOI

[10] [10] Stahl, S. and Beineke, L.W., Blocks and the nonorientable genus of graphs. J. Graph Theory 1(1977), no. 1, 75–78. Google Scholar | DOI

[11] Woodcock, J., A faster algorithm for torus embedding. . Master's thesis, Department of Computer Science, University of Victoria, 2007. Google Scholar

Cité par Sources :