{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:33:13Z","timestamp":1759336393429,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,5]],"date-time":"2023-10-05T00:00:00Z","timestamp":1696464000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,10,5]],"date-time":"2023-10-05T00:00:00Z","timestamp":1696464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1942065"],"award-info":[{"award-number":["1942065"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007863","name":"Rice University","doi-asserted-by":"publisher","award":["Building Research on Inequality and Diversity to Grow Equity (BRIDGE) seed grant"],"award-info":[{"award-number":["Building Research on Inequality and Diversity to Grow Equity (BRIDGE) seed grant"]}],"id":[{"id":"10.13039\/100007863","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2024,1]]},"DOI":"10.1007\/s11590-023-02070-0","type":"journal-article","created":{"date-parts":[[2023,10,5]],"date-time":"2023-10-05T15:01:43Z","timestamp":1696518103000},"page":"19-31","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Linear-size formulations for connected planar graph partitioning and political districting"],"prefix":"10.1007","volume":"18","author":[{"given":"Jack","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamidreza","family":"Validi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2999-9666","authenticated-orcid":false,"given":"Austin","family":"Buchanan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Illya V.","family":"Hicks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,5]]},"reference":[{"key":"2070_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Hoboken (1993)"},{"key":"2070_CR2","first-page":"P4","volume":"28","author":"M Aprile","year":"2021","unstructured":"Aprile, M., Fiorini, S., Huynh, T., Joret, G., Wood, D.R.: Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond. Electron. J. Comb. 28, P4-47 (2021)","journal-title":"Electron. J. Comb."},{"issue":"4","key":"2070_CR3","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1287\/opre.2013.1183","volume":"61","author":"R Carvajal","year":"2013","unstructured":"Carvajal, R., Constantino, M., Goycoolea, M., Vielma, J.P., Weintraub, A.: Imposing connectivity constraints in forest planning models. Oper. Res. 61(4), 824\u2013836 (2013)","journal-title":"Oper. Res."},{"key":"2070_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"2070_CR5","unstructured":"DeFord, D., Najt, L., Stucky, E.: PlanarEmbeddings (2019). https:\/\/github.com\/vrdi\/NetworksWeek5\/tree\/master\/PlanarEmbeddings"},{"issue":"4","key":"2070_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bureau Stand. B 71(4), 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bureau Stand. B"},{"issue":"1","key":"2070_CR7","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1(1), 127\u2013136 (1971)","journal-title":"Math. Program."},{"issue":"3","key":"2070_CR8","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/s00454-016-9852-9","volume":"57","author":"S Fiorini","year":"2017","unstructured":"Fiorini, S., Huynh, T., Joret, G., Pashkovich, K.: Smaller extended formulations for the spanning tree polytope of bounded-genus graphs. Discrete Comput. Geom. 57(3), 757\u2013761 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"2070_CR9","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s12532-016-0111-0","volume":"9","author":"M Fischetti","year":"2017","unstructured":"Fischetti, M., Leitner, M., Ljubi\u0107, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out Steiner trees: a node-based model for uniform edge costs. Math. Program. Comput. 9(2), 203\u2013229 (2017)","journal-title":"Math. Program. Comput."},{"issue":"8","key":"2070_CR10","doi-asserted-by":"publisher","first-page":"B-495","DOI":"10.1287\/mnsc.16.8.B495","volume":"16","author":"RS Garfinkel","year":"1970","unstructured":"Garfinkel, R.S., Nemhauser, G.L.: Optimal political districting by implicit enumeration techniques. Manag. Sci. 16(8), B-495 (1970)","journal-title":"Manag. Sci."},{"key":"2070_CR11","volume-title":"Algorithmic Graph Theory","author":"A Gibbons","year":"1985","unstructured":"Gibbons, A.: Algorithmic Graph Theory. Cambridge University Press, Cambridge (1985)"},{"key":"2070_CR12","unstructured":"Haunert, J.H.: Aggregation in map generalization by combinatorial optimization. Ph.D. Thesis, Fachrichtung Geod\u00e4sie und Geoinformatik der Leibniz-Univ. (2008)"},{"key":"2070_CR13","doi-asserted-by":"crossref","unstructured":"Haunert, J.H., Wolff, A.: Generalization of land cover maps by mixed integer programming. In: Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, pp. 75\u201382 (2006)","DOI":"10.1145\/1183471.1183485"},{"key":"2070_CR14","volume-title":"The Realist\u2019s Guide to Redistricting: Avoiding the Legal Pitfalls","author":"JG Hebert","year":"2010","unstructured":"Hebert, J.G., Vandenberg, M.E., Smith, P.: The Realist\u2019s Guide to Redistricting: Avoiding the Legal Pitfalls. American Bar Association, Chicago (2010)"},{"issue":"6","key":"2070_CR15","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1287\/opre.13.6.998","volume":"13","author":"S Hess","year":"1965","unstructured":"Hess, S., Weaver, J., Siegfeldt, H., Whelan, J., Zitlau, P.: Nonpartisan political redistricting by computer. Oper. Res. 13(6), 998\u20131006 (1965)","journal-title":"Oper. Res."},{"issue":"4","key":"2070_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4018\/IJAGR.2017100101","volume":"8","author":"M Kim","year":"2017","unstructured":"Kim, M., Xiao, N.: Contiguity-based optimization models for political redistricting problems. Int. J. Appl. Geosp. Res. (IJAGR) 8(4), 1\u201318 (2017)","journal-title":"Int. J. Appl. Geosp. Res. (IJAGR)"},{"issue":"3","key":"2070_CR17","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s41324-018-0171-5","volume":"26","author":"MJ Kim","year":"2018","unstructured":"Kim, M.J.: Multiobjective spanning tree based optimization model to political redistricting. Spat. Inf. Res. 26(3), 317\u2013325 (2018)","journal-title":"Spat. Inf. Res."},{"key":"2070_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-56039-6","volume-title":"Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics","author":"B Korte","year":"2018","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21, 6th edn. Springer, Berlin (2018)","edition":"6"},{"issue":"3","key":"2070_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"RK Martin","year":"1991","unstructured":"Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3), 119\u2013128 (1991)","journal-title":"Oper. Res. Lett."},{"key":"2070_CR20","unstructured":"NCSL: 2010 redistricting deviation table. https:\/\/www.ncsl.org\/research\/redistricting\/2010-ncsl-redistricting-deviation-table.aspx (2020). Accessed 21 July 2022"},{"key":"2070_CR21","first-page":"89","volume":"15","author":"J Oehrlein","year":"2017","unstructured":"Oehrlein, J., Haunert, J.H.: A cutting-plane method for contiguity-constrained spatial aggregation. J. Sp. Inf. Sci. 15, 89\u2013120 (2017)","journal-title":"J. Sp. Inf. Sci."},{"key":"2070_CR22","unstructured":"Pashkovich, K.: Extended formulations for combinatorial polytopes. Ph.D. Thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg (2012)"},{"issue":"1","key":"2070_CR23","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-012-1267-2","volume":"204","author":"F Ricca","year":"2013","unstructured":"Ricca, F., Scozzari, A., Simeone, B.: Political districting: from classical models to recent approaches. Ann. Oper. Res. 204(1), 271\u2013299 (2013)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"2070_CR24","doi-asserted-by":"publisher","first-page":"1409","DOI":"10.1016\/j.ejor.2006.08.065","volume":"189","author":"F Ricca","year":"2008","unstructured":"Ricca, F., Simeone, B.: Local search algorithms for political districting. Eur. J. Oper. Res. 189(3), 1409\u20131426 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"2070_CR25","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"issue":"1","key":"2070_CR26","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1111\/j.1538-4632.2005.00605.x","volume":"37","author":"T Shirabe","year":"2005","unstructured":"Shirabe, T.: A model of contiguity for spatial unit allocation. Geogr. Anal. 37(1), 2\u201316 (2005)","journal-title":"Geogr. Anal."},{"issue":"6","key":"2070_CR27","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1068\/b34104","volume":"36","author":"T Shirabe","year":"2009","unstructured":"Shirabe, T.: Districting modeling with exact contiguity constraints. Environ. Plann. B. Plann. Des. 36(6), 1053\u20131066 (2009)","journal-title":"Environ. Plann. B. Plann. Des."},{"issue":"2","key":"2070_CR28","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1287\/opre.2022.2311","volume":"71","author":"R Swamy","year":"2023","unstructured":"Swamy, R., King, D.M., Jacobson, S.H.: Multiobjective optimization for politically fair districting: a scalable multilevel approach. Oper. Res. 71(2), 536\u2013562 (2023)","journal-title":"Oper. Res."},{"issue":"1","key":"2070_CR29","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1002\/net.21849","volume":"73","author":"H Validi","year":"2019","unstructured":"Validi, H., Buchanan, A.: A note on \u201ca linear-size zero-one programming model for the minimum spanning tree problem in planar graphs\u2019\u2019. Networks 73(1), 135\u2013142 (2019)","journal-title":"Networks"},{"issue":"4","key":"2070_CR30","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s12532-022-00221-5","volume":"14","author":"H Validi","year":"2022","unstructured":"Validi, H., Buchanan, A.: Political districting to minimize cut edges. Math. Program. Comput. 14(4), 623\u2013672 (2022)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"2070_CR31","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1287\/opre.2021.2141","volume":"70","author":"H Validi","year":"2022","unstructured":"Validi, H., Buchanan, A., Lykhovyd, E.: Imposing contiguity constraints in political districting models. Oper. Res. 70(2), 867\u2013892 (2022)","journal-title":"Oper. Res."},{"issue":"1","key":"2070_CR32","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/s10107-017-1117-8","volume":"166","author":"Y Wang","year":"2017","unstructured":"Wang, Y., Buchanan, A., Butenko, S.: On imposing connectivity constraints in integer programs. Math. Program. 166(1), 241\u2013271 (2017)","journal-title":"Math. Program."},{"issue":"1","key":"2070_CR33","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/net.10010","volume":"39","author":"JC Williams","year":"2002","unstructured":"Williams, J.C.: A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs. Networks 39(1), 53\u201360 (2002)","journal-title":"Networks"},{"issue":"3","key":"2070_CR34","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"RT Wong","year":"1984","unstructured":"Wong, R.T.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28(3), 271\u2013287 (1984)","journal-title":"Math. Program."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02070-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-02070-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02070-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T06:23:50Z","timestamp":1704867830000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-02070-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,5]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["2070"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-02070-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2023,10,5]]},"assertion":[{"value":"26 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}