{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:47:55Z","timestamp":1759063675325},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,7,1]],"date-time":"1996-07-01T00:00:00Z","timestamp":836179200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,7]]},"DOI":"10.1007\/bf02086607","type":"journal-article","created":{"date-parts":[[2005,8,15]],"date-time":"2005-08-15T00:28:41Z","timestamp":1124065721000},"page":"33-59","source":"Crossref","is-referenced-by-count":42,"title":["Maximum planar subgraphs and nice embeddings: Practical layout tools"],"prefix":"10.1007","volume":"16","author":[{"given":"M.","family":"J\u00fcnger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02086607_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"Booth, K. S., and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity testing using PQ-tree algorithms,Journal of Computer and System Sciences 13 (1976), 335\u2013379.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02086607_CR2","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1137\/0222068","volume":"22","author":"J. Cai","year":"1993","unstructured":"Cai, J., X. Han, and R. E. Tarjan, An O(m logn)-time algorithm for the maximal planar subgraph problem,SIAM Journal on Computing 22 (1993), 1142\u20131162.","journal-title":"SIAM Journal on Computing"},{"key":"BF02086607_CR3","unstructured":"Cimikowski, R. J., An empirical analysis of graph planarization heuristics, unpublished manuscript, Computer Science Dept, Montana State University (1992)."},{"key":"BF02086607_CR4","series-title":"Lecture Notes in Mathematics, Vol. 952","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BFb0061982","volume-title":"Combinatorial Mathematics IX","author":"P. Eades","year":"1982","unstructured":"Eades P., L. R. Foulds, and J. W. Giffin. An efficient heuristic for identifying a maximum weight planar subgraph,Combinatorial Mathematics IX, Lecture Notes in Mathematics, Vol. 952, Springer-Verlag, Berlin (1982), pp. 239\u2013251."},{"key":"BF02086607_CR5","volume-title":"Universitext","author":"L. R. Foulds","year":"1992","unstructured":"Foulds, L. R., Graph theory applications,Universitext, Springer-Verlag, New York (1992)."},{"key":"BF02086607_CR6","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1057\/jors.1976.174","volume":"27","author":"L. R. Foulds","year":"1976","unstructured":"Foulds, L. R., and R. W. Robinson, A strategy for solving the plant layout problem,Operational Research Quaterly 27 (1976), 845\u2013855.","journal-title":"Operational Research Quaterly"},{"key":"BF02086607_CR7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1080\/00207547808929997","volume":"16","author":"L. R. Foulds","year":"1978","unstructured":"Foulds, L. R., and R. W. Robinson, Graph theoretic heuristics for the plant layout problem,International Journal of Production Research 16 (1978), 27\u201337.","journal-title":"International Journal of Production Research"},{"key":"BF02086607_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979)."},{"key":"BF02086607_CR9","volume-title":"Technical Report ORP91-01","author":"O. Goldschmidt","year":"1992","unstructured":"Goldschmidt, O., and A. Takvorian, An Efficient Graph Planarization Two-Phase Heuristic, Technical Report ORP91-01, Dept. of Mech. Engr., University of Texas, Austin (1992)."},{"key":"BF02086607_CR10","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","volume":"32","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., M. J\u00fcnger, and G. Reinelt, A cutting plane algorithm for the linear ordering problem,Operations Research 32 (1984), 1195\u20131220.","journal-title":"Operations Research"},{"key":"BF02086607_CR11","unstructured":"Himsolt, M., Konzeption und Implementierung von Grapheneditoren, Dissertation, Universit\u00e4t Passau (1993)."},{"key":"BF02086607_CR12","unstructured":"Himsolt, M., Personal communication (1993)."},{"key":"BF02086607_CR13","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., and R. E. Tarjan, Efficient planarity testing,Journal of the Association for Computing Machinery 21 (1974), 549\u2013568.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF02086607_CR14","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1109\/43.21845","volume":"8","author":"R. Jayakumar","year":"1989","unstructured":"Jayakumar, R., K. Thulasiraman, and M. N. S. Swamy, O(n 2) algorithms for graph planarization,IEEE Transactions on Computer-aided Design 8 (1989), 257\u2013267.","journal-title":"IEEE Transactions on Computer-aided Design"},{"key":"BF02086607_CR15","unstructured":"J\u00fcnger, M., G. Reinelt, and S. Thienel, Provably Good Solutions for the Traveling Salesman Problem, Rep. No. 92.114, Angewandte Mathematik und Informatik, Universit\u00e4t zu K\u00f6ln (1992)."},{"key":"BF02086607_CR16","unstructured":"Kant, G., An O(n 2) Maximal Planarization Algorithm Based on PQ-trees, Technical Report RUU-CS-92-03, Dept. of Computer Science, Utrecht University (1992)."},{"key":"BF02086607_CR17","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1287\/mnsc.38.4.594","volume":"38","author":"J. Leung","year":"1992","unstructured":"Leung, J., A new graph-theoretic heuristic for facility layout,Management Science 38 (1992), 594\u2013605.","journal-title":"Management Science"},{"key":"BF02086607_CR18","unstructured":"Liu, P. C., and R. C. Geldmacher, On the deletion of nonplanar edges of a graph,Proc. 10th. S.-E. Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, FL (1977), pp. 727\u2013738."},{"key":"BF02086607_CR19","unstructured":"Martin, A., Personal communication (1993)."},{"key":"BF02086607_CR20","unstructured":"Mutzel, P., A Fast Linear Time Embedding Algorithm Based on the Hopcroft-Tarjan Planarity Test, Report No. 92.107, Angewandte Mathematik und Informatik, Universit\u00e4t zu K\u00f6ln (1992)."},{"key":"BF02086607_CR21","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M. W. Padberg","year":"1991","unstructured":"Padberg, M. W., and G. Rinaldi, A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems,SIAM Review 33 (1991), 60\u2013100.","journal-title":"SIAM Review"},{"key":"BF02086607_CR22","volume-title":"Handbook on Operations Research and Management Sciences: Networks","author":"W. R. Pulleyblank","year":"1989","unstructured":"Pulleyblank, W. R., Polyhedral combinatorics, in G. L. Nemhauser, A. H. G. Rinnoy Kan, and M. J. Todd (eds.),Handbook on Operations Research and Management Sciences: Networks, North-Holland, Amsterdam (1989)."},{"key":"BF02086607_CR23","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/21.87055","volume":"18","author":"R. Tamassia","year":"1988","unstructured":"Tamassia, R., G. Di Battista, and C. Batini, Automatic graph drawing and readability of diagrams,IEEE Transactions on Systems, Man, and Cybernetics 18 (1988), 61\u201379.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02086607.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02086607\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02086607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T14:00:54Z","timestamp":1557842454000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02086607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,7]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,7]]}},"alternative-id":["BF02086607"],"URL":"https:\/\/doi.org\/10.1007\/bf02086607","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,7]]}}}