Topological Inductive Constructions for Tight Surface Graphs

Springer Science and Business Media LLC - Tập 38 - Trang 1-31 - 2022
James Cruickshank1, Derek Kitson2, Stephen C. Power3, Qays Shakir4
1School of Mathematical and Statistical Sciences, University of Galway, Galway, Ireland
2Department of Mathematics and Computer Studies, Mary Immaculate College, Thurles, Ireland
3Department of Mathematics and Statistics, Lancaster University, Lancaster, UK
4Technical College of Management, Baghdad, Iraq

Tóm tắt

We investigate properties of sparse and tight surface graphs. In particular we derive topological inductive constructions for $$(2,2)$$ -tight surface graphs in the case of the sphere, the plane, the twice punctured sphere and the torus. In the case of the torus we identify all 116 irreducible base graphs and provide a geometric application involving contact graphs of configurations of circular arcs.

Tài liệu tham khảo

Alam, Md.J., Eppstein, D., Kaufmann, M., Kobourov, S.G., Pupyrev, S., Schulz, A., Ueckerdt, T.: Contact graphs of circular arcs, Algorithms and data structures, Lecture Notes in Comput. Sci., 9214, Springer, Cham, pp. 1–13 (2015) Barnette, D.W., Edelson, A.L.: All \(2\)-manifolds have finitely many minimal triangulations. Israel J. Math. 67(1), 123–128 (1989). https://doi.org/10.1007/BF02764905. (0021-2172) Cruickshank, J., Shakir, Q.: Software for computing irreducible \((2,2)\)-tight torus graphs (2021). https://doi.org/10.5281/zenodo.4579832 Cruickshank, J., Kitson, D., Power, S.C.: The generic rigidity of triangulated spheres with blocks and holes. J. Combin. Theory Ser. B 122(550–577), 0095–8956 (2017) Cruickshank, J., Kitson, D., Power, S.C.: The rigidity of a partially triangulated torus. Proc. Lond. Math. Soc. (3) 118(5), 1277–1304 (2019). https://doi.org/10.1112/plms.12215. (0024-6115) de Fraysseix, H., Ossona de Mendez, P.: Representations by contact and intersection of segments. Algorithmica 47(4), 453–463 (2007). https://doi.org/10.1007/s00453-006-0157-x. (0178-4617) Developers. The Sage, Sagemath, the Sage Mathematics Software System (Version 8.1) (2017). https://www.sagemath.org Farb, B., Margalit, D.: A Primer on Mapping Class Groups, Princeton Mathematical Series, vol. 49. Princeton University Press, Princeton (2012).. (xiv+472, 978-0-691-14794-9) Fekete, Z., Jordán, T., Whiteley, W.: An inductive construction for plane Laman graphs via vertex splitting, Algorithms–ESA, : Lecture Notes in Computer Science 3221, vol. 2004. Springer, Berlin, 299–310 (2004) Gonçalves, D., Isenmann, L., Pennarun, C.: Planar graphs as L-intersection or L-contact graphs, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, pp. 172–184 (2018). https://doi.org/10.1137/1.9781611975031.12, Haas, R., Orden, D., Rote, G., Santos, F., Servatius, B., Servatius, H., Souvaine, D., Streinu, I., Whiteley, W.: Planar minimally rigid graphs and pseudo-triangulations. Comput. Geom. 31(1–2), 31–61 (2005). https://doi.org/10.1016/j.comgeo.2004.07.003. (0925-7721) Hliněný, P.: Classes and recognition of curve contact graphs. J. Combin. Theory Ser. B 74(1), 87–103 (1998). https://doi.org/10.1006/jctb.1998.1846. (0095-8956) Jacobs, D.J., Hendrickson, B.: An algorithm for two-dimensional rigidity percolation: the pebble game. J. Comput. Phys. 137(2), 346–365 (1997). https://doi.org/10.1006/jcph.1997.5809. (0021-9991) Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Sächs. Akad. Wiss. Leipzig Math.-Phys. 88, 141–164 (1936). (German) Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discrete Math. 308(8), 1425–1437 (2008). https://doi.org/10.1016/j.disc.2007.07.104. (0012-365X) Mohar, B., Thomassen, C.: Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001) Nakamoto, A.: Irreducible quadrangulations of the torus. J. Combin. Theory Ser. B 67(2), 183–201 (1996). https://doi.org/10.1006/jctb.1996.0040. (0095-8956) Nakamoto, A., Ota, K.: Note on irreducible triangulations of surfaces. J. Graph Theory 20(2), 227–233 (1995). https://doi.org/10.1002/jgt.3190200211. (0364-9024) Nixon, A., Owen, J.C., Power, S.C.: Rigidity of frameworks supported on surfaces. SIAM J. Discrete Math. 26(4), 1733–1757 (2012). https://doi.org/10.1137/110848852. (0895-4801) Shakir, Q.: Sparse Topological Graphs, Ph.D. Thesis. National University of Ireland Galway (2019)