Packing Trees into 1-planar Graphs

DOI10.1007/978-3-030-39881-1_8MaRDI QIDQ6328555arXivFDO

Authors Felice De Luca, Emilio Di Giacomo, Seok-Hee Hong, Stephen G. Kobourov, William Lenhart, Giuseppe Liotta, Alessandra Tappini, S. Wismath

Publication date 5 November 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-39881-1_8

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

arXiv classification

cs.CGmath.CO

Abstract: 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 $ngeq12$ vertices admits a 1-planar packing, while such a packing does not exist if $nleq10$.

This page was built for publication: Packing Trees into 1-planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328555)