{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T10:49:05Z","timestamp":1768560545711,"version":"3.49.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s00453-020-00793-5","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T16:04:15Z","timestamp":1609776255000},"page":"1544-1558","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Fast Algorithm for the Product Structure of Planar Graphs"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0471-4118","authenticated-orcid":false,"given":"Pat","family":"Morin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"issue":"3\u20134","key":"793_CR1","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1002\/rsa.10057","volume":"21","author":"N Alon","year":"2002","unstructured":"Alon, N., Grytczuk, J., Ha\u0142uszczak, M., Riordan, O.: Nonrepetitive colorings of graphs. Random Struct. Algorithms 21(3\u20134), 336\u2013346 (2002). https:\/\/doi.org\/10.1002\/rsa.10057","journal-title":"Random Struct. Algorithms"},{"key":"793_CR2","doi-asserted-by":"publisher","unstructured":"D\u0119bski, M., Felsner, S., Micek, P., Schr\u00f6der, F.: Improved bounds for centered colorings. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020, pp. 2212\u20132226. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.136","DOI":"10.1137\/1.9781611975994.136"},{"key":"793_CR3","doi-asserted-by":"publisher","unstructured":"Diestel, R.: Graph Theory, Fifth Edition, volume 173 of Graduate texts in mathematics. Springer, Berlin (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3","DOI":"10.1007\/978-3-662-53622-3"},{"key":"793_CR4","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., Esperet, L., Joret, G., Walczak, B., Wood, D.R.: Planar graphs have bounded nonrepetitive chromatic number. In: Advances in Combinatorics, March (2020). https:\/\/doi.org\/10.19086\/aic.12100","DOI":"10.19086\/aic.12100"},{"key":"793_CR5","unstructured":"Dujmovi\u0107, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. In: Proceedings of 60th Annual Symposium on Foundations of Computer Science (FOCS \u201919), (2019). arXiv:1904.04791"},{"key":"793_CR6","unstructured":"Dujmovi\u0107, V., Esperet, L., Gavoille, C., Joret, G., Micek, P., Morin, P.: Adjacency labelling for planar graphs (and beyond). CoRR, abs\/2003.04280, (2020), arXiv:2003.04280"},{"key":"793_CR7","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.R.: The structure of k-planar graphs. CoRR, abs\/1907.05168, (2019), arXiv:1907.05168"},{"issue":"2","key":"793_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985). https:\/\/doi.org\/10.1016\/0022-0000(85)90014-5","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"793_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-0010-x","volume":"49","author":"A Grigoriev","year":"2007","unstructured":"Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1\u201311 (2007). https:\/\/doi.org\/10.1007\/s00453-007-0010-x","journal-title":"Algorithmica"},{"issue":"3","key":"793_CR10","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/0405031","volume":"5","author":"LS Heath","year":"1992","unstructured":"Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5(3), 398\u2013412 (1992). https:\/\/doi.org\/10.1137\/0405031","journal-title":"SIAM J. Discrete Math."},{"key":"793_CR11","doi-asserted-by":"publisher","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: Janos, S. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2\u20134, 1988, Chicago, Illinois, USA, pp. 334\u2013343. ACM (1988) https:\/\/doi.org\/10.1145\/62212.62244","DOI":"10.1145\/62212.62244"},{"issue":"4","key":"793_CR12","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596\u2013603 (1992). https:\/\/doi.org\/10.1137\/0405049","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"793_CR13","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1002\/jgt.21630","volume":"72","author":"VP Korzhik","year":"2013","unstructured":"Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory 72(1), 30\u201371 (2013). https:\/\/doi.org\/10.1002\/jgt.21630","journal-title":"J. Graph Theory"},{"key":"793_CR14","unstructured":"Kr\u00e1\u013e, D., Lazic, R.: Open problems from the workshop on algorithms, logic and structure, December (2016). https:\/\/warwick.ac.uk\/fac\/sci\/maths\/people\/staff\/daniel_kral\/alglogstr\/openproblems.pdf"},{"issue":"1","key":"793_CR15","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. 12(1), 6\u201326 (1999). https:\/\/doi.org\/10.1137\/S089548019529248X","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"793_CR16","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27(6), 1022\u20131041 (2006). https:\/\/doi.org\/10.1016\/j.ejc.2005.01.010","journal-title":"Eur. J. Comb."},{"issue":"3","key":"793_CR17","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Grad and classes with bounded expansion i. decompositions. Eur. J. Comb. 29(3), 760\u2013776 (2008). https:\/\/doi.org\/10.1016\/j.ejc.2006.07.013","journal-title":"Eur. J. Comb."},{"key":"793_CR18","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M. Siebertz, S.: Polynomial bounds for centered colorings on proper minor-closed graph classes. In: Timothy M.C. (ed.) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019, pp. 1501\u20131520. SIAM, (2019). arXiv:1807.03683v2, https:\/\/doi.org\/10.1137\/1.9781611975482.91","DOI":"10.1137\/1.9781611975482.91"},{"key":"793_CR19","unstructured":"Urschel, J.C., Wellens, J.: Testing k-planarity is NP-complete. CoRR, abs\/1907.02104, (2020). arXiv:1907.02104"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00793-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00793-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00793-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T10:19:39Z","timestamp":1617877179000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00793-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["793"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00793-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"6 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}