{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:34:09Z","timestamp":1725489249065},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540669043"},{"type":"electronic","value":"9783540466482"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46648-7_23","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:29:28Z","timestamp":1186907368000},"page":"225-231","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On 3-Layer Crossings and Pseudo Arrangements"],"prefix":"10.1007","author":[{"given":"Farhad","family":"Shahrokhi","sequence":"first","affiliation":[]},{"given":"Imrich","family":"Vrt\u2019o","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,3]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/21.364865","volume":"25","author":"T. Catarci","year":"1995","unstructured":"Catarci, T.: The assignment heuristics for crossing reduction. IEEE Transactions on Systems, Man and Cybernetics 25 (1995) 515\u2013521","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0898-1221(84)90085-3","volume":"10","author":"F. R. K. Chung","year":"1984","unstructured":"Chung, F. R. K.: On optimal linear arrangements of trees. Computers and Mathematics with Applications 10 (1984) 43\u201360","journal-title":"Computers and Mathematics with Applications"},{"key":"23_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-55808-X_2","volume-title":"In International Symposium on Mathematical Foundations of Computer Sciences","author":"J. D\u00edaz","year":"1992","unstructured":"D\u00edaz, J.: Graph layout problems. In International Symposium on Mathematical Foundations of Computer Sciences. Lecture Notes in Computer Science, Vol. 629. Springer-Verlag, Berlin Heidelberg New York (1992) 14\u201321"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","volume":"4","author":"J. Battista Di","year":"1994","unstructured":"Di Battista, J., Eades, P., Tamassia, R., Tollis, I. G.: Algorithms for drawing graphs: an annotated bibliography. Computational Geometry 4 (1994) 235\u2013282","journal-title":"Computational Geometry"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.: Edge crossings in drawings of bipartite graphs. Algorithmica 11 (1994) 379\u2013403","journal-title":"Algorithmica"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"Eades, P., Whitesides, S.: Drawing graphs in 2 layers. Theoretical Computer Science 131 (1994) 361\u2013374","journal-title":"Theoretical Computer Science"},{"key":"23_CR7","unstructured":"Even, G., Naor, J. S., Rao, S., Schieber, B.: Divide-and-Conquer approximation algorithms via spreading matrices. In 36th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press (1995) 62\u201371"},{"key":"23_CR8","unstructured":"Even, G., Naor, J. S., Rao, S., Schieber, B.: Fast approximate graph partition algorithms. In 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press (1997) 639\u2013648"},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M. R. Garey","year":"1983","unstructured":"Garey, M. R., Johnson, D. S.: Crossing number is NP-complete. SIAM J. Algebraic and Discrete Methods 4 (1983) 312\u2013316","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"23_CR10","unstructured":"Hansen, M.: Approximate algorithms for geometric embeddings in the plane with applications to parallel processing problems. In 30th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press (1989) 604\u2013609"},{"key":"23_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BFb0021817","volume-title":"3rd Symposium on Graph Drawing\u201995","author":"M. J\u00fcnger","year":"1996","unstructured":"J\u00fcnger, M., Mutzel, P.: Exact and heuristic algorithm for 2-layer straight line crossing number. In 3rd Symposium on Graph Drawing\u201995. Lecture Notes in Computer Science, Vol. 1027. Springer-Verlag, BerlinHeidelberg New York (1996) 337\u2013348"},{"key":"23_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-63938-1_46","volume-title":"5th Symposium on Graph Drawing\u201997","author":"M. J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Lee, E. K., Mutzel, P., Odenthal T.: A polyhedral approach to the multi-layer crossing number problem. In 5th Symposium on Graph Drawing\u201997. Lecture Notes in Computer Science, Vol. 1353. Springer-Verlag, Berlin Heidelberg New York (1997) 13\u201324"},{"key":"23_CR13","volume-title":"Complexity issues in VLSI","author":"F. T. Leighton","year":"1983","unstructured":"Leighton, F. T.: Complexity issues in VLSI. MIT Press, Massachusetts (1983)"},{"key":"23_CR14","first-page":"85","volume":"17","author":"M. May","year":"1988","unstructured":"May, M., Szkatula, K.: On the bipartite crossing number. Control and Cybernetics 17 (1988) 85\u201398","journal-title":"Control and Cybernetics"},{"key":"23_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/3-540-62495-3_57","volume-title":"4th Symposium on Graph Drawing\u201996","author":"P. Mutzel","year":"1997","unstructured":"Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. In 4th Symposium on Graph Drawing\u201996. Lecture Notes in Computer Science, Vol. 1190. Springer-Verlag, Berlin Heidelberg New York (1997) 318\u2013333"},{"key":"23_CR16","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"Pach, J., Agarwal, K.: Combinatorial Geometry. John Wiley & Sons Inc., New York (1995)"},{"key":"23_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-63938-1_67","volume-title":"5th Symposium on Graph Drawing\u201997","author":"H. Purchase","year":"1997","unstructured":"Purchase, H.: Which aesthetics has the greatest effect on human understanding? In 5th Symposium on Graph Drawing\u201997. Lecture Notes in Computer Science, Vol. 1353. Springer-Verlag, Berlin Heidelberg New York (1997) 248\u2013261"},{"key":"23_CR18","unstructured":"Rao, S., Richa, A.:, New approximation techniques for some ordering problems. In: 9th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press (1998) 211\u2013225"},{"key":"23_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-63307-3_48","volume-title":"Workshop on Algorithms and Data Structures\u201997","author":"F. Shahrokhi","year":"1997","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L. A., Vrt\u2019o, I.: On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem. In Workshop on Algorithms and Data Structures\u201997. Lecture Notes in Computer Science, Vol. 1272. Springer-Verlag, Berlin Heidelberg New York (1997) 55\u201368 Extended version will appear in SIAM Journal on Computing as: On bipartite drawings and the linear arrangement problem."},{"key":"23_CR20","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L.A., and Vrt\u2019o, I.: Crossing number problems: bounds and applications. In: B\u00e1r\u00e1ny, I., and B\u00f6r\u00f6czky, K. (eds): Intuitive Geometry. Bolyai Society Mathematical Studies, Vol 6. Akad\u00e9mia Kiad\u00f3, Budapest (1997) 179\u2013206"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical systems structures. IEEE Transactions on Systems, Man and Cybernetics 11 (1981) 109\u2013125","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"23_CR22","first-page":"502","volume":"7","author":"J. Warfield","year":"1977","unstructured":"Warfield, J.: Crossing theory and hierarchy mapping. IEEE Transactions on Systems, Man and Cybernetics 7 (1977) 502\u2013523","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"23_CR23","first-page":"15","volume-title":"Selected Topics in Graph Theory","author":"A. T. White","year":"1978","unstructured":"White, A. T., and Beineke, L. W.: Topological graph theory. In: L. W. Beineke, L. W., and R. J. Wilson, R. J. (eds.): Selected Topics in Graph Theory. Academic Press, New York (1978) 15\u201350"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46648-7_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T17:15:24Z","timestamp":1585934124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46648-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540669043","9783540466482"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-46648-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"3 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}