{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:52:03Z","timestamp":1725688323364},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_28","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"316-327","source":"Crossref","is-referenced-by-count":1,"title":["Connectivity Oracles for Planar Graphs"],"prefix":"10.1007","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Wulff-Nilsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"28_CR1","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/s00453-008-9234-7","volume":"53","author":"P. Afshani","year":"2009","unstructured":"Afshani, P., Chan, T.M.: Dynamic connectivity for axis-parallel rectangles. Algorithmica\u00a053(4), 474\u2013487 (2009)","journal-title":"Algorithmica"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: Proceedings 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 258\u2013264 (2002)","DOI":"10.1145\/564870.564914"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proceedings 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 534\u2013544 (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"issue":"1","key":"28_CR4","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1006\/jcss.1998.1580","volume":"57","author":"A. Andersson","year":"1998","unstructured":"Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? J. Comput. Syst. Sci.\u00a057(1), 74\u201393 (1998)","journal-title":"Comput. Syst. Sci."},{"issue":"3","key":"28_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1236457.1236460","volume":"54","author":"A. Andersson","year":"2007","unstructured":"Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM\u00a054(3), 13 (2007)","journal-title":"J. ACM"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"731","DOI":"10.4153\/CJM-1966-073-4","volume":"18","author":"D. Barnette","year":"1966","unstructured":"Barnette, D.: Trees in polyhedral graphs. Canadian Journal of Mathematics\u00a018, 731\u2013736 (1966)","journal-title":"Canadian Journal of Mathematics"},{"key":"28_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA Problem Revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Karger, D.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proceedings 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 101\u2013110 (2009)","DOI":"10.1145\/1536414.1536431"},{"key":"28_CR9","series-title":"LNCS","first-page":"316","volume-title":"SWAT 2012","author":"G. Borradaile","year":"2012","unstructured":"Borradaile, G., Pettie, S., Wulff-Nilsen, C.: Connectivity Oracles for Planar Graphs. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 316\u2013327. Springer, Heidelberg (2012)"},{"issue":"3","key":"28_CR10","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/S009753970343912X","volume":"36","author":"T. Chan","year":"2006","unstructured":"Chan, T.: Dynamic subgraph connectivity with geometric applications. SIAM J. Comput.\u00a036(3), 681\u2013694 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"28_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/090751670","volume":"40","author":"T.M. Chan","year":"2011","unstructured":"Chan, T.M., Patrascu, M., Roditty, L.: Dynamic connectivity: Connecting to networks and geometry. SIAM J. Comput.\u00a040(2), 333\u2013349 (2011)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"28_CR12","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/S0097539705429847","volume":"37","author":"C. Demetrescu","year":"2008","unstructured":"Demetrescu, C., Thorup, M., Chowdhury, R.A., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Comput.\u00a037(5), 1299\u20131318 (2008)","journal-title":"SIAM J. Comput."},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-14165-2_18","volume-title":"Automata, Languages and Programming","author":"R. Duan","year":"2010","unstructured":"Duan, R.: New Data Structures for Subgraph Connectivity. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 201\u2013212. Springer, Heidelberg (2010)"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 506\u2013515 (2009)","DOI":"10.1137\/1.9781611973068.56"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Connectivity oracles for failure prone graphs. In: Proceedings 42nd ACM Symposium on Theory of Computing, pp. 465\u2013474 (2010)","DOI":"10.1145\/1806689.1806754"},{"key":"28_CR16","first-page":"646","volume":"7","author":"J. Edmonds","year":"1960","unstructured":"Edmonds, J.: A combinatorial representation for polyhedral surfaces. Notices of the American Mathematical Society\u00a07, 646 (1960)","journal-title":"Notices of the American Mathematical Society"},{"issue":"5","key":"28_CR17","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G., Nissenzweig, A.: Sparsification \u2014 a technique for speeding up dynamic graph algorithms. J. ACM\u00a044(5), 669\u2013696 (1997)","journal-title":"J. ACM"},{"issue":"1","key":"28_CR18","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Italiano, G.F., Tamassia, R., Tarjan, R.E., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algor.\u00a013(1), 33\u201354 (1992)","journal-title":"J. Algor."},{"issue":"4","key":"28_CR19","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. Frederickson","year":"1985","unstructured":"Frederickson, G.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput.\u00a014(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"28_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci.\u00a048(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"28_CR21","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s004530010032","volume":"28","author":"D. Frigioni","year":"2000","unstructured":"Frigioni, D., Italiano, G.F.: Dynamically switching vertices in planar graphs. Algorithmica\u00a028(1), 76\u2013103 (2000)","journal-title":"Algorithmica"},{"key":"28_CR22","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in O(n loglogn) time and linear space. J. Algorithms\u00a050, 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"key":"28_CR23","first-page":"135","volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS 2002","author":"Y. Han","year":"2002","unstructured":"Han, Y., Thorup, M.: Integer sorting in ${O}(n\\sqrt{\\log\\log n})$ expected time and linear space. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS 2002, pp. 135\u2013144. IEEE Computer Society, Washington, DC (2002)"},{"issue":"2","key":"28_CR24","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"28_CR25","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM\u00a048(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proceedings 38th ACM Symposium on Theory of Computing (STOC), pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Planning for fast connectivity updates. In: Proceedings 48th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 263\u2013271 (2007)","DOI":"10.1109\/FOCS.2007.4389498"},{"key":"28_CR28","unstructured":"Strothmann, W.: Bounded degree spanning trees. PhD thesis, Universit\u00e4t-Gesamthochschule Paderborn (1997)"},{"key":"28_CR29","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Syst. Theory\u00a010, 99\u2013127 (1977)","journal-title":"Math. Syst. Theory"},{"key":"28_CR30","doi-asserted-by":"crossref","first-page":"73","DOI":"10.4064\/fm-21-1-73-84","volume":"21","author":"H. Whitney","year":"1933","unstructured":"Whitney, H.: Planar graphs. Fundamenta mathematicae\u00a021, 73\u201384 (1933)","journal-title":"Fundamenta mathematicae"},{"issue":"2","key":"28_CR31","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u03b8(n). Info.\u00a0Proc.\u00a0Lett.\u00a017(2), 81\u201384 (1983)","journal-title":"Info.\u00a0Proc.\u00a0Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:07:25Z","timestamp":1606187245000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}