{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T23:07:08Z","timestamp":1771456028429,"version":"3.50.1"},"publisher-location":"Boston, MA","reference-count":24,"publisher":"Springer US","isbn-type":[{"value":"9780387747583","type":"print"},{"value":"9780387747590","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_483","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:10:42Z","timestamp":1219662642000},"page":"2813-2820","source":"Crossref","is-referenced-by-count":0,"title":["Optimization in Leveled Graphs"],"prefix":"10.1007","author":[{"given":"Petra","family":"Mutzel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"483_CR1_483","first-page":"89","volume":"21A","author":"P. Eades","year":"1986","unstructured":"Eades P, Kelly D (1986) Heuristics for reducing crossings in 2-layered networks. Ars Combin 21A:89\u201398","journal-title":"Ars Combin."},{"key":"483_CR2_483","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"Eades P, Whitesides S (1994) Drawing graphs in two layers. Theoret Comput Sci 131:361\u2013374","journal-title":"Theoret. Computer Sci."},{"key":"483_CR3_483","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01187020","volume":"10","author":"P. Eades","year":"1994","unstructured":"Eades P, Wormald NC (1994) Edge crossings in drawings of bipartite graphs. Algorithmica 10:379\u2013403","journal-title":"Algorithmica"},{"key":"483_CR4_483","unstructured":"Fukuda K (1996) Personal Communication"},{"key":"483_CR5_483","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey MR, Johnson DS (1983) Crossing number is NP-complete. SIAM J Alg Discrete Meth 4:312\u2013316","journal-title":"SIAM J. Alg. Discrete Meth."},{"key":"483_CR6_483","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01582010","volume":"33","author":"M. Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel M, J\u00fcnger M, Reinelt G (1985) Facets of the linear ordering polytope. Math Program 33:43\u201360","journal-title":"Math. Program."},{"key":"483_CR7_483","first-page":"203","volume":"1","author":"F. Harary","year":"1972","unstructured":"Harary F, Schwenk A (1972) A\u00a0new crossing number for bipartite graphs. Utilitas Math 1:203\u2013209","journal-title":"Utilitas Math."},{"key":"483_CR8_483","first-page":"205","volume-title":"Graph Drawing (Proc. GD\u201999). Lecture Notes Computer Sci","author":"P Healy","year":"1999","unstructured":"Healy P, Kuusik A (1999) The vertex-exchange graph: A\u00a0new concept for multi-level crossing minimisation. In: Kratochvil J (ed) Graph Drawing (Proc. GD\u201999). Lecture Notes Computer Sci. Springer, Berlin, pp\u00a0205\u2013216"},{"key":"483_CR9_483","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/3-540-56024-6_5","volume-title":"Combinatorial Pattern Matching, Third Ann. Symp. (CMP, 1992). Lecture Notes Computer Sci","author":"G Jacobson","year":"1992","unstructured":"Jacobson G, Vo K-P (1992) Heaviest increasing\/common subsequence problems. In: Apostolico A, Crochemore M, Galil Z, Manber U (eds) Combinatorial Pattern Matching, Third Ann. Symp. (CMP, 1992). Lecture Notes Computer Sci. Springer, Berlin, pp\u00a052\u201366"},{"key":"483_CR10_483","first-page":"13","volume-title":"Graph Drawing (Proc. GD\u201997). Lecture Notes Computer Sci","author":"M J\u00fcnger","year":"1997","unstructured":"J\u00fcnger M, Lee E, Mutzel P, Odenthal T (1997) A\u00a0polyhedral approach to the multi-layer crossing number problem. In: DiBattista G (ed) Graph Drawing (Proc. GD\u201997). Lecture Notes Computer Sci. Springer, Berlin, pp\u00a013\u201324"},{"key":"483_CR11_483","volume-title":"Graph Drawing (Proc. GD\u201998). Lecture Notes Computer Sci","author":"M J\u00fcnger","year":"1998","unstructured":"J\u00fcnger M, Leipert S, Mutzel P (1998) Level planarity testing in linear time. In: Whitesides S (ed) Graph Drawing (Proc. GD\u201998). Lecture Notes Computer Sci. Springer, Berlin"},{"issue":"1","key":"483_CR12_483","first-page":"1","volume":"1","author":"M. J\u00fcnger","year":"1996","unstructured":"J\u00fcnger M, Mutzel P (1996) 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J\u00a0Graph\n\t  Algorithms Appl (JGAA) 1(1):1\u201325, http:\/\/www.cs.brown.edu\/publications\/jgaa\/","journal-title":"J. Graph Algorithms Appl. (JGAA)"},{"key":"483_CR13_483","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1002\/1097-024X(200009)30:11<1325::AID-SPE342>3.0.CO;2-T","volume":"30","author":"M. J\u00fcnger","year":"2000","unstructured":"J\u00fcnger M, Thienel S (2000) The ABACUS system for branch and cut ad price algorithms in integer programming and combinatorial optimization. Softw Pract Exper 30:1325\u20131352","journal-title":"Software Pract. Exper."},{"key":"483_CR14_483","unstructured":"Kececioglu JD (1991) Exact and approximation algorithms for DNA sequence reconstruction. PhD Thesis, University Arizona"},{"key":"483_CR15_483","doi-asserted-by":"crossref","unstructured":"Kececioglu JD (1993) The maximum weight trace problem in multiple sequence alignment. In: Proc. 4-th Symp. Combinatorial Pattern Matching. Lecture Notes Computer Sci, vol\u00a0684, pp\u00a0106\u2013119","DOI":"10.1007\/BFb0029800"},{"key":"483_CR16_483","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial algorithms for integrated circuit layout","author":"T. Lengauer","year":"1990","unstructured":"Lengauer T (1990) Combinatorial algorithms for integrated circuit layout. Wiley, New York"},{"key":"483_CR17_483","first-page":"318","volume-title":"Graph Drawing (Proc. GD\u201996). Lecture Notes Computer Sci","author":"P Mutzel","year":"1997","unstructured":"Mutzel P (1997) An alternative method to crossing minimization on hierarchical graphs. In: North S (ed) Graph Drawing (Proc. GD\u201996). Lecture Notes Computer Sci. Springer, Berlin, pp\u00a0318\u2013333"},{"key":"483_CR18_483","first-page":"69","volume-title":"Algorithms and Computation; Ninth Internat. Symp. (ISAAC\u201998). Lecture Notes Computer Sci","author":"P Mutzel","year":"1998","unstructured":"Mutzel P, Weiskircher R (1998) Two-layer planarization in graph drawing. In: Chwa K-Y, Ibara O (eds) Algorithms and Computation; Ninth Internat. Symp. (ISAAC\u201998). Lecture Notes Computer Sci. Springer, Berlin, pp\u00a069\u201378"},{"key":"483_CR19_483","doi-asserted-by":"crossref","unstructured":"Reinert K, Lenhof HP, Mutzel P, Mehlhorn K, Kececioglu J (1997) A\u00a0branch-and-cut algorithm for multiple sequence alignment. In: Proc. First Annual Internat. Conf. Computational Molecular Biology (RECOMB\u201997), pp\u00a0241\u2013250","DOI":"10.1145\/267521.267845"},{"key":"483_CR20_483","series-title":"Lecture Notes Computer Sci.","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/3-540-63307-3_48","volume-title":"Workshop Algorithms and Data Structures (WADS\u201997)","author":"F. Shahrokhi","year":"1997","unstructured":"Shahrokhi F, S\u00fdkora O, Sz\u00e9kely LA, Vr\u0165o I (1997) On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem. In: Workshop Algorithms and Data Structures (WADS\u201997). of In: Lecture Notes Computer Sci, vol\u00a01272. Springer, Berlin, pp\u00a055\u201368"},{"key":"483_CR21_483","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"19","author":"J. Spinrad","year":"1987","unstructured":"Spinrad J, Brandst\u00e4dt A, Stewart L (1987) Bipartite permutation graphs. Discrete Appl Math 19:279\u2013292","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"483_CR22_483","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"SMC-11","author":"K. Sugiyama","year":"1981","unstructured":"Sugiyama K, Tagawa S, Toda M (1981) Methods for visual understanding of hierarchical systems. IEEE Trans Syst, Man Cybern SMC-11(2):109\u2013125","journal-title":"IEEE Trans. Syst., Man Cybern."},{"key":"483_CR23_483","volume-title":"Annotated Bibliographies in Combinatorial Optimization","author":"M. Vingron","year":"1997","unstructured":"Vingron M, Lenhof H-P, Mutzel P (1997) Computational molecular biology. In: Maffioli F, Dell'Amico M, Martello S (eds) Annotated Bibliographies in Combinatorial Optimization. Wiley, New York"},{"issue":"2","key":"483_CR24_483","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0092-8240(86)80006-4","volume":"48","author":"M.S. Waterman","year":"1986","unstructured":"Waterman MS, Griggs JR (1986) Interval graphs and maps of DNA. Bull Math Biology 48(2):189\u2013195","journal-title":"Bull. Math. Biology"}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T10:12:14Z","timestamp":1720692734000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_483","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}