{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:37:01Z","timestamp":1740177421589,"version":"3.37.3"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000084","name":"Directorate for Engineering","doi-asserted-by":"publisher","award":["1745300"],"award-info":[{"award-number":["1745300"]}],"id":[{"id":"10.13039\/100000084","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s41109-019-0142-3","type":"journal-article","created":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T13:03:12Z","timestamp":1563282192000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Multiscale planar graph generation"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8255-0230","authenticated-orcid":false,"given":"Varsha","family":"Chauhan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Gutfraind","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Safro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"142_CR1","doi-asserted-by":"crossref","unstructured":"Aiello, W, Chung F, Lu L (2000) A random graph model for massive graphs In: Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, 171\u2013180.. ACM.","DOI":"10.1145\/335305.335326"},{"issue":"1","key":"142_CR2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"W Aiello","year":"2001","unstructured":"Aiello, W, Chung F, Lu L (2001) A random graph model for power law graphs. Exp Math 10(1):53\u201366.","journal-title":"Exp Math"},{"issue":"1-3","key":"142_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2010.11.002","volume":"499","author":"M Barth\u00e9lemy","year":"2011","unstructured":"Barth\u00e9lemy, M (2011) Spatial networks. Phys Rep 499(1-3):1\u2013101.","journal-title":"Phys Rep"},{"key":"142_CR4","doi-asserted-by":"crossref","unstructured":"Brandt, A, Ron D (2003) Chapter 1 : Multigrid solvers and multilevel optimization strategies. In: Cong J Shinnerl JR (eds)Multilevel Optimization and VLSICAD.. Springer.","DOI":"10.1007\/978-1-4757-3748-6_1"},{"key":"142_CR5","unstructured":"Brinkmann, G. (2011) Program fullgen-a program for generating nonisomorphic fullerenes. see http:\/\/cs.anu.edu.au\/bdm\/plantri ."},{"issue":"2","key":"142_CR6","first-page":"323","volume":"58","author":"G Brinkmann","year":"2007","unstructured":"Brinkmann, G, McKay BD, et al (2007) Fast generation of planar graphs. MATCH Commun Math Comput Chem 58(2):323\u2013357.","journal-title":"MATCH Commun Math Comput Chem"},{"key":"142_CR7","doi-asserted-by":"crossref","unstructured":"Bulu\u00e7, A, Meyerhenke H, Safro I, Sanders P, Schulz C (2016) Recent advances in graph partitioning In: Algorithm Engineering: Selected Results and Surveys, 117\u2013158.. Springer.","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"142_CR8","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D, Zhan Y, Faloutsos C (2004) R-mat: A recursive model for graph mining In: Proceedings of the 2004 SIAM International Conference on Data Mining, 442\u2013446.. Springer.","DOI":"10.1137\/1.9781611972740.43"},{"issue":"6","key":"142_CR9","doi-asserted-by":"publisher","first-page":"3468","DOI":"10.1137\/090775087","volume":"33","author":"J Chen","year":"2011","unstructured":"Chen, J, Safro I (2011) Algebraic distance on graphs. SIAM J Sci Comput 33(6):3468\u20133490.","journal-title":"SIAM J Sci Comput"},{"key":"142_CR10","first-page":"543","volume":"2011","author":"M Chimani","year":"2013","unstructured":"Chimani, M, Gutwenger C, J\u00fcnger M, Klau GW, Klein K, Mutzel P (2013) The open graph drawing framework (ogdf). Handb Graph Drawing Vis 2011:543\u2013569.","journal-title":"Handb Graph Drawing Vis"},{"key":"142_CR11","doi-asserted-by":"publisher","first-page":"409","DOI":"10.5194\/isprsannals-II-3-W5-409-2015","volume":"2","author":"R Cura","year":"2015","unstructured":"Cura, R, Perret J, Paparoditis N (2015) Streetgen: In-base procedural-based road generation. ISPRS Ann Photogramm Remote Sens Spat Inf Sci 2:409.","journal-title":"ISPRS Ann Photogramm Remote Sens Spat Inf Sci"},{"key":"142_CR12","unstructured":"Davis, T (1997) University of Florida Sparse Matrix Collection. NA Dig 97(23)."},{"key":"142_CR13","unstructured":"Denise, A, Vasconcellos M, Welsh DJ (1996) The random planar graph. Congressus numerantium:61\u201380."},{"key":"142_CR14","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P, R\u00e9nyi A (1959) On random graphs, I. Publ Math (Debrecen) 6:290\u2013297.","journal-title":"Publ Math (Debrecen)"},{"issue":"3","key":"142_CR15","doi-asserted-by":"publisher","first-page":"032810","DOI":"10.1103\/PhysRevE.88.032810","volume":"88","author":"P Fronczak","year":"2013","unstructured":"Fronczak, P, Fronczak A, Bujok M (2013) Exponential random graph models for networks with community structure. Phys Rev E 88(3):032810.","journal-title":"Phys Rev E"},{"issue":"2","key":"142_CR16","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1017\/S0963548303005947","volume":"13","author":"S Gerke","year":"2004","unstructured":"Gerke, S, McDiarmid C (2004) On the number of edges in random planar graphs. Comb Probab Comput 13(2):165\u2013183.","journal-title":"Comb Probab Comput"},{"issue":"4","key":"142_CR17","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1137\/0109045","volume":"9","author":"EN Gilbert","year":"1961","unstructured":"Gilbert, EN (1961) Random plane networks. J Soc Ind Appl Math 9(4):533\u2013543.","journal-title":"J Soc Ind Appl Math"},{"key":"142_CR18","unstructured":"Gutfraind, A, Meyers LA, Safro I (2012) Multiscale network generation. CoRR abs\/1207.4266. http:\/\/arxiv.org\/abs\/1207.4266."},{"key":"142_CR19","unstructured":"Gutfraind, A, Safro I, Meyers LA (2015) Multiscale network generation In: 18th IEEE International Conference on Information Fusion (Fusion), 158\u2013165.. Springer."},{"issue":"1","key":"142_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10589-017-9945-2","volume":"69","author":"WW Hager","year":"2018","unstructured":"Hager, WW, Hungerford JT, Safro I (2018) A multilevel bilinear programming algorithm for the vertex separator problem. Comput Optim Appl 69(1):189\u2013223.","journal-title":"Comput Optim Appl"},{"issue":"3","key":"142_CR21","doi-asserted-by":"publisher","first-page":"54860","DOI":"10.18637\/jss.v024.i03","volume":"24","author":"DR Hunter","year":"2008","unstructured":"Hunter, DR, Handcock MS, Butts CT, Goodreau SM, Morris M (2008) ergm: A package to fit, simulate and diagnose exponential-family models for networks. J Stat Softw 24(3):54860.","journal-title":"J Stat Softw"},{"issue":"3","key":"142_CR22","first-page":"352","volume":"5","author":"E John","year":"2016","unstructured":"John, E, Safro I (2016) Single-and multi-level network sparsification by algebraic distance. J Complex Netw 5(3):352\u2013388.","journal-title":"J Complex Netw"},{"issue":"1","key":"142_CR23","doi-asserted-by":"publisher","first-page":"016107","DOI":"10.1103\/PhysRevE.83.016107","volume":"83","author":"B Karrer","year":"2011","unstructured":"Karrer, B, Newman ME (2011) Stochastic blockmodels and community structure in networks. Phys Rev E 83(1):016107.","journal-title":"Phys Rev E"},{"key":"142_CR24","unstructured":"Leskovec, J, Krevl A (2014) SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data ."},{"issue":"1","key":"142_CR25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2009","unstructured":"Leskovec, J, Lang KJ, Dasgupta A, Mahoney MW (2009) Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29\u2013123.","journal-title":"Internet Math"},{"key":"142_CR26","doi-asserted-by":"crossref","unstructured":"Mahdian, M, Xu Y (2007) Stochastic kronecker graphs In: International Workshop on Algorithms and Models for the Web-Graph, 179\u2013186.. Springer.","DOI":"10.1007\/978-3-540-77004-6_14"},{"issue":"2","key":"142_CR27","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.jctb.2004.09.007","volume":"93","author":"C McDiarmid","year":"2005","unstructured":"McDiarmid, C, Steger A, Welsh DJ (2005) Random planar graphs. J Comb Theory Ser B 93(2):187\u2013205.","journal-title":"J Comb Theory Ser B"},{"key":"142_CR28","doi-asserted-by":"crossref","unstructured":"Meinert, S, Wagner D (2011) An experimental study on generating planar graphs In: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, 375\u2013387.. Springer.","DOI":"10.1007\/978-3-642-21204-8_39"},{"issue":"1","key":"142_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.2166\/ws.2011.121","volume":"12","author":"J Muranho","year":"2012","unstructured":"Muranho, J, Ferreira A, Sousa J, Gomes A, Marques AS (2012) Waternetgen: an epanet extension for automatic water distribution network models generation and pipe sizing. Water Sci Technol Water Supply 12(1):117\u2013123.","journal-title":"Water Sci Technol Water Supply"},{"key":"142_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"M Newman","year":"2010","unstructured":"Newman, M (2010) Networks: An Introduction. Oxford University Press, Inc., New York."},{"key":"142_CR31","doi-asserted-by":"crossref","unstructured":"Newman, M (2018) Networks. Springer.","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"issue":"6","key":"142_CR32","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(556)","volume":"134","author":"A Ostfeld","year":"2008","unstructured":"Ostfeld, A, Uber JG, Salomons E, Berry JW, Hart WE, Phillips CA, Watson J-P, Dorini G, Jonkergouw P, Kapelan Z, et al (2008) The battle of the water sensor networks (bwsn): A design challenge for engineers and algorithms. J Water Resour Plan Manag 134(6):556\u2013568.","journal-title":"J Water Resour Plan Manag"},{"issue":"17","key":"142_CR33","doi-asserted-by":"publisher","first-page":"7640","DOI":"10.1073\/pnas.0912983107","volume":"107","author":"G Palla","year":"2010","unstructured":"Palla, G, Lov\u00e1sz L, Vicsek T (2010) Multifractal network generator. Proc Natl Acad Sci 107(17):7640.","journal-title":"Proc Natl Acad Sci"},{"key":"142_CR34","unstructured":"Rao, AR, Jana R, Bandyopadhyay S (1996) A markov chain monte carlo method for generating random (0, 1)-matrices with given marginals. Sankhy\u0101: Indian J Stat Ser A:225\u2013242."},{"issue":"1","key":"142_CR35","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1137\/100791142","volume":"9","author":"D Ron","year":"2011","unstructured":"Ron, D, Safro I, Brandt A (2011) Relaxation-based coarsening and multiscale graph organization. Multiscale Modeling Simul 9(1):407\u2013423.","journal-title":"Multiscale Modeling Simul"},{"key":"142_CR36","unstructured":"Rossman, LA (1994) EPANET Users Manual, Cincinnati, OH: US Environmental Protection Agency."},{"issue":"3","key":"142_CR37","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1006\/jagm.1995.1021","volume":"18","author":"J Ruppert","year":"1995","unstructured":"Ruppert, J (1995) A delaunay refinement algorithm for quality 2-dimensional mesh generation. J Algoritm 18(3):548\u2013585.","journal-title":"J Algoritm"},{"issue":"2","key":"142_CR38","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.jda.2010.09.007","volume":"9","author":"I Safro","year":"2011","unstructured":"Safro, I, Temkin B (2011) Multiscale approach for the network compression-friendly ordering. J Discret Algorithm 9(2):190\u2013202.","journal-title":"J Discret Algorithm"},{"issue":"1","key":"142_CR39","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.jalgor.2004.10.004","volume":"60","author":"I Safro","year":"2006","unstructured":"Safro, I, Ron D, Brandt A (2006) Graph minimum linear arrangement by multilevel weighted edge contractions. J Algorithm 60(1):24\u201341.","journal-title":"J Algorithm"},{"key":"142_CR40","first-page":"4","volume":"13","author":"I Safro","year":"2008","unstructured":"Safro, I, Ron D, Brandt A (2008) Multilevel algorithms for linear ordering problems. ACM J Exp Algorithmic 13:4.","journal-title":"ACM J Exp Algorithmic"},{"key":"142_CR41","first-page":"2","volume":"19","author":"I Safro","year":"2015","unstructured":"Safro, I, Sanders P, Schulz C (2015) Advanced coarsening schemes for graph partitioning. ACM J Exp Algorithmics (JEA) 19:2\u20132.","journal-title":"ACM J Exp Algorithmics (JEA)"},{"issue":"5","key":"142_CR42","doi-asserted-by":"publisher","first-page":"056109","DOI":"10.1103\/PhysRevE.85.056109","volume":"85","author":"C Seshadhri","year":"2012","unstructured":"Seshadhri, C, Kolda TG, Pinar A (2012) Community structure and scale-free collections of erdo\u030bs-r\u00e9nyi graphs. Phys Rev E 85(5):056109.","journal-title":"Phys Rev E"},{"key":"142_CR43","doi-asserted-by":"crossref","unstructured":"Shewchuk, JR (1996) Triangle: Engineering a 2d quality mesh generator and delaunay triangulator In: Applied Computational Geometry Towards Geometric Engineering, 203\u2013222.. Springer.","DOI":"10.1007\/BFb0014497"},{"key":"142_CR44","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.envsoft.2013.05.006","volume":"47","author":"R Sitzenfrei","year":"2013","unstructured":"Sitzenfrei, R, M\u00f6derl M, Rauch W (2013) Automatic generation of water distribution systems based on gis data. Environ Model Softw 47:138\u2013147.","journal-title":"Environ Model Softw"},{"key":"142_CR45","unstructured":"Staudt, C, Sazonovs A, Meyerhenke H (2014) Networkit: An interactive tool suite for high-performance network analysis. CoRR, abs\/1403.3005:41."},{"key":"142_CR46","doi-asserted-by":"crossref","unstructured":"Staudt, CL, Hamann M, Safro I, Gutfraind A, Meyerhenke H (2016) Generating scaled replicas of real-world complex networks In: International Workshop on Complex Networks and Their Applications, 17\u201328.. Springer.","DOI":"10.1007\/978-3-319-50901-3_2"},{"issue":"1","key":"142_CR47","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/s41109-017-0054-z","volume":"2","author":"CL Staudt","year":"2017","unstructured":"Staudt, CL, Hamann M, Gutfraind A, Safro I, Meyerhenke H (2017) Generating realistic scaled complex networks. Appl Netw Sci 2(1):36. https:\/\/doi.org\/10.1007\/s41109-017-0054-z .","journal-title":"Appl Netw Sci"},{"key":"142_CR48","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1963190.2063515","volume":"16","author":"L Tabourier","year":"2011","unstructured":"Tabourier, L, Roth C, Cointet J-P (2011) Generating constrained random graphs using multiple edge switches. J Exp Algorithmics 16:1\u201371117115. https:\/\/doi.org\/10.1145\/1963190.2063515 .","journal-title":"J Exp Algorithmics"},{"issue":"3","key":"142_CR49","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1002\/jgt.3190050304","volume":"5","author":"C Thomassen","year":"1981","unstructured":"Thomassen, C (1981) Kuratowski\u2019s theorem. J Graph Theory 5(3):225\u2013241.","journal-title":"J Graph Theory"},{"issue":"2","key":"142_CR50","doi-asserted-by":"publisher","first-page":"249","DOI":"10.4153\/CJM-1963-029-x","volume":"15","author":"WT Tutte","year":"1963","unstructured":"Tutte, WT (1963) A census of planar maps. Canad J Math 15(2):249\u2013271.","journal-title":"Canad J Math"},{"key":"142_CR51","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1155\/2019\/5120581","volume":"2019","author":"J van Lidth de Jeude","year":"2019","unstructured":"van Lidth de Jeude, J, Di Clemente R, Caldarelli G, Saracco F, Squartini T (2019) Reconstructing mesoscale network structures. Complexity 2019:4.","journal-title":"Complexity"},{"key":"142_CR52","doi-asserted-by":"crossref","unstructured":"Wang, Z, Thomas RJ, Scaglione A (2008) Generating random topology power grids In: Hawaii International Conference on System Sciences, Proceedings of the 41st Annual, 183\u2013183.. Springer.","DOI":"10.1109\/HICSS.2008.182"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0142-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41109-019-0142-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0142-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,18]],"date-time":"2023-09-18T09:03:34Z","timestamp":1695027814000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-019-0142-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["142"],"URL":"https:\/\/doi.org\/10.1007\/s41109-019-0142-3","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"3 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Publisher\u2019s Note"}}],"article-number":"46"}}