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.
Original language | English (US) |
---|---|
Pages (from-to) | 605-624 |
Number of pages | 20 |
Journal | Journal of Graph Algorithms and Applications |
Volume | 25 |
Issue number | 2 |
DOIs | |
State | Published - 2021 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Computer Science Applications
- Geometry and Topology
- Computational Theory and Mathematics