{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:07:12Z","timestamp":1758823632614},"reference-count":22,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4607,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a graph <jats:italic>G = (V, E)<\/jats:italic>, the graph planarization problem is to find a largest subset <jats:italic>F<\/jats:italic> of <jats:italic>E<\/jats:italic>, such that <jats:italic>H<\/jats:italic> = (<jats:italic>V, F<\/jats:italic>) is planar. It is known to be NP\u2010complete. This problem is of interest in automatic graph drawing, in facilities layout, and in the design of printed circuit boards and integrated circuits. We present a two\u2010phase heuristic for solving the planarization problem. The first phase devises a clever ordering of the vertices of the graph on a single line and the second phase tries to find the maximal number of nonintersecting edges that can be drawn above or below this line. Extensive empirical results show that this heuristic outperforms its competitors. \u00a9 1994 by John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/net.3230240203","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T17:22:04Z","timestamp":1178990524000},"page":"69-73","source":"Crossref","is-referenced-by-count":30,"title":["An efficient graph planarization two\u2010phase heuristic"],"prefix":"10.1002","volume":"24","author":[{"given":"Olivier","family":"Goldschmidt","sequence":"first","affiliation":[]},{"given":"Alexan","family":"Takvorian","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"issue":"4","key":"e_1_2_1_3_2","first-page":"681","article-title":"Finding a maximum weight independent set of a circle graph","volume":"74","author":"Asano T.","year":"1991","journal-title":"IEICE Trans."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020206"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"e_1_2_1_7_2","unstructured":"J.Cai X.Han andR.Tarjan An O(mlogn)\u2010time algorithm for the maximal planar subgraph problem. Technical Report CS\u2010TR\u2010309\u201091 Dept. of Computer Science Princeton University Princeton NJ (1991)."},{"key":"e_1_2_1_8_2","first-page":"436","volume-title":"Incremental planarity testing","author":"Di Battista G.","year":"1989"},{"key":"e_1_2_1_9_2","volume-title":"Graph Algorithms","author":"Even S.","year":"1979"},{"key":"e_1_2_1_10_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030305"},{"key":"e_1_2_1_12_2","unstructured":"O.GoldschmidtandA.Takvorian On finding a maximum weight independent set of a circle graph. Technical Report ORP93\/01 Graduate Program in Operations Research. University of Texas Austin TX (1993)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0483(87)90017-X"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.21845"},{"key":"e_1_2_1_16_2","unstructured":"G.Kant An O(n2) maximal planarization algorithm based on PQ\u2010trees. Technical Report RUU\u2010CS\u201092\u201003 Dept. of Computer Science Utrecht University Utrecht The Netherlands (1992)."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout. Teubner. Stuttgart","author":"Lengauer T.","year":"1990"},{"key":"e_1_2_1_18_2","unstructured":"P. C.LiuandR. C.Geldmacher On the deletion of non\u2010planar edges of a graph. Proceedings of the 10th South\u2010East Conference on Combinatorics Graph Theory and Computing. Boca Raton. FL (1977)727\u2013738."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410006028X"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.31548"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.245.4923.1221"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.103509"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/21.87055"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230240203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230240203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T14:38:45Z","timestamp":1698158325000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230240203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["10.1002\/net.3230240203"],"URL":"https:\/\/doi.org\/10.1002\/net.3230240203","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}