{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:10:12Z","timestamp":1761808212349,"version":"3.44.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,9,24]],"date-time":"2018-09-24T00:00:00Z","timestamp":1537747200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SCHM 3186\/1-1"],"award-info":[{"award-number":["SCHM 3186\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0516-4","type":"journal-article","created":{"date-parts":[[2018,9,24]],"date-time":"2018-09-24T09:55:51Z","timestamp":1537782951000},"page":"1881-1900","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Edge-Orders"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7043-1867","authenticated-orcid":false,"given":"Lena","family":"Schlipf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3032-4834","authenticated-orcid":false,"given":"Jens M.","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,24]]},"reference":[{"key":"516_CR1","unstructured":"Annexstein, F., Berman, K., Swaminathan, R.: Independent spanning trees with small stretch factors. Technical Report 96-13, DIMACS (June 1996)"},{"issue":"1","key":"516_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.7155\/jgaa.00219","volume":"15","author":"M Badent","year":"2011","unstructured":"Badent, M., Brandes, U., Cornelsen, S.: More canonical ordering. J. Graph Algorithms Appl. 15(1), 97\u2013126 (2011)","journal-title":"J. Graph Algorithms Appl."},{"key":"516_CR3","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: Proceedings of the 10th European Symposium on Algorithms (ESA\u201902), pp. 152\u2013164 (2002)","DOI":"10.1007\/3-540-45749-6_17"},{"issue":"2","key":"516_CR4","doi-asserted-by":"publisher","first-page":"347","DOI":"10.7155\/jgaa.00396","volume":"20","author":"T Biedl","year":"2016","unstructured":"Biedl, T., Derka, M.: The (3,1)-ordering for 4-connected planar triangulations. J. Graph Algorithms Appl. 20(2), 347\u2013362 (2016)","journal-title":"J. Graph Algorithms Appl."},{"key":"516_CR5","doi-asserted-by":"crossref","unstructured":"Biedl, T., Schmidt, J.M.: Small-area orthogonal drawings of 3-connected graphs. In: Proceedings of the 23rd International Symposium on Graph Drawing (GD\u201915), pp. 153\u2013165 (2015)","DOI":"10.1007\/978-3-319-27261-0_13"},{"issue":"4","key":"516_CR6","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1016\/0196-6774(88)90015-6","volume":"9","author":"J Cheriyan","year":"1988","unstructured":"Cheriyan, J., Maheshwari, S.N.: Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms 9(4), 507\u2013537 (1988)","journal-title":"J. Algorithms"},{"issue":"4","key":"516_CR7","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1137\/S0895480103434592","volume":"19","author":"S Curran","year":"2005","unstructured":"Curran, S., Lee, O., Yu, X.: Chain decompositions of 4-connected graphs. SIAM J. Discrete Math. 19(4), 848\u2013880 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"516_CR8","doi-asserted-by":"crossref","unstructured":"de\u00a0Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fary embeddings of planar graphs. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC\u201988), pp. 426\u2013433 (1988)","DOI":"10.1145\/62212.62254"},{"issue":"2","key":"516_CR9","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1137\/S0895480197328771","volume":"20","author":"HN Djidjev","year":"2006","unstructured":"Djidjev, H.N.: A linear-time algorithm for finding a maximal planar subgraph. SIAM J. Discrete Math. 20(2), 444\u2013462 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"516_CR10","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S Even","year":"1976","unstructured":"Even, S., Tarjan, R.E.: Computing an st-Numbering. Theor. Comput. Sci. 2(3), 339\u2013344 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"516_CR11","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"516_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/122413.122416","volume":"22","author":"Z Galil","year":"1991","unstructured":"Galil, Z., Italiano, G.F.: Reducing edge connectivity to vertex connectivity. SIGACT News 22(1), 57\u201361 (1991)","journal-title":"SIGACT News"},{"issue":"14\u201316","key":"516_CR13","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1016\/j.ipl.2013.04.008","volume":"113","author":"A Gopalan","year":"2013","unstructured":"Gopalan, A., Ramasubramanian, S.: A counterexample for the proof of implication conjecture on independent spanning trees. Inf. Process. Lett. 113(14\u201316), 522\u2013526 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"516_CR14","doi-asserted-by":"publisher","first-page":"1336","DOI":"10.1109\/TNET.2015.2440179","volume":"24","author":"A Gopalan","year":"2016","unstructured":"Gopalan, A., Ramasubramanian, S.: IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees. IEEE\/ACM Trans. Netw. 24(3), 1336\u20131349 (2016)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"1","key":"516_CR15","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1137\/17M1134056","volume":"32","author":"A Hoyer","year":"2018","unstructured":"Hoyer, A., Thomas, R.: Four edge-independent spanning trees. SIAM J. Discrete Math. 32(1), 233\u2013248 (2018)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"516_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(87)90024-1","volume":"8","author":"H Imai","year":"1987","unstructured":"Imai, H., Asano, T.: Dynamic orthogonal segment intersection search. J. Algorithms 8(1), 1\u201318 (1987)","journal-title":"J. Algorithms"},{"key":"516_CR17","doi-asserted-by":"crossref","unstructured":"Itai, A., Rodeh, M.: The multi-tree approach to reliability in distributed networks. In: 25th Annual Symposium on Foundations of Computer Science (FOCS\u201984), pp. 137\u2013147 (1984)","DOI":"10.1109\/SFCS.1984.715910"},{"key":"516_CR18","doi-asserted-by":"crossref","unstructured":"Kant, G.: Drawing planar graphs using the lmc-ordering. In: Proceedings of the 33th Annual Symposium on Foundations of Computer Science (FOCS\u201992), pp. 101\u2013110 (1992)","DOI":"10.1109\/SFCS.1992.267814"},{"key":"516_CR19","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Computing ears and branchings in parallel. In: Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS\u201985), pp. 464\u2013467 (1985)","DOI":"10.1109\/SFCS.1985.16"},{"key":"516_CR20","series-title":"Annals of Discrete Mathematics","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0167-5060(08)70504-1","volume-title":"Advances in Graph Theory","author":"W Mader","year":"1978","unstructured":"Mader, W.: A reduction method for edge-connectivity in graphs. In: Bollob\u00e1s, B. (ed.) Advances in Graph Theory. Annals of Discrete Mathematics, vol. 3, pp. 145\u2013164. North-Holland, Amsterdam (1978)"},{"issue":"2","key":"516_CR21","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"RM McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011)","journal-title":"Comput. Sci. Rev."},{"issue":"2","key":"516_CR22","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-015-0075-x","volume":"77","author":"K Mehlhorn","year":"2017","unstructured":"Mehlhorn, K., Neumann, A., Schmidt, J.M.: Certifying 3-edge-connectivity. Algorithmica 77(2), 309\u2013335 (2017)","journal-title":"Algorithmica"},{"key":"516_CR23","unstructured":"Mondshein, L.F.: Combinatorial Ordering and the Geometric Embedding of Graphs. Ph.D. thesis, M.I.T. Lincoln Laboratory\/Harvard University (1971). Technical Report available at www.dtic.mil\/cgi-bin\/GetTRDoc?AD=AD0732882 . Accessed 11 Sept 2018"},{"key":"516_CR24","doi-asserted-by":"crossref","unstructured":"Nagai, S., Nakano, S.: A linear-time algorithm to find independent spanning trees in maximal planar graphs. In: 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201900), pp. 290\u2013301 (2000)","DOI":"10.1007\/3-540-40064-8_27"},{"issue":"6","key":"516_CR25","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0020-0190(97)00083-5","volume":"62","author":"S Nakano","year":"1997","unstructured":"Nakano, S., Rahman, M.S., Nishizeki, T.: A linear-time algorithm for four-partitioning four-connected planar graphs. Inf. Process. Lett. 62(6), 315\u2013322 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"516_CR26","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"HE Robbins","year":"1939","unstructured":"Robbins, H.E.: A theorem on graphs, with an application to a problem of traffic control. Am. Math. Mon. 46(5), 281\u2013283 (1939)","journal-title":"Am. Math. Mon."},{"key":"516_CR27","unstructured":"Schmidt, J.M.: Construction sequences and certifying 3-connectedness. In: Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS\u201910), pp. 633\u2013644 (2010)"},{"issue":"7","key":"516_CR28","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.ipl.2013.01.016","volume":"113","author":"JM Schmidt","year":"2013","unstructured":"Schmidt, J.M.: A simple test on 2-vertex- and 2-edge-connectivity. Inf. Process. Lett. 113(7), 241\u2013244 (2013)","journal-title":"Inf. Process. Lett."},{"key":"516_CR29","doi-asserted-by":"crossref","unstructured":"Schmidt, J.M.: The Mondshein sequence. In: Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP\u201914), pp. 967\u2013978 (2014)","DOI":"10.1007\/978-3-662-43948-7_80"},{"issue":"6","key":"516_CR30","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1137\/15M1030030","volume":"45","author":"JM Schmidt","year":"2016","unstructured":"Schmidt, J.M.: Mondshein sequences (a.k.a. (2,1)-orders). SIAM J. Comput. 45(6), 1985\u20132003 (2016)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"516_CR31","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34(1), 339\u2013362 (1932)","journal-title":"Trans. Am. Math. Soc."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0516-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0516-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0516-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T18:13:41Z","timestamp":1755627221000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0516-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,24]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["516"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0516-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,9,24]]},"assertion":[{"value":"16 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}