Generating polyhedral quadrangulations of the projective plane. (English) Zbl 1433.05090
Summary: We determine the 26 families of irreducible polyhedral quadrangulations of the projective plane under three reductions called a face-contraction, a 4-cycle removal and a \(2_3\)-path shrink, which were first given by V. Batagelj [Discrete Math. 78, No. 1–2, 45–53 (1989; Zbl 0694.05028)]. Every polyhedral quadrangulation of the projective plane can be obtained from one of them by a sequence of the inverse operations of the reductions.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 51A05 | General theory of linear incidence geometry and projective geometries |
Citations:
Zbl 0694.05028References:
| [1] | D. Archdeacon, J. Hutchinson, A. Nakamoto, S. Negam and K. Ota, Chromatic numbers of quadrangulations on closed surfaces,J. Graph Theory37(2001), 100-114, doi:10.1002/jgt. 1005. · Zbl 0979.05034 |
| [2] | V. Batagelj, An inductive definition of the class of3-connected quadrangulations of the plane, Discrete Math.78(1989), 45-53, doi:10.1016/0012-365x(89)90159-3. · Zbl 0694.05028 |
| [3] | G. Brinkmann, S. Greenberg, C. Greenhill, B. D. McKay, R. Thomas and P. Wollan, Generation of simple quadrangulations of the sphere,Discrete Math.305(2005), 33-54, doi:10.1016/j. disc.2005.10.005. · Zbl 1078.05023 |
| [4] | H. J. Broersma, A. J. W. Duijvestijn and F. G¨obel, Generating all3-connected4-regular planar graphs from the octahedron graph,J. Graph Theory17(1993), 613-620, doi:10.1002/jgt. 3190170508. · Zbl 0781.05047 |
| [5] | P. Eades, S.-H. Hong, N. Katoh, G. Liotta, P. Schweitzer and Y. Suzuki, A linear time algorithm for testing maximal1-planarity of graphs with a rotation system,Theoret. Comput. Sci.513 (2013), 65-76, doi:10.1016/j.tcs.2013.09.029. · Zbl 1407.68354 |
| [6] | D. Hud´ak, T. Madaras and Y. Suzuki, On properties of maximal1-planar graphs,Discuss. Math. Graph Theory32(2012), 737-747, doi:10.7151/dmgt.1639. · Zbl 1293.05065 |
| [7] | J. P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided,J. Comb. Theory Ser. B65(1995), 139-155, doi:10.1006/jctb.1995.1047. · Zbl 0828.05029 |
| [8] | W. Liu and Y. Chen, Polyhedral embeddings of snarks with arbitrary nonorientable genera, Electron. J. Combin.19(2012), #P14 (6 pages),https://www.combinatorics.org/ ojs/index.php/eljc/article/view/v19i3p14. · Zbl 1252.05044 |
| [9] | B. Mohar, Existence of polyhedral embeddings of graphs,Combinatorica21(2001), 395-401, doi:10.1007/s004930100003. · Zbl 0989.05024 |
| [10] | B. Mohar and N. Robertson, Flexibility of polyhedral embeddings of graphs in surfaces,J. Comb. Theory Ser. B83(2001), 38-57, doi:10.1006/jctb.2001.2036. · Zbl 1024.05023 |
| [11] | B. Mohar and A. Vodopivec, On polyhedral embeddings of cubic graphs,Combin. Probab. Comput.15(2006), 877-893, doi:10.1017/s0963548306007607. · Zbl 1108.05033 |
| [12] | T. Nagasawa, K. Noguchi and Y. Suzuki, No optimal1-planar graph triangulates any nonorientable closed surface,J. Graph Theory89(2018), 350-360, doi:10.1002/jgt.22255. · Zbl 1402.05049 |
| [13] | M. Nagashima, A. Nakamoto, S. Negami and Y. Suzuki, Generating3-connected quadrangulations on surfaces,Ars Combin.116(2014), 371-384. · Zbl 1340.05050 |
| [14] | A. Nakamoto, Irreducible quadrangulations of the Klein bottle,Yokohama Math. J.43(1995), 125-139,http://hdl.handle.net/10131/5655. · Zbl 0857.05025 |
| [15] | A. Nakamoto, Irreducible quadrangulations of the torus,J. Comb. Theory Ser. B67(1996), 183-201, doi:10.1006/jctb.1996.0040. · Zbl 0857.05023 |
| [16] | A. Nakamoto,Triangulations and Quadrangulations on Surfaces, Ph.D. thesis, Keio University, Japan, 1996. · Zbl 0857.05024 |
| [17] | A. Nakamoto, Generating quadrangulations of surfaces with minimum degree at least3,J. Graph Theory30(1999), 223-234, doi:10.1002/(sici)1097-0118(199903)30:3h223::aid-jgt7i 3.3.co;2-d. · Zbl 0924.05018 |
| [18] | A. Nakamoto and K. Ota, Note on irreducible triangulations of surfaces,J. Graph Theory20 (1995), 227-233, doi:10.1002/jgt.3190200211. · Zbl 0834.05021 |
| [19] | A. Nakamoto and Y. Suzuki, Diagonal slides and rotations in quadrangulations on the sphere,Yokohama Math. J.55(2010), 105-112,http://hdl.handle.net/10131/ 00011358. · Zbl 1208.52014 |
| [20] | S. Negami and A. Nakamoto, Diagonal transformations of graphs on closed surfaces,Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem.40(1993), 71-97. |
| [21] | K. Noguchi and Y. Suzuki, Relationship among triangulations, quadrangulations and optimal 1-planar graphs,Graphs Combin.31(2015), 1965-1972, doi:10.1007/s00373-015-1568-8. · Zbl 1329.05088 |
| [22] | N. Robertson and R. Vitray, Representativity of surface embeddings, in: B. Korte, L. Lov´asz, H. J. Pr¨omel and A. Schrijver (eds.),Paths, Flows, and VLSI-Layout, Springer, Berlin, volume 9 ofAlgorithms and Combinatorics, 1990 pp. 293-328, papers from the meeting held at the University of Bonn, Bonn, June 20 - July 1, 1988. · Zbl 0735.05032 |
| [23] | Y. Suzuki, Optimal1-planar graphs which triangulate other surfaces,Discrete Math.310 (2010), 6-11, doi:10.1016/j.disc.2009.07.016. · Zbl 1188.05056 |
| [24] | Y. Suzuki, Re-embeddings of maximum1-planar graphs,SIAM J. Discrete Math.24(2010), 1527-1540, doi:10.1137/090746835. · Zbl 1221.05099 |
| [25] | Y. Suzuki, Cube-contractions in3-connected quadrangulations,Ars Math. Contemp.10(2016), 281-290, doi:10.26493/1855-3974.552.bf3. · Zbl 1347.05047 |
| [26] | Y. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
