Packing Trees into 1-planar Graphs

Authors

  • Felice De Luca
  • Emilio Di Giacomo
  • Seok-Hee Hong
  • Stephen Kobourov
  • William Lenhart
  • Giuseppe Liotta
  • Henk Meijer
  • Alessandra Tappini
  • Stephen Wismath

DOI:

https://doi.org/10.7155/jgaa.00574

Keywords:

graph drawing , graph packing , 1-planar packing , 1-planarity

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 n12 vertices admits a 1-planar packing, while such a packing does not exist if n10.

Downloads

Downloads

Published

2021-11-01

How to Cite

De Luca, F., Di Giacomo, E., Hong, S.-H., Kobourov, S., Lenhart, W., Liotta, G., … Wismath, S. (2021). Packing Trees into 1-planar Graphs. Journal of Graph Algorithms and Applications, 25(2), 605–624. https://doi.org/10.7155/jgaa.00574