{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T06:38:31Z","timestamp":1712471911876},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-2002-001907FP6-021235-2"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"\n We consider classical linear-time planar separator algorithms, determining for a given planar graph a small subset of its nodes whose removal divides the graph into two components of similar size. These algorithms are based on planar separator theorems, which guarantee separators of size\n O<\/jats:italic>\n (\u221a\n n<\/jats:italic>\n ) and remaining components of size at most 2\n n<\/jats:italic>\n \/3 (where\n n<\/jats:italic>\n denotes the number of nodes in the graph). In this article, we present a comprehensive experimental study of the classical algorithms applied to a large variety of graphs, where our main goal is to find separators that do not only satisfy upper bounds, but also possess other desirable characteristics with respect to separator size and component balance. We achieve this by investigating a number of specific alternatives for the concrete implementation and fine-tuning of certain parts of the classical algorithms. It is also shown that the choice of several parameters influences the separation quality considerably. Moreover, we propose as planar separators the usage of fundamental cycles, whose size is at most twice the diameter of the graph: For graphs of small diameter, the guaranteed bound is better than the\n O<\/jats:italic>\n (\u221a\n n<\/jats:italic>\n ) bounds, and it turns out that this simple strategy almost always outperforms the other algorithms, even for graphs with large diameter.\n <\/jats:p>","DOI":"10.1145\/1498698.1571635","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":6,"title":["Engineering planar separator algorithms"],"prefix":"10.1145","volume":"14","author":[{"given":"Martin","family":"Holzer","sequence":"first","affiliation":[{"name":"KIT, Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Frank","family":"Schulz","sequence":"additional","affiliation":[{"name":"KIT, Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"KIT, Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Grigorios","family":"Prasinos","sequence":"additional","affiliation":[{"name":"CTI & University of Patras, Patras, Greece"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[{"name":"CTI & University of Patras, Patras, Greece"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00072-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1210588"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191198768"},{"key":"e_1_2_1_4_1","unstructured":"Ashcraft C. and Liu J. W. H. 1996. Applications of the Dulmage-Mendelsohn decomposition and network flow to graph bisection improvement. Tech. rep. CS-96-05 Department of Computer Science York University North York Ontario Canada. http:\/\/www.cs.yorku.ca\/techreports\/1996\/CS-96-05.html. Ashcraft C. and Liu J. W. H. 1996. Applications of the Dulmage-Mendelsohn decomposition and network flow to graph bisection improvement. Tech. rep. CS-96-05 Department of Computer Science York University North York Ontario Canada. http:\/\/www.cs.yorku.ca\/techreports\/1996\/CS-96-05.html."},{"key":"e_1_2_1_5_1","unstructured":"Bourke P. 1992. Sphere generation. http:\/\/astronomy.swin.edu.au\/pbourke\/modelling\/sphere\/. Bourke P. 1992. Sphere generation. http:\/\/astronomy.swin.edu.au\/pbourke\/modelling\/sphere\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603022"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050082"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 1st Annual Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Eppstein D.","unstructured":"Eppstein , D. , Italiano , G. F. , Tamassia , R. , Tarjan , R. E. , Westbrook , J. , and Yung , M . 1990. Maintenance of a minimum spanning forest in a dynamic planar graph . In Proceedings of the 1st Annual Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, 1--11. Eppstein, D., Italiano, G. F., Tamassia, R., Tarjan, R. E., Westbrook, J., and Yung, M. 1990. Maintenance of a minimum spanning forest in a dynamic planar graph. In Proceedings of the 1st Annual Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, 1--11."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00130"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1076"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_56"},{"key":"e_1_2_1_14_1","volume-title":"The Design and Analysis of Algorithms","author":"Kozen D.","unstructured":"Kozen , D. 1992. The Design and Analysis of Algorithms . Springer , Berlin . Kozen, D. 1992. The Design and Analysis of Algorithms. Springer, Berlin."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_16_1","first-page":"615","article-title":"Applications of a planar separator theorem","volume":"9","author":"Lipton R.","year":"1980","unstructured":"Lipton , R. and Tarjan , R. E. 1980 . Applications of a planar separator theorem . J. Comput. 9 , 615 -- 627 . Lipton, R. and Tarjan, R. E. 1980. Applications of a planar separator theorem. J. Comput. 9, 615--627.","journal-title":"J. Comput."},{"key":"e_1_2_1_17_1","first-page":"177","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton R. J.","year":"1979","unstructured":"Lipton , R. J. and Tarjan , R. E. 1979 . A separator theorem for planar graphs . J. Appl. Math. 36 , 2, 177 -- 189 . Lipton, R. J. and Tarjan, R. E. 1979. A separator theorem for planar graphs. J. Appl. Math. 36, 2, 177--189.","journal-title":"J. Appl. Math."},{"key":"e_1_2_1_18_1","volume-title":"Data Structures and Algorithms 1, 2, and 3","author":"Mehlhorn K.","unstructured":"Mehlhorn , K. 1984. Data Structures and Algorithms 1, 2, and 3 . Springer , Berlin . Mehlhorn, K. 1984. Data Structures and Algorithms 1, 2, and 3. Springer, Berlin."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808703"},{"key":"e_1_2_1_20_1","unstructured":"Näher S. and Mehlhorn K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press. http:\/\/www.algorithmic-solutions.com. Näher S. and Mehlhorn K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press. http:\/\/www.algorithmic-solutions.com."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the National Academy of Sciences. National Academy of Sciences","author":"Ozkan S. B.","unstructured":"Ozkan , S. B. , Wu , G. A. , Chodera , J. D. , and Dill , K. A . 2007. Protein folding by zipping and assembly . In Proceedings of the National Academy of Sciences. National Academy of Sciences , Washington, DC. Ozkan, S. B., Wu, G. A., Chodera, J. D., and Dill, K. A. 2007. Protein folding by zipping and assembly. In Proceedings of the National Academy of Sciences. National Academy of Sciences, Washington, DC."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237404"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1571635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T07:29:24Z","timestamp":1672298964000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1571635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":22,"alternative-id":["10.1145\/1498698.1571635"],"URL":"http:\/\/dx.doi.org\/10.1145\/1498698.1571635","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}