{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:24Z","timestamp":1740133944261,"version":"3.37.3"},"reference-count":29,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","funder":[{"name":"Universit\u00e0 degli Studi di Perugia, Dipartimento di Ingegneria","award":["RICBA20EDG"],"award-info":[{"award-number":["RICBA20EDG"]}]},{"name":"Universit\u00e0 degli Studi di Perugia, Dipartimento di Ingegneria","award":["RICBA21LG"],"award-info":[{"award-number":["RICBA21LG"]}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Universit\u00e0 degli Studi di Perugia, Dipartimento di Ingegneria","award":["RICBA22CB"],"award-info":[{"award-number":["RICBA22CB"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p> This paper studies a packing problem in the so-called beyond-planar setting, that is when the host graph is \u201calmost-planar\u201d in some sense. Precisely, we consider the case that the host graph is [Formula: see text]-planar, i.e., it admits an embedding with at most [Formula: see text] crossings per edge, and focus on families of [Formula: see text]-regular caterpillars, that are caterpillars whose non-leaf vertices have the same degree [Formula: see text]. We study the dependency of [Formula: see text] from the number [Formula: see text] of caterpillars that are packed, both in the case that these caterpillars are all isomorphic to one another (in which case the packing is called placement) and when they are not. We give necessary and sufficient conditions for the placement of [Formula: see text] [Formula: see text]-regular caterpillars and sufficient conditions for the packing of a set of [Formula: see text]-, [Formula: see text]-, [Formula: see text], [Formula: see text]-regular caterpillars such that the degree [Formula: see text] and the degree [Formula: see text] of the non-leaf vertices can differ from one caterpillar to another, for [Formula: see text], [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054123420042","type":"journal-article","created":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T07:51:26Z","timestamp":1684828286000},"page":"875-902","source":"Crossref","is-referenced-by-count":0,"title":["k-Planar Placement and Packing of \u0394-Regular Caterpillars"],"prefix":"10.1142","volume":"34","author":[{"given":"Carla","family":"Binucci","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria, Universit\u00e0 degli Studi di Perugia, via G. Duranti 93, 06125, Perugia, Italy"}]},{"given":"Emilio","family":"Di Giacomo","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria, Universit\u00e0 degli Studi di Perugia, via G. Duranti 93, 06125, Perugia, Italy"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[{"name":"Wilhelm-Schickard Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, Sand 13, 72076, T\u00fcbingen, Germany"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria, Universit\u00e0 degli Studi di Perugia, via G. Duranti 93, 06125, Perugia, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9192-2067","authenticated-orcid":false,"given":"Alessandra","family":"Tappini","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria, Universit\u00e0 degli Studi di Perugia, via G. Duranti 93, 06125, Perugia, Italy"}]}],"member":"219","published-online":{"date-parts":[[2023,5,22]]},"reference":[{"key":"S0129054123420042BIB001","doi-asserted-by":"crossref","first-page":"101574","DOI":"10.1016\/j.comgeo.2019.101574","volume":"85","author":"Ackerman E.","year":"2019","journal-title":"Computational Geometry"},{"key":"S0129054123420042BIB002","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.ipl.2017.04.006","volume":"124","author":"Aichholzer O.","year":"2017","journal-title":"Information Processing Letters"},{"key":"S0129054123420042BIB003","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2018.03.005","volume":"723","author":"Angelini P.","year":"2018","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"S0129054123420042BIB004","doi-asserted-by":"crossref","first-page":"573","DOI":"10.7155\/jgaa.00531","volume":"24","author":"Angelini P.","year":"2020","journal-title":"Journal of Graph Algorithms and Applications"},{"volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","year":"1999","author":"Battista G. D.","key":"S0129054123420042BIB005"},{"issue":"2","key":"S0129054123420042BIB006","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0095-8956(78)90030-8","volume":"25","author":"Bollob\u00e1s B.","year":"1978","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"S0129054123420042BIB007","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1016\/j.dam.2011.11.014","volume":"160","author":"Czap J.","year":"2012","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"S0129054123420042BIB008","doi-asserted-by":"crossref","first-page":"605","DOI":"10.7155\/jgaa.00574","volume":"25","author":"De Luca F.","year":"2021","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"S0129054123420042BIB009","first-page":"4:1","volume":"52","author":"Didimo W.","year":"2019","journal-title":"ACM Comput. Surv."},{"key":"S0129054123420042BIB010","first-page":"29","volume-title":"Theory of Graphs and its Applications, Proc. Sympos. Smolenice","author":"Erd\u00f6s P.","year":"1964"},{"key":"S0129054123420042BIB011","first-page":"95","volume-title":"Proceedings of the 21st Annual Canadian Conference on Computational Geometry","author":"Frati F.","year":"2009"},{"issue":"6","key":"S0129054123420042BIB012","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.ipl.2008.11.002","volume":"109","author":"Frati F.","year":"2009","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"S0129054123420042BIB013","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1002\/jgt.10042","volume":"40","author":"Garc\u00eda Olaverri A.","year":"2002","journal-title":"Journal of Graph Theory"},{"key":"S0129054123420042BIB014","series-title":"LNCS","first-page":"353","volume-title":"WADS 2013","volume":"8037","author":"Geyer M.","year":"2013"},{"issue":"2","key":"S0129054123420042BIB015","first-page":"109","volume":"8","author":"Geyer M.","year":"2017","journal-title":"JoCG"},{"key":"S0129054123420042BIB016","first-page":"463","volume-title":"Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976)","volume":"1","author":"Gy\u00e1rf\u00e1s A.","year":"1978"},{"key":"S0129054123420042BIB017","first-page":"323","volume":"59","author":"Haler S. P.","year":"2014","journal-title":"Australas. J Comb."},{"issue":"01","key":"S0129054123420042BIB018","volume":"11","author":"Hedetniemi S.","year":"1981","journal-title":"Ars Combinatoria"},{"key":"S0129054123420042BIB019","doi-asserted-by":"crossref","DOI":"10.1007\/978-981-15-6533-5","volume-title":"Beyond Planar Graphs","author":"Hong S.","year":"2020"},{"key":"S0129054123420042BIB020","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-44969-8","volume-title":"Drawing Graphs: Methods and Models","volume":"2025","author":"Kaufmann M.","year":"2001"},{"key":"S0129054123420042BIB021","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.cosrev.2017.06.002","volume":"25","author":"Kobourov S. G.","year":"2017","journal-title":"Computer Science Review"},{"issue":"6","key":"S0129054123420042BIB022","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1006\/eujc.1996.0047","volume":"17","author":"Mah\u00e9o M.","year":"1996","journal-title":"Eur. J. Comb."},{"key":"S0129054123420042BIB023","doi-asserted-by":"publisher","DOI":"10.1142\/5648"},{"volume-title":"22nd European Workshop on Computational Geometry","year":"2006","author":"Oda Y.","key":"S0129054123420042BIB024"},{"issue":"3","key":"S0129054123420042BIB025","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0095-8956(78)90005-9","volume":"25","author":"Sauer N.","year":"1978","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"S0129054123420042BIB026","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF01787731","volume":"6","author":"Teo S. K.","year":"1990","journal-title":"Graphs Comb."},{"issue":"2","key":"S0129054123420042BIB027","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/eujc.1993.1018","volume":"14","author":"Wang H.","year":"1993","journal-title":"European Journal of Combinatorics"},{"issue":"1","key":"S0129054123420042BIB028","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/BF01195330","volume":"9","author":"Wozniak M.","year":"1993","journal-title":"Graphs and Combinatorics"},{"issue":"22","key":"S0129054123420042BIB029","doi-asserted-by":"crossref","first-page":"2634","DOI":"10.1016\/j.disc.2011.08.002","volume":"311","author":"Zak A.","year":"2011","journal-title":"Discret. Math."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123420042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T04:54:34Z","timestamp":1698296074000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123420042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,22]]},"references-count":29,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.1142\/S0129054123420042"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123420042","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,5,22]]}}}