{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:35:54Z","timestamp":1725525354844},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642002014"},{"type":"electronic","value":"9783642002021"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00202-1_22","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T02:34:01Z","timestamp":1234233241000},"page":"250-261","source":"Crossref","is-referenced-by-count":8,"title":["Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings"],"prefix":"10.1007","author":[{"given":"Tamara","family":"Mchedlidze","sequence":"first","affiliation":[]},{"given":"Antonios","family":"Symvonis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/3-540-62495-3_34","volume-title":"Graph Drawing","author":"M. Alzohairi","year":"1997","unstructured":"Alzohairi, M., Rival, I.: Series-parallel planar ordered sets have pagenumber two. In: North, S.C. (ed.) GD 1996. LNCS, vol.\u00a01190, pp. 11\u201324. Springer, Heidelberg (1997)"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00383444","volume":"8","author":"G. Brightwell","year":"1991","unstructured":"Brightwell, G., Winkler, P.: Counting linear extensions. Order\u00a08, 225\u2013242 (1991)","journal-title":"Order"},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(84)90002-7","volume":"7","author":"M. Chein","year":"1984","unstructured":"Chein, M., Habib, M.: Jump number of dags having dilworth number 2. Discrete Applied Math.\u00a07, 243\u2013250 (1984)","journal-title":"Discrete Applied Math."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Cogis, O., Habib, M.: Nombre de sauts et graphes series-paralleles. In: RAIRO Inf. Th., vol.\u00a013, pp. 3\u201318 (1979)","DOI":"10.1051\/ita\/1979130100031"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00383598","volume":"1","author":"C.J. Colbourn","year":"1985","unstructured":"Colbourn, C.J., Pulleyblank, W.R.: Minimizing setups in ordered sets of fixed width. Order\u00a01, 225\u2013229 (1985)","journal-title":"Order"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1090\/S0002-9939-1982-0660592-3","volume":"85","author":"D. Duffus","year":"1982","unstructured":"Duffus, D., Rival, I., Winkler, P.: Minimizing setups for cycle-free orders sets. Proc. of the American Math. Soc.\u00a085, 509\u2013513 (1982)","journal-title":"Proc. of the American Math. Soc."},{"issue":"2-3","key":"22_CR7","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G. Di Battista","year":"1988","unstructured":"Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci.\u00a061(2-3), 175\u2013198 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"22_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comgeo.2004.04.002","volume":"30","author":"E. Di Giacomo","year":"2005","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Comput. Geom. Theory Appl.\u00a030(1), 1\u201323 (2005)","journal-title":"Comput. Geom. Theory Appl."},{"key":"22_CR9","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"issue":"2-3","key":"22_CR10","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00044-X","volume":"92","author":"H. Enomoto","year":"1999","unstructured":"Enomoto, H., Miyauchi, M.S., Ota, K.: Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph. Discrete Appl. Math.\u00a092(2-3), 149\u2013155 (1999)","journal-title":"Discrete Appl. Math."},{"key":"22_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/800119.803884","volume-title":"STOC 1974: Proceedings of the sixth annual ACM symposium on Theory of computing","author":"M.R. Garey","year":"1974","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: STOC 1974: Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47\u201363. ACM, New York (1974)"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-540-77120-3_17","volume-title":"Algorithms and Computation","author":"F. Giordano","year":"2007","unstructured":"Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A.: Computing upward topological book embeddings of upward planar digraphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 172\u2013183. Springer, Heidelberg (2007)"},{"key":"22_CR14","volume-title":"Graph Theory","author":"F. Harary","year":"1972","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading (1972)"},{"issue":"4","key":"22_CR15","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1137\/S0895480193252380","volume":"10","author":"L.S. Heath","year":"1997","unstructured":"Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of posets. SIAM J. Discrete Math.\u00a010(4), 599\u2013625 (1997)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"22_CR16","doi-asserted-by":"publisher","first-page":"1588","DOI":"10.1137\/S0097539795291550","volume":"28","author":"L.S. Heath","year":"1999","unstructured":"Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs: Part\u00a0II. SIAM J. Comput.\u00a028(5), 1588\u20131626 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"22_CR17","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539795280287","volume":"28","author":"L.S. Heath","year":"1999","unstructured":"Heath, L.S., Pemmaraju, S.V., Trenk, A.N.: Stack and queue layouts of directed acyclic graphs: Part\u00a0I. SIAM J. Comput.\u00a028(4), 1510\u20131539 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2-3","key":"22_CR18","first-page":"129","volume":"70","author":"Z.A. Karejan","year":"1980","unstructured":"Karejan, Z.A., Mosesjan, K.M.: The hamiltonian completion number of a digraph (in Russian). Akad. Nauk Armyan. SSR Dokl.\u00a070(2-3), 129\u2013132 (1980)","journal-title":"Akad. Nauk Armyan. SSR Dokl."},{"issue":"2-3","key":"22_CR19","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0012-365X(87)90008-2","volume":"63","author":"D. Kelly","year":"1987","unstructured":"Kelly, D.: Fundamentals of planar ordered sets. Discrete Math.\u00a063(2-3), 197\u2013216 (1987)","journal-title":"Discrete Math."},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00383398","volume":"8","author":"J. Mitas","year":"1991","unstructured":"Mitas, J.: Tackling the jump number of interval orders. Order\u00a08, 115\u2013132 (1991)","journal-title":"Order"},{"key":"22_CR21","unstructured":"Mchedlidze, T., Symvonis, A.: Optimal acyclic hamiltonian path completion for outerplanar triangulated st-digraphs (with application to upward topological book embeddings), arXiv:0807.2330, http:\/\/arxiv.org\/abs\/0807.2330"},{"issue":"3","key":"22_CR22","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF00563521","volume":"6","author":"R. Nowakowski","year":"1989","unstructured":"Nowakowski, R., Parker, A.: Ordered sets, pagenumbers and planarity. Order\u00a06(3), 209\u2013218 (1989)","journal-title":"Order"},{"key":"22_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/11537311_39","volume-title":"Fundamentals of Computation Theory","author":"A. Ono","year":"2005","unstructured":"Ono, A., Nakano, S.: Constant Time Generation of Linear Extensions. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 445\u2013453. Springer, Heidelberg (2005)"},{"issue":"2","key":"22_CR24","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/S0097539791202647","volume":"23","author":"G. Pruesse","year":"1994","unstructured":"Pruesse, G., Ruskey, F.: Generating linear extensions fast. SIAM Journal on Computing\u00a023(2), 373\u2013386 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR25","unstructured":"Pulleyblank, W.R.: On minimizing setups in precedence constrained scheduling. Report 81105-OR (1981)"},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"Rival, I.: Optimal linear extensions by interchanging chains. vol.\u00a089, pp. 387\u2013394 (Novomber 1983)","DOI":"10.2307\/2045481"},{"key":"22_CR27","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF00383200","volume":"7","author":"A. Sharary","year":"1991","unstructured":"Sharary, A., Zaguia, N.: On minimizing jumps for ordered sets. Order\u00a07, 353\u2013359 (1991)","journal-title":"Order"},{"key":"22_CR28","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF00340778","volume":"3","author":"G. Steiner","year":"1987","unstructured":"Steiner, G., Stewart, L.K.: A linear algorithm to find the jump number of 2-dimensional bipartite partial orders. Order\u00a03, 359\u2013367 (1987)","journal-title":"Order"},{"issue":"4","key":"22_CR29","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/BF01840401","volume":"5","author":"R. Tamassia","year":"1990","unstructured":"Tamassia, R., Preparata, F.P.: Dynamic maintenance of planar digraphs, with applications. Algorithmica\u00a05(4), 509\u2013527 (1990)","journal-title":"Algorithmica"},{"key":"22_CR30","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach a visibility representation of planar graphs. Discrete & Computational Geometry\u00a01, 321\u2013341 (1986)","journal-title":"Discrete & Computational Geometry"},{"key":"22_CR31","unstructured":"Wigderson, A.: The complexity of the hamiltonian circuit problem for maximal planar graphs. Technical Report TR-298, Princeton University, EECS Department (1982)"},{"issue":"1","key":"22_CR32","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M. Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci.\u00a038(1), 36\u201367 (1989)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00202-1_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T19:07:38Z","timestamp":1558120058000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00202-1_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642002014","9783642002021"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00202-1_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}