Packing trees into 1-planar graphs

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

doi:10.7155/JGAA.00574

Packing trees into 1-planar graphs

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

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

We introduce and study the 1-planar packing problem: Given k graphs with n vertices G₁, …, 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 ≥ 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	https://doi.org/10.7155/JGAA.00574
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

Access to Document

10.7155/JGAA.00574

Cite this

@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",

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",

}

TY - JOUR

T1 - Packing trees into 1-planar graphs

AU - De Luca, Felice

AU - Di Giacomo, Emilio

AU - Hong, Seok Hee

AU - Kobourov, Stephen

AU - Lenhart, William

AU - Liotta, Giuseppe

AU - Meijer, Henk

AU - Tappini, Alessandra

AU - Wismath, Stephen

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85121101794&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85121101794&partnerID=8YFLogxK

U2 - 10.7155/JGAA.00574

DO - 10.7155/JGAA.00574

M3 - Article

AN - SCOPUS:85121101794

SN - 1526-1719

VL - 25

SP - 605

EP - 624

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 2

ER -

Packing trees into 1-planar graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this