@article{21b4556f97824df8804c44a2fa339d83,
title = "Packing trees into 1-planar graphs",
abstract = "We introduce and study the 1-planar packing problem: Given k graphs with n vertices G1, …, Gk, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each Gi is a tree and k = 3. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with n ≥ 12 vertices admits a 1-planar packing, while such a packing does not exist if n ≤ 10.",
author = "{De Luca}, Felice and {Di Giacomo}, Emilio and Hong, {Seok Hee} and Stephen Kobourov and William Lenhart and Giuseppe Liotta and Henk Meijer and Alessandra Tappini and Stephen Wismath",
note = "Funding Information: A preliminary version of this paper appears in the Proceedings of WALCOM 2020 [12]. This work started at the Bertinoro Workshop on Graph Drawing 2019 and it is partially supported by: (i) MIUR, grant 20174LF3T8 “AHeAD: efficient Algorithms for HArnessing networked Data”; (ii) Dip. di Ingeg-neria dell{\textquoteright}Universit{\`a} degli Studi di Perugia, grants RICBA18WD “Algoritmi e sistemi di analisi visuale di reti complesse e di grandi dimensioni” and RICBA19FM “Modelli, algoritmi e sistemi per la visualizzazione di grafi e reti”; (iii) NFS, grants CCF-1740858, CCF-1712119, DMS-1839274, DMS-1839307; (iv) ARC Discovery grant. Funding Information: This work started at the Bertinoro Workshop on Graph Drawing 2019 and it is partially supported by: (i) MIUR, grant 20174LF3T8 ?AHeAD: efficient Algorithms for HArnessing networked Data?; (ii) Dip. di Ingeg-neria dell?Universit? degli Studi di Perugia, grants RICBA18WD ?Algoritmi e sistemi di analisi visuale di reti complesse e di grandi dimensioni? and RICBA19FM ?Modelli, algoritmi e sistemi per la visualizzazione di grafi e reti?; (iii) NFS, grants CCF-1740858, CCF-1712119, DMS-1839274, DMS-1839307; (iv) ARC Discovery grant. Publisher Copyright: {\textcopyright} 2021, Brown University. All rights reserved.",
year = "2021",
doi = "10.7155/JGAA.00574",
language = "English (US)",
volume = "25",
pages = "605--624",
journal = "Journal of Graph Algorithms and Applications",
issn = "1526-1719",
publisher = "Brown University",
number = "2",
}