{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:26Z","timestamp":1747173446807,"version":"3.40.5"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"content-version":"unspecified","delay-in-days":210,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a plane graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline1.png\"\/><jats:tex-math>\n$G=(V,E)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, a <jats:italic>Petrie tour<\/jats:italic> of <jats:italic>G<\/jats:italic> is a tour <jats:italic>P<\/jats:italic> of <jats:italic>G<\/jats:italic> that alternately turns left and right at each step. A <jats:italic>Petrie tour partition<\/jats:italic> of <jats:italic>G<\/jats:italic> is a collection <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline2.png\"\/><jats:tex-math>\n${\\mathscr P}=\\{P_1,\\ldots,P_q\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of Petrie tours so that each edge of <jats:italic>G<\/jats:italic> is in exactly one tour <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline3.png\"\/><jats:tex-math>\n$P_i \\in {\\mathscr P}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. A Petrie tour <jats:italic>P<\/jats:italic> is called a Petrie cycle if all its vertices are distinct. A <jats:italic>Petrie cycle partition<\/jats:italic> of <jats:italic>G<\/jats:italic> is a collection <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline4.png\"\/><jats:tex-math>\n${\\mathscr C}=\\{C_1,\\ldots,C_p\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of Petrie cycles so that each vertex of <jats:italic>G<\/jats:italic> is in exactly one cycle <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline5.png\"\/><jats:tex-math>\n$C_i \\in {\\mathscr C}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In this paper, we study the properties of 3-regular plane graphs that have Petrie cycle partitions and 4-regular plane multi-graphs that have Petrie tour partitions. Given a 4-regular plane multi-graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline6.png\"\/><jats:tex-math>\n$G=(V,E)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, a <jats:italic>3-regularization<\/jats:italic> of <jats:italic>G<\/jats:italic> is a 3-regular plane graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline7.png\"\/><jats:tex-math>\n$G_3$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> obtained from <jats:italic>G<\/jats:italic> by splitting every vertex <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129522000238_inline8.png\"\/><jats:tex-math>\n$v\\in V$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> into two degree-3 vertices. <jats:italic>G<\/jats:italic> is called <jats:italic>Petrie partitionable<\/jats:italic> if it has a 3-regularization that has a Petrie cycle partition. The general version of this problem is motivated by a data compression method, <jats:italic>tristrip<\/jats:italic>, used in computer graphics. In this paper, we present a simple characterization of Petrie partitionable graphs and show that the problem of determining if <jats:italic>G<\/jats:italic> is Petrie partitionable is NP-complete.<\/jats:p>","DOI":"10.1017\/s0960129522000238","type":"journal-article","created":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T11:37:48Z","timestamp":1661859468000},"page":"240-256","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["On Petrie cycle and Petrie tour partitions of 3- and 4-regular plane graphs"],"prefix":"10.1017","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3904-0478","authenticated-orcid":false,"given":"Xin","family":"He","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huaming","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yijie","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,8,30]]},"reference":[{"volume-title":"Graph Theory with Applications","year":"1979","author":"Bondy","key":"S0960129522000238_ref4"},{"key":"S0960129522000238_ref9","first-page":"57","article-title":"On an eberhard-type problem in cubic polyhedral graphs having petrie and hamiltonian cycles","volume":"18","author":"Ivan\u010do","year":"1999","journal-title":"Tatra Mountains Mathematical Publications"},{"key":"S0960129522000238_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"S0960129522000238_ref13","unstructured":"Porcu, M. B. and Scateni, R. (2003). An interactive strpification algorithm based on dual graph operations. In: Eurographics."},{"key":"S0960129522000238_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050308"},{"key":"S0960129522000238_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/11550822_32"},{"key":"S0960129522000238_ref12","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1987.12000694"},{"key":"S0960129522000238_ref7","unstructured":"Fouquet, J. L. and Jolivet, J. L. (1982). Strong edge-coloring of cubic planar graphs. In: Adrian Bondy, J. and Murty, U. S. R. (eds.) Progress in graph theory. Proceedings of the conference on combinatorics held at the University of Waterloo, 247\u2013264."},{"volume-title":"F\u00e4rbungsprobleme auf Fl\u00e4chen und Graphen","year":"1959","author":"Ringel","key":"S0960129522000238_ref14"},{"key":"S0960129522000238_ref10","first-page":"413","article-title":"Note on petrie and hamiltonian cycles in cubic polyhedral graphs","volume":"35","author":"Ivan\u010do","year":"1994","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"S0960129522000238_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462014"},{"key":"S0960129522000238_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/300523.300531"},{"key":"S0960129522000238_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513431"},{"key":"S0960129522000238_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190030312"},{"key":"S0960129522000238_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00061-9"},{"key":"S0960129522000238_ref3","unstructured":"Bommes, D. , L\u2019vy, B. , Pietroni, N. , Puppo, E. , Silva, C. , Tarini, M. and Zorin, D. (2012). State of the art in quad meshing. In: Eurographics STARS, http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.363.6797."},{"key":"S0960129522000238_ref5","first-page":"1057","article-title":"Spectral surface quadrangulation","author":"Dong","journal-title":"ACM SIGGRAPH\u201906"},{"key":"S0960129522000238_ref15","first-page":"42","article-title":"The theory of left-right paths","volume":"452","author":"Shank","year":"1975","journal-title":"Combinatorial Mathematics III, Lecture Notes in Mathematics"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129522000238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,15]],"date-time":"2022-11-15T10:28:34Z","timestamp":1668508114000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129522000238\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["S0960129522000238"],"URL":"https:\/\/doi.org\/10.1017\/s0960129522000238","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2022,2]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}