{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:30:20Z","timestamp":1760441420569,"version":"3.41.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319621265"},{"type":"electronic","value":"9783319621272"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62127-2_33","type":"book-chapter","created":{"date-parts":[[2017,7,4]],"date-time":"2017-07-04T02:47:31Z","timestamp":1499136451000},"page":"385-396","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast and Compact Planar Embeddings"],"prefix":"10.1007","author":[{"given":"Leo","family":"Ferres","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9","family":"Fuentes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,5]]},"reference":[{"issue":"10","key":"33_CR1","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"36","author":"B Awerbuch","year":"1987","unstructured":"Awerbuch, B., Shiloach, Y.: New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Trans. Computers 36(10), 1258\u20131263 (1987)","journal-title":"IEEE Trans. Computers"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1016\/j.jpdc.2005.03.011","volume":"65","author":"DA Bader","year":"2005","unstructured":"Bader, D.A., Cong, G.: A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs). J. Parallel and Distributed Computing 65, 994\u20131006 (2005)","journal-title":"J. Parallel and Distributed Computing"},{"key":"33_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-010-9452-7","volume":"62","author":"J Barbay","year":"2012","unstructured":"Barbay, J., Aleardi, L.C., He, M., Munro, J.I.: Succinct representation of labeled graphs. Algorithmica 62, 224\u2013257 (2012)","journal-title":"Algorithmica"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"Biggs, N.: Spanning trees of dual graphs. J. Comb. Theory, Series B, 11: 127\u2013131 (1971)","DOI":"10.1016\/0095-8956(71)90022-0"},{"key":"33_CR5","unstructured":"Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: SODA, pp. 679\u2013688 (2003)"},{"key":"33_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-642-13509-5_13","volume-title":"Combinatorial Pattern Matching","author":"GE Blelloch","year":"2010","unstructured":"Blelloch, G.E., Farzan, A.: Succinct representations of separable graphs. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 138\u2013150. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-13509-5_13"},{"key":"33_CR7","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.tcs.2008.08.016","volume":"408","author":"LC Aleardi","year":"2008","unstructured":"Aleardi, L.C., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. TCS 408, 174\u2013187 (2008)","journal-title":"TCS"},{"key":"33_CR8","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/S0097539702411381","volume":"34","author":"Y-T Chiang","year":"2005","unstructured":"Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications. SIAM J. Comp. 34, 924\u2013945 (2005)","journal-title":"SIAM J. Comp."},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Cong, G., Bader, D.A.: The Euler tour technique and parallel rooted spanning tree. In: ICPP, pp. 448\u2013457 (2004)","DOI":"10.1109\/ICPP.2004.1327954"},{"key":"33_CR10","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Multithreaded algorithms. In: Introduction to Algorithms, pp. 772\u2013812. MIT Press (2009)"},{"key":"33_CR11","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. In: SODA, pp. 599\u2013608 (2003)"},{"key":"33_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-20086-6_1","volume-title":"Experimental Algorithms","author":"L Ferres","year":"2015","unstructured":"Ferres, L., Fuentes-Sep\u00falveda, J., He, M., Zeh, N.: Parallel construction of succinct trees. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 3\u201314. Springer, Cham (2015). doi:10.1007\/978-3-319-20086-6_1"},{"key":"33_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1361192.1361196","volume":"4","author":"\u00c9 Fusy","year":"2008","unstructured":"Fusy, \u00c9., Schaeffer, G., Poulalhon, D.: Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling. TALG 4, 19 (2008)","journal-title":"TALG"},{"key":"33_CR14","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/S0895480197325031","volume":"12","author":"X He","year":"1999","unstructured":"He, X., Kao, M., Lu, H.: Linear-time succinct encodings of planar graphs via canonical orderings. SIAM J. Discrete Math. 12, 317\u2013325 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549\u2013554 (1989)","DOI":"10.1007\/978-1-4612-3694-8_36"},{"key":"33_CR16","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/BF01192047","volume":"14","author":"M Kao","year":"1995","unstructured":"Kao, M., Teng, S., Toyama, K.: An optimal parallel algorithm for planar cycle separators. Algorithmica 14, 398\u2013408 (1995)","journal-title":"Algorithmica"},{"key":"33_CR17","first-page":"239","volume":"58","author":"K Keeler","year":"1995","unstructured":"Keeler, K., Westbrook, J.: Short encodings of planar graphs and maps. DAM 58, 239\u2013252 (1995)","journal-title":"DAM"},{"key":"33_CR18","doi-asserted-by":"crossref","unstructured":"Labeit, J., Shun, J., Blelloch, G.E.: Parallel lightweight wavelet tree, suffix array and FM-index construction. In: DCC, pp. 33\u201342 (2016)","DOI":"10.1109\/DCC.2016.117"},{"key":"33_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Applied Math. 36, 177\u2013189 (1979)","journal-title":"SIAM J. Applied Math."},{"key":"33_CR20","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Nicholson, P.K.: Compressed representations of graphs. In: Encyclopedia of Algorithms, pp. 382\u2013386. Springer (2016)","DOI":"10.1007\/978-1-4939-2864-4_646"},{"key":"33_CR21","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Compact Data Structures: A Practical Approach. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781316588284"},{"key":"33_CR22","doi-asserted-by":"crossref","unstructured":"Riley, T.R., Thurston, W.P.: The absence of efficient dual pairs of spanning trees in planar graphs. Electronic J. Comb. 13 (2006)","DOI":"10.37236\/1151"},{"issue":"1","key":"33_CR23","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y Shiloach","year":"1982","unstructured":"Shiloach, Y., Vishkin, U.: An o(log n) parallel connectivity algorithm. J. Algorithms 3(1), 57\u201367 (1982)","journal-title":"J. Algorithms"},{"key":"33_CR24","doi-asserted-by":"crossref","unstructured":"Shun, J., Dhulipala, L., Blelloch, G.E.: A simple and practical linear-work parallel algorithm for connectivity. In: SPAA, pp. 143\u2013153 (2014)","DOI":"10.1145\/2612669.2612692"},{"key":"33_CR25","first-page":"289","volume":"8","author":"A Tur\u00e1n","year":"1984","unstructured":"Tur\u00e1n, A.: On the succinct representation of graphs. DAM 8, 289\u2013294 (1984)","journal-title":"DAM"},{"key":"33_CR26","doi-asserted-by":"publisher","first-page":"249","DOI":"10.4153\/CJM-1963-029-x","volume":"15","author":"WT Tutte","year":"1963","unstructured":"Tutte, W.T.: A census of planar maps. Canadian J. Math. 15, 249\u2013271 (1963)","journal-title":"Canadian J. Math."},{"key":"33_CR27","first-page":"36","volume":"38","author":"M Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. JCSS 38, 36\u201367 (1989)","journal-title":"JCSS"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62127-2_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T01:34:33Z","timestamp":1750469673000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-62127-2_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319621265","9783319621272"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62127-2_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"5 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. John's","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}