Topological Inductive Constructions for Tight Surface Graphs
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)