{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:12:56Z","timestamp":1763467976478,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2007,2,9]]},"abstract":"<jats:p>A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques that can be used to speed up the implementation of graph partitioning algorithms and improve the partition quality. In particular, we consider planar graphs with costs and weights on the vertices, where weights are used to estimate the sizes of the partitions and costs are used to estimate the size of the separator. We show that in these graphs one can always find a small cost separator (consisting of vertices or edges) that partitions the graph into components of bounded weight. We describe implementations of the partitioning algorithms and discuss results of our experiments.<\/jats:p>","DOI":"10.1145\/1187436.1210588","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":5,"title":["Partitioning planar graphs with costs and weights"],"prefix":"10.1145","volume":"11","author":[{"given":"Lyudmil","family":"Aleksandrov","sequence":"first","affiliation":[{"name":"Bulgarian Academy of Sciences, Sofia, Bulgaria"}]},{"given":"Hristo","family":"Djidjev","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos, NM, USA"}]},{"given":"Hua","family":"Guo","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, ON, CANADA"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, ON, CANADA"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194272183"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/BF02570715","article-title":"Linear-size nonobtuse triangulation of polygons","volume":"14","author":"Bern M.","year":"1995","unstructured":"Bern , M. , Mitchell , S. , and Ruppert , J. 1995 . Linear-size nonobtuse triangulation of polygons . Discrete Computational Geometry 14 , 411 -- 428 . Bern, M., Mitchell, S., and Ruppert, J. 1995. Linear-size nonobtuse triangulation of polygons. Discrete Computational Geometry 14, 411--428.","journal-title":"Discrete Computational Geometry"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","article-title":"A framework for solving vlsi graph layout problems","volume":"28","author":"Bhatt S. N.","year":"1984","unstructured":"Bhatt , S. N. and Leighton , F. T. 1984 . A framework for solving vlsi graph layout problems . J. Computer and System Sciences 28 , 300 -- 343 . Bhatt, S. N. and Leighton, F. T. 1984. A framework for solving vlsi graph layout problems. J. Computer and System Sciences 28, 300--343.","journal-title":"J. Computer and System Sciences"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/175276.175279"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1013"},{"key":"e_1_2_1_6_1","first-page":"643","article-title":"A separator theorem","volume":"34","author":"Djidjev H. N.","year":"1981","unstructured":"Djidjev , H. N. 1981 . A separator theorem . Compt. Rend. Acad. Bulg. Sci. 34 , 643 -- 645 . Djidjev, H. N. 1981. A separator theorem. Compt. Rend. Acad. Bulg. Sci. 34, 643--645.","journal-title":"Compt. Rend. Acad. Bulg. Sci."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s004530010031","article-title":"Partitioning planar graphs with vertex costs: Algorithms and applications","volume":"28","author":"Djidjev H. N.","year":"2000","unstructured":"Djidjev , H. N. 2000 . Partitioning planar graphs with vertex costs: Algorithms and applications . Algorithmica 28 , 1, 51 -- 75 . Djidjev, H. N. 2000. Partitioning planar graphs with vertex costs: Algorithms and applications. Algorithmica 28, 1, 51--75.","journal-title":"Algorithmica"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s004530010043","article-title":"Improved algorithms for dynamic shortest paths","volume":"28","author":"Djidjev H. N.","year":"2000","unstructured":"Djidjev , H. N. , Pantziou , G. E. , and Zaroliagis , C. D. 2000 . Improved algorithms for dynamic shortest paths . Algorithmica 28 , 4, 367 -- 389 . Djidjev, H. N., Pantziou, G. E., and Zaroliagis, C. D. 2000. Improved algorithms for dynamic shortest paths. Algorithmica 28, 4, 367--389.","journal-title":"Algorithmica"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0913067"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0605032","article-title":"A separator theorem for chordal graphs","volume":"5","author":"Gilbert J. R.","year":"1984","unstructured":"Gilbert , J. R. , Rose , D. J. , and Edenbrandt , A. 1984 a. A separator theorem for chordal graphs . SIAM J. Alg. Disc. Meth. , 5 , 306 -- 313 . Gilbert, J. R., Rose, D. J., and Edenbrandt, A. 1984a. A separator theorem for chordal graphs. SIAM J. Alg. Disc. Meth., 5, 306--313.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"e_1_2_1_14_1","volume-title":"Tech. Rep. CSL-93-15","author":"Gilbert J. R.","year":"1993","unstructured":"Gilbert , J. R. , Ng , E. G. , and Peyton , B. W . 1993 . Separators and structure prediction in sparse orthogonal factorization. Tech. Rep. CSL-93-15 , Palo Alto Research Center, Xerox Corporation, California . Gilbert, J. R., Ng, E. G., and Peyton, B. W. 1993. Separators and structure prediction in sparse orthogonal factorization. Tech. Rep. CSL-93-15, Palo Alto Research Center, Xerox Corporation, California."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594275339"},{"key":"e_1_2_1_16_1","volume-title":"Proc. 24th Annual ACM Symposium on Theory of Computing. 507--516","author":"Goodrich M. T.","year":"1992","unstructured":"Goodrich , M. T. 1992 . Planar separators and parallel polygon triangulation . In Proc. 24th Annual ACM Symposium on Theory of Computing. 507--516 . 10.1145\/129712.129762 Goodrich, M. T. 1992. Planar separators and parallel polygon triangulation. In Proc. 24th Annual ACM Symposium on Theory of Computing. 507--516. 10.1145\/129712.129762"},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. SAND94-2692, Sandia National Laboratories.","author":"Hendrickson B.","year":"1994","unstructured":"Hendrickson , B. and Leland , R . 1994 . The chaco user's guide---version 2.0. Tech. Rep. SAND94-2692, Sandia National Laboratories. Hendrickson, B. and Leland, R. 1994. The chaco user's guide---version 2.0. Tech. Rep. SAND94-2692, Sandia National Laboratories."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_19_1","volume-title":"METIS: A family of multilevel partitioning algorithms. EE\/CS","author":"Karypis G.","year":"1998","unstructured":"Karypis , G. 1998 . METIS: A family of multilevel partitioning algorithms. EE\/CS , UMN , Minneapolis, USA. \/www-users.cs.umn.edu\/~karypis\/metis\/. Karypis, G. 1998. METIS: A family of multilevel partitioning algorithms. EE\/CS, UMN, Minneapolis, USA. \/www-users.cs.umn.edu\/~karypis\/metis\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Kernighan B. W. and Lin S. 1970. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal 291--307.  Kernighan B. W. and Lin S. 1970. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal 291--307.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"volume-title":"Foundations of Computing","author":"Leiserson C. E.","key":"e_1_2_1_21_1","unstructured":"Leiserson , C. E. 1983. Area efficient VLSI computation . In Foundations of Computing . MIT Press , Cambridge, MA . Leiserson, C. E. 1983. Area efficient VLSI computation. In Foundations of Computing. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","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 . SIAM J. Appl. Math. 36 , 177 -- 189 . Lipton, R. J. and Tarjan, R. E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177--189.","journal-title":"SIAM J. Appl. Math."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","article-title":"Applications of a planar separator theorem","volume":"9","author":"Lipton R. J.","year":"1980","unstructured":"Lipton , R. J. and Tarjan , R. E. 1980 . Applications of a planar separator theorem . SIAM J. Comput. 9 , 615 -- 627 . Lipton, R. J. and Tarjan, R. E. 1980. Applications of a planar separator theorem. SIAM J. Comput. 9, 615--627.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_24_1","volume-title":"Tech. Rep. CRPC-TR-94504","author":"Maini H. S.","year":"1994","unstructured":"Maini , H. S. , Mehrotra , K. G. , Mohan , C. K. , and Ranka , S . 1994 . Genetic algorithms for graph partitioning and incremental graph partitioning. Tech. Rep. CRPC-TR-94504 , Rice University . Maini, H. S., Mehrotra, K. G., Mohan, C. K., and Ranka, S. 1994. Genetic algorithms for graph partitioning and incremental graph partitioning. Tech. Rep. CRPC-TR-94504, Rice University."},{"key":"e_1_2_1_25_1","unstructured":"Mehlhorn K. and Naher S. 1999. LEDA a platform for combinatorial and geometric computing. Cambridge University Press Cambridge.   Mehlhorn K. and Naher S. 1999. LEDA a platform for combinatorial and geometric computing. Cambridge University Press Cambridge."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256294"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"e_1_2_1_28_1","unstructured":"Schloegel K. Karypis G. and Kumar V. 2000. Graph partitioning for high performance scientific simulations. In CRPC Parallel Computing Handbook J. D. et al. Ed. Morgan Kaufmann San Mates CA in press.   Schloegel K. Karypis G. and Kumar V. 2000. Graph partitioning for high performance scientific simulations. In CRPC Parallel Computing Handbook J. D. et al. Ed. Morgan Kaufmann San Mates CA in press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593255135"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1210588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1210588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1210588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":28,"alternative-id":["10.1145\/1187436.1210588"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1210588","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}