×

zbMATH — the first resource for mathematics

A large set of torus obstructions and how they were discovered. (English) Zbl 1380.05134
Summary: We outline the progress made so far on the search for the complete set of torus obstructions and also consider practical algorithms for torus embedding and their implementations. We present the set of obstructions that are known to-date and give a brief history of how these graphs were found. We also describe a nice algorithm for embedding graphs on the torus which we used to verify previous results and add to the set of torus obstructions. Although it is still exponential in the order of the graph, the algorithm presented here is relatively simple to describe and implement and fast-in-practice for small graphs. It parallels the popular quadratic planar embedding algorithm of G. Demoucron et al. [Rev. Franç. Rech. Opér. 8, No. 30, 33–47 (1964; Zbl 0128.17203)].

MSC:
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C83 Graph minors
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
Software:
SPOT
PDF BibTeX XML Cite
Full Text: Link
References:
[1] [1] Dan Archdeacon. A Kuratowski theorem for the projective plane. J. Graph Theory, 5(3):243-246, 1981. · Zbl 0464.05028
[2] [2] Dan Archdeacon and Phil Huneke. A Kuratowski theorem for nonorientable surfaces. J. Combin. Theory Ser. B, 46(2):173-231, 1989. · Zbl 0616.05034
[3] [3] Takao Asano. An approach to the subgraph homeomorphism problem. Theoret. Comput. Sci., 38(2-3):249-267, 1985. · Zbl 0572.68052
[4] [4] Joseph Battle, Frank Harary, Yukihiro Kodama, and J. W. T. Youngs. Additivity of the genus of a graph. Bull. Amer. Math. Soc., 68:565-568, 1962. · Zbl 0142.41501
[5] [5] R. Bodendiek and K. Wagner. Solution to K¨onig’s graph embedding problem. Math. Nachr., 140:251-272, 1989. the electronic journal of combinatorics 25(1) (2018), #P1.1615 · Zbl 0677.05018
[6] [6] Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using P Q-tree algorithms. J. Comput. System Sci., 13(3):335-379, 1976. Working Papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N. M., 1975). · Zbl 0367.68034
[7] [7] John Boyer and Wendy Myrvold.Stop minding your P’s and Q’s: a simplified O(n) planar embedding algorithm. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999), pages 140-146. ACM, New York, 1999. · Zbl 0938.68064
[8] [8] John M. Boyer and Wendy J. Myrvold. On the cutting edge: simplified O(n) planarity by edge addition. J. Graph Algorithms Appl., 8(3):241-273, 2004. · Zbl 1086.05067
[9] [9] J. Chambers. Hunting for torus obstructions. Master’s thesis, Department of Computer Science, University of Victoria, Victoria, B.C., 2002.
[10] [10] M. Chimani and K. Klein.Algorithm engineering: Concepts and practice.In T. Bartz-Beielstein, M. Chiarandini, L. Paquete, and M. Preuss, editors, Experimental Methods for the Analysis of Optimization Algorithms, pages 131-158. SpringerVerlag, 2010. · Zbl 1214.68478
[11] [11] H. de Fraysseix and P. Rosentiehl. A depth-first search characterization of planarity. Ann. Discrete Math., 13:75-80, 1982. · Zbl 0497.05026
[12] [12] G. Demoucron, Y. Malgrange, and R. Pertuiset. Graphes planaires. Revue Francaise Recherche Operationnelle, 8:33-47, 1964.
[13] [13] Andrei Gagarin and William Kocay. Embedding graphs containing K5-subdivisions. Ars Combin., 64:33-49, 2002. · Zbl 1073.05525
[14] [14] Andrei Gagarin and William Kocay. Embedding graphs containing K5-subdivisions on the torus. J. Combin. Math. Combin. Comput., 80:207-223, 2012. · Zbl 1242.05068
[15] [15] Andrei Gagarin, Wendy Myrvold, and John Chambers. The obstructions for toroidal graphs with no K3,3’s. Discrete Math., 309(11):3625-3631, 2009. · Zbl 1186.05041
[16] [16] Alan Gibbons. Algorithmic graph theory. Cambridge University Press, Cambridge, 1985.
[17] [17] Henry H. Glover, John P. Huneke, and Chin San Wang. 103 graphs that are irreducible for the projective plane. J. Combin. Theory Ser. B, 27(3):332-370, 1979. · Zbl 0352.05027
[18] [18] John Hopcroft and Robert Tarjan. Efficient planarity testing. J. Assoc. Comput. Mach., 21:549-568, 1974. · Zbl 0307.68025
[19] [19] M. Juvan. Algorithms and obstructions for embedding graphs in the torus. PhD thesis, University of Ljubljana, 1995. (in Slovene).
[20] [20] M. Juvan and B. Mohar. A simplified algorithm for embedding graphs in the torus. 2001 preprint. 10 pages.
[21] [21] Martin Juvan, Joˇze Marinˇcek, and Bojan Mohar. Embedding graphs in the torus in linear time. In Integer programming and combinatorial optimization (Copenhagen, 1995), volume 920 of Lecture Notes in Comput. Sci., pages 360-363. Springer, Berlin, 1995. the electronic journal of combinatorics 25(1) (2018), #P1.1616
[22] [22] W. Klotz. A constructive proof of Kuratowski’s theorem. Ars Combin., 28:51-54, 1989. · Zbl 0726.05036
[23] [23] K. Kuratowski. Sur le probl‘eme des courbes gauches en topologie. Fundamenta Mathematicae, 15:271-283, 1930. · JFM 56.1141.03
[24] [24] Bojan Mohar and Petr ˇSkoda. Obstructions of connectivity two for embedding graphs into the torus. Canad. J. Math., 66(6):1327-1357, 2014. · Zbl 1303.05040
[25] [25] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.
[26] [26] Wendy Myrvold and William Kocay. Errors in graph embedding algorithms. J. Comput. System Sci., 77(2):430-438, 2011. · Zbl 1213.05252
[27] [27] E. Neufeld. Practical toroidality testing. Master’s thesis, Department of Computer Science, University of Victoria, Victoria, B.C., 1993.
[28] [28] Eugene Neufeld and Wendy Myrvold. Practical toroidality testing. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), pages 574-580. ACM, New York, 1997. · Zbl 1321.05065
[29] [29] Neil Robertson and P. D. Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Combin. Theory Ser. B, 48(2):255-288, 1990. · Zbl 0719.05033
[30] [30] K. Wagner. ¨Uber eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114:570-590, 1937. · JFM 63.0550.01
[31] [31] Douglas B. West. Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996. · Zbl 0845.05001
[32] [32] S. G. Williamson. Embedding graphs in the plane—algorithmic aspects. Ann. Discrete Math., 6:349-384, 1980. Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978). · Zbl 0451.05021
[33] [33] S. G. Williamson. Depth-first search and Kuratowski subgraphs. J. Assoc. Comput. Mach., 31(4):681-693, 1984. · Zbl 0632.68063
[34] [34] J. Woodcock. A faster algorithm for torus embedding. Master’s thesis, Department of Computer Science, University of Victoria, Victoria, B.C., 2004. Available from http://dspace.library.uvic.ca:8080/handle/1828/130. the electronic journal of combinatorics 25(1) (2018), #P1.1617
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.