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.1007/978-3-030-39881-1_8

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: Chapter in Book/Report/Conference proceeding › Conference contribution

1 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)
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings
Editors	M. Sohel Rahman, Kunihiko Sadakane, Wing-Kin Sung
Publisher	Springer
Pages	81-93
Number of pages	13
ISBN (Print)	9783030398804
DOIs	https://doi.org/10.1007/978-3-030-39881-1_8
State	Published - 2020
Externally published	Yes
Event	14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020 - Singapore, Singapore Duration: Mar 31 2020 → Apr 2 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12049 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020
Country/Territory	Singapore
City	Singapore
Period	3/31/20 → 4/2/20

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-39881-1_8

Cite this

De Luca, F., Di Giacomo, E., Hong, S. H., Kobourov, S., Lenhart, W., Liotta, G., Meijer, H., Tappini, A., & Wismath, S. (2020). Packing trees into 1-planar graphs. In M. S. Rahman, K. Sadakane, & W.-K. Sung (Eds.), WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings (pp. 81-93). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12049 LNCS). Springer. https://doi.org/10.1007/978-3-030-39881-1_8

Packing trees into 1-planar graphs. / De Luca, Felice; Di Giacomo, Emilio; Hong, Seok Hee et al.
WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings. ed. / M. Sohel Rahman; Kunihiko Sadakane; Wing-Kin Sung. Springer, 2020. p. 81-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12049 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

De Luca, F, Di Giacomo, E, Hong, SH, Kobourov, S, Lenhart, W, Liotta, G, Meijer, H, Tappini, A & Wismath, S 2020, Packing trees into 1-planar graphs. in MS Rahman, K Sadakane & W-K Sung (eds), WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12049 LNCS, Springer, pp. 81-93, 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020, Singapore, Singapore, 3/31/20. https://doi.org/10.1007/978-3-030-39881-1_8

De Luca F, Di Giacomo E, Hong SH, Kobourov S, Lenhart W, Liotta G et al. Packing trees into 1-planar graphs. In Rahman MS, Sadakane K, Sung WK, editors, WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings. Springer. 2020. p. 81-93. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-39881-1_8

De Luca, Felice ; Di Giacomo, Emilio ; Hong, Seok Hee et al. / Packing trees into 1-planar graphs. WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Proceedings. editor / M. Sohel Rahman ; Kunihiko Sadakane ; Wing-Kin Sung. Springer, 2020. pp. 81-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cfa407ecb8b54db0ae0f8c29b49b20a6,

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

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020 ; Conference date: 31-03-2020 Through 02-04-2020",

year = "2020",

doi = "10.1007/978-3-030-39881-1_8",

language = "English (US)",

isbn = "9783030398804",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "81--93",

editor = "Rahman, {M. Sohel} and Kunihiko Sadakane and Wing-Kin Sung",

booktitle = "WALCOM",

}

TY - GEN

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 - 2020

Y1 - 2020

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=85080935057&partnerID=8YFLogxK

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

U2 - 10.1007/978-3-030-39881-1_8

DO - 10.1007/978-3-030-39881-1_8

M3 - Conference contribution

AN - SCOPUS:85080935057

SN - 9783030398804

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 93

BT - WALCOM

A2 - Rahman, M. Sohel

A2 - Sadakane, Kunihiko

A2 - Sung, Wing-Kin

PB - Springer

T2 - 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020

Y2 - 31 March 2020 through 2 April 2020

ER -

Packing trees into 1-planar graphs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this