{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:26:15Z","timestamp":1747189575487,"version":"3.40.5"},"reference-count":26,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"name":"Natural Science Foundation of Changsha City","award":["kq2202247"],"award-info":[{"award-number":["kq2202247"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:p> Given an [Formula: see text]-vertex graph [Formula: see text] with a fixed linear ordering of [Formula: see text] and two integers [Formula: see text], the problem FIXED-ORDER BOOK DRAWING with few crossings per edge asks whether or not [Formula: see text] admits a [Formula: see text]-page book drawing where the maximum number of crossings per edge can be upper bounded by the number [Formula: see text]. This problem was posed as an open question by Bhore et\u00a0al. (J. Graph Algorithms Appl. 2020). In this paper, we study this problem from the viewpoint of parameterized complexity, in particular, we develop fixed-parameter tractable algorithms for it. More specifically, we show that this problem parameterized by both the bound number [Formula: see text] of crossings per edge and the vertex cover number [Formula: see text] of the input graph admits an algorithm with running time in [Formula: see text], and this problem parameterized by both the bound number [Formula: see text] of crossings per edge and the pathwidth [Formula: see text] of the vertex ordering admits an algorithm with running time in [Formula: see text]. Our results provide a specific answer to Bhore et al.\u2019s question. <\/jats:p>","DOI":"10.1142\/s0129054123500168","type":"journal-article","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T06:41:26Z","timestamp":1695969686000},"page":"551-577","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Algorithms for Fixed-Order Book Drawing with Few Crossings Per Edge"],"prefix":"10.1142","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6965-7989","authenticated-orcid":false,"given":"Jingui","family":"Huang","sequence":"first","affiliation":[{"name":"College of Information Science and Engineering, Hunan Provincial Key Laboratory of Intelligent, Computing and Language Information Processing, Hunan Normal University, Changsha, P. R. China"},{"name":"Hunan Xiangjiang Artificial Intelligence Academy, Changsha, P. R. China"}]},{"given":"Jie","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Information Science and Engineering, Hunan Provincial Key Laboratory of Intelligent, Computing and Language Information Processing, Hunan Normal University, Changsha, P. R. China"},{"name":"Information Technology Institute of China, Railway Guangzhou Group Co., Ltd., P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2686-5240","authenticated-orcid":false,"given":"Yunlong","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Information Science and Engineering, Hunan Provincial Key Laboratory of Intelligent, Computing and Language Information Processing, Hunan Normal University, Changsha, P. R. China"},{"name":"Hunan Xiangjiang Artificial Intelligence Academy, Changsha, P. R. China"}]},{"given":"Guang","family":"Xiao","sequence":"additional","affiliation":[{"name":"College of Information Science and Engineering, Hunan Provincial Key Laboratory of Intelligent, Computing and Language Information Processing, Hunan Normal University, Changsha, P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1516-0480","authenticated-orcid":false,"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,9,29]]},"reference":[{"key":"S0129054123500168BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.03.029"},{"key":"S0129054123500168BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45803-7_18"},{"key":"S0129054123500168BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03841-4_30"},{"key":"S0129054123500168BIB004","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00526"},{"key":"S0129054123500168BIB005","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00597"},{"key":"S0129054123500168BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.07.009"},{"key":"S0129054123500168BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/11809678_53"},{"key":"S0129054123500168BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"S0129054123500168BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00314-6"},{"key":"S0129054123500168BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-006-4294-9"},{"key":"S0129054123500168BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.05.009"},{"key":"S0129054123500168BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00256-5_10"},{"key":"S0129054123500168BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.03.001"},{"key":"S0129054123500168BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-35802-0_29"},{"key":"S0129054123500168BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"S0129054123500168BIB016","doi-asserted-by":"publisher","DOI":"10.1137\/0601025"},{"key":"S0129054123500168BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-0010-x"},{"key":"S0129054123500168BIB018","series-title":"LNCS","first-page":"307","volume-title":"Proc. GD\u201919","volume":"11904","author":"Hlin\u011bn\u00fd P.","year":"2019"},{"key":"S0129054123500168BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90234-M"},{"key":"S0129054123500168BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-73915-1_19"},{"key":"S0129054123500168BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.04.021"},{"key":"S0129054123500168BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-021-3405-x"},{"key":"S0129054123500168BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-93176-6_38"},{"key":"S0129054123500168BIB024","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054123410022"},{"key":"S0129054123500168BIB025","doi-asserted-by":"publisher","DOI":"10.1109\/12.46286"},{"key":"S0129054123500168BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035832"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123500168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T03:06:06Z","timestamp":1720494366000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123500168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,29]]},"references-count":26,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10.1142\/S0129054123500168"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123500168","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,9,29]]}}}