Geodesic
Packing Trees into 1-planar Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020 , Tome 25 (2021) no. 2, pp. 605-624.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ 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 \geq 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \leq 10$.
DOI : 10.7155/jgaa.00574
Keywords: graph drawing, graph packing, 1-planar packing, 1-planarity 
@article{JGAA_2021_25_2_a1,
     author = {Felice De Luca and Emilio Di Giacomo and Seok-Hee Hong and Stephen Kobourov and William Lenhart and Giuseppe Liotta and Henk Meijer and Alessandra Tappini and Stephen Wismath},
     title = {Packing {Trees} into 1-planar {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {605--624},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2021},
     doi = {10.7155/jgaa.00574},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00574/}
}
TY  - JOUR
AU  - Felice De Luca
AU  - Emilio Di Giacomo
AU  - Seok-Hee Hong
AU  - Stephen Kobourov
AU  - William Lenhart
AU  - Giuseppe Liotta
AU  - Henk Meijer
AU  - Alessandra Tappini
AU  - Stephen Wismath
TI  - Packing Trees into 1-planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 605
EP  - 624
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00574/
DO  - 10.7155/jgaa.00574
LA  - en
ID  - JGAA_2021_25_2_a1
ER  - 
%0 Journal Article
%A Felice De Luca
%A Emilio Di Giacomo
%A Seok-Hee Hong
%A Stephen Kobourov
%A William Lenhart
%A Giuseppe Liotta
%A Henk Meijer
%A Alessandra Tappini
%A Stephen Wismath
%T Packing Trees into 1-planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2021
%P 605-624
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00574/
%R 10.7155/jgaa.00574
%G en
%F JGAA_2021_25_2_a1
Felice De Luca; Emilio Di Giacomo; Seok-Hee Hong; Stephen Kobourov; William Lenhart; Giuseppe Liotta; Henk Meijer; Alessandra Tappini; Stephen Wismath. Packing Trees into 1-planar Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 14th International Conference and  Workshops on Algorithms and Computation, WALCOM 2020
					, Tome 25 (2021) no. 2, pp. 605-624. doi : 10.7155/jgaa.00574. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00574/

Cité par Sources :