{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:42:15Z","timestamp":1743126135390,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":35,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819628445"},{"type":"electronic","value":"9789819628452"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-2845-2_10","type":"book-chapter","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T15:59:57Z","timestamp":1740067197000},"page":"143-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ranking and\u00a0Unranking of\u00a0the\u00a0Planar Embeddings of\u00a0a\u00a0Planar Graph"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4224-1550","authenticated-orcid":false,"given":"Giuseppe","family":"Di Battista","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5766-4567","authenticated-orcid":false,"given":"Fabrizio","family":"Grosso","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giulia","family":"Maragno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9806-7411","authenticated-orcid":false,"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"key":"10_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Angelini, P., Di Battista, G., Patrignani, M.: Finding a minimum-depth embedding of a planar graph in $$O(n^4)$$ time. Algorithmica 60(4), 890\u2013937 (2011)","DOI":"10.1007\/s00453-009-9380-6"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2013.08.018","volume":"514","author":"P Angelini","year":"2013","unstructured":"Angelini, P., Cortese, P.F., Di Battista, G., Patrignani, M.: Topological morphing of planar graphs. Theor. Comput. Sci. 514, 2\u201320 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Angelini, P., et al.: Testing planarity of partially embedded graphs. ACM Trans. Algorithms 11(4) (2015). Article No. 32","DOI":"10.1145\/2629341"},{"key":"10_CR5","unstructured":"Bender, E.A., Williamson, S.G.: Foundations of Combinatorics with Applications. Courier Corporation (2005)"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1109\/12.868028","volume":"49","author":"P Bertolazzi","year":"2000","unstructured":"Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Trans. Comput. 49, 826\u2013840 (2000)","journal-title":"IEEE Trans. Comput."},{"issue":"6","key":"10_CR7","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/BF01188716","volume":"12","author":"P Bertolazzi","year":"1994","unstructured":"Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476\u2013497 (1994)","journal-title":"Algorithmica"},{"issue":"3","key":"10_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s002249910006","volume":"33","author":"HC Chen","year":"2000","unstructured":"Chen, H.C., Wang, Y.L.: An efficient algorithm for generating pr\u00fcfer codes from labelled trees. Theory Comput. Syst. 33, 97\u2013105 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"10_CR10","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1137\/0406027","volume":"6","author":"J Cai","year":"1993","unstructured":"Cai, J.: Counting embeddings of planar graphs using DFS trees. SIAM J. Discret. Math. 6(3), 335\u2013352 (1993)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"10_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2007.03.009","volume":"382","author":"S Caminiti","year":"2007","unstructured":"Caminiti, S., Finocchi, I., Petreschi, R.: On coding labeled trees. Theor. Comput. Sci. 382(2), 97\u2013108 (2007). Latin American Theoretical Informatics","journal-title":"Theor. Comput. Sci."},{"key":"10_CR12","first-page":"376","volume":"23","author":"A Cayley","year":"1878","unstructured":"Cayley, A.: A theorem on trees. Quart. J. Math. 23, 376\u2013378 (1878)","journal-title":"Quart. J. Math."},{"key":"10_CR13","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)"},{"key":"10_CR14","unstructured":"Di Battista, G., Grosso, F., Maragno, G., Patrignani, M.: Ranking and unranking of the planar embeddings of a planar graph (2024). https:\/\/arxiv.org\/abs\/2411.10319"},{"issue":"4","key":"10_CR15","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302\u2013318 (1996)","journal-title":"Algorithmica"},{"issue":"5","key":"10_CR16","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Didimo, W., Liotta, G., Ortali, G., Patrignani, M.: Optimal orthogonal drawings of planar 3-graphs in linear time. In: Chawla, S. (ed.) Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 806\u2013825. ACM-SIAM (2020)","DOI":"10.1137\/1.9781611975994.49"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jcss.2018.08.003","volume":"99","author":"W Didimo","year":"2019","unstructured":"Didimo, W., Liotta, G., Patrignani, M.: HV-planarity: algorithms and complexity. J. Comput. Syst. Sci. 99, 72\u201390 (2019)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10_CR19","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A Garg","year":"2001","unstructured":"Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"key":"10_CR20","unstructured":"Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. In: 12th ACM-SIAM Symposium on Discrete Algorithms, SODA 2001, pp. 246\u2013255. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s00373-002-0499-3","volume":"19","author":"H Kajimoto","year":"2003","unstructured":"Kajimoto, H.: An extension of the Pr\u00fcfer code and assembly of connected graphs from their blocks. Graphs Combin. 19, 231\u2013239 (2003)","journal-title":"Graphs Combin."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Karabeg, A.: Ranking planar embeddings using PQ-trees. In: Gimbel, J., Kennedy, J.W., Quintas, L.V. (eds.) Quo Vadis, Graph Theory? Annals of Discrete Mathematics, vol.\u00a055, pp. 249\u2013260. Elsevier (1993)","DOI":"10.1016\/S0167-5060(08)70392-3"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Kiem-Phong\u00a0Vo, W.E.D., Williamson, S.G.: Ranking and unranking planar embeddings. Linear Multilinear Algebra 18(1), 35\u201365 (1985)","DOI":"10.1080\/03081088508817673"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press (1999)","DOI":"10.1145\/309739.309744"},{"key":"10_CR25","unstructured":"Leyshon, P.R., Lisle, R.J.: Stereographic Projection Techniques. Elsevier Science (1996). Original from the University of California"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Mutzel, P., Weiskircher, R.: Optimizing over all combinatorial embeddings of a planar graph. In: 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 361\u2013376. Springer, London (1999)","DOI":"10.1007\/3-540-48777-8_27"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Mutzel, P., Weiskircher, R.: Computing optimal embeddings for planar graphs. In: Proceedings of the 6th Annual International Conference on Computing and Combinatorics, COCOON 2000, pp. 95\u2013104. Springer, London (2000)","DOI":"10.1007\/3-540-44968-X_10"},{"issue":"6","key":"10_CR28","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0020-0190(01)00141-7","volume":"79","author":"WJ Myrvold","year":"2001","unstructured":"Myrvold, W.J., Ruskey, F.: Ranking and unranking permutations in linear time. Inf. Process. Lett. 79(6), 281\u2013284 (2001)","journal-title":"Inf. Process. Lett."},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"Pizzonia, M., Tamassia, R.: Minimum depth graph embedding. In: Proceedings of the ESA 2000. LNCS, vol. 1879, pp. 356\u2013367. Springer (2000)","DOI":"10.1007\/3-540-45253-2_33"},{"key":"10_CR30","first-page":"742","volume":"27","author":"H Prufer","year":"1918","unstructured":"Prufer, H.: Neuer bewis eines satzes uber permutationnen. Arch. Math. Phys. 27, 742\u2013744 (1918)","journal-title":"Arch. Math. Phys."},{"issue":"1\u20133","key":"10_CR31","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0012-365X(93)90316-L","volume":"122","author":"MFM Stallmann","year":"1993","unstructured":"Stallmann, M.F.M.: On counting planar embeddings. Discret. Math. 122(1\u20133), 385\u2013392 (1993)","journal-title":"Discret. Math."},{"issue":"1","key":"10_CR32","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1023\/A:1009760732249","volume":"3","author":"R Tamassia","year":"1998","unstructured":"Tamassia, R.: Constraints in graph drawing algorithms. Constraints An Int. J. 3(1), 87\u2013120 (1998)","journal-title":"Constraints An Int. J."},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Tamassia, R. (ed.): Handbook on Graph Drawing and Visualization. Chapman and Hall\/CRC (2013)","DOI":"10.1201\/b15385"},{"issue":"2","key":"10_CR34","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"RE Tarjan","year":"1984","unstructured":"Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM 31(2), 245\u2013281 (1984)","journal-title":"J. ACM"},{"issue":"2","key":"10_CR35","doi-asserted-by":"publisher","first-page":"111","DOI":"10.4236\/jsea.2009.22016","volume":"2","author":"X Wang","year":"2009","unstructured":"Wang, X., Wang, L., Wu, Y.: An optimal algorithm for prufer codes. J. Softw. Eng. Appl. 2(2), 111\u2013115 (2009)","journal-title":"J. Softw. Eng. Appl."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-2845-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T16:00:14Z","timestamp":1740067214000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-2845-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819628445","9789819628452"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-2845-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"21 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 February 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 March 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/walcom2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}