k-Planar Placement and Packing of Δ-Regular Caterpillars

DOI10.1142/S0129054123420042MaRDI QIDQ6066468zbMATH OpenOpenAlexFDO

Authors Carla Binucci, Emilio Di Giacomo, Michael Kaufmann, Giuseppe Liotta, Alessandra Tappini

Publication date 16 November 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.01226

zbMATH Keywords

\(k\)-planaritybeyond planaritygraph packinggraph placement

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: This paper studies a emph{packing} problem in the so-called beyond-planar setting, that is when the host graph is ``almost-planar in some sense. Precisely, we consider the case that the host graph is $k$-planar, i.e., it admits an embedding with at most $k$ crossings per edge, and focus on families of $Delta$-regular caterpillars, that are caterpillars whose non-leaf vertices have the same degree $Delta$. We study the dependency of $k$ from the number $h$ of caterpillars that are packed, both in the case that these caterpillars are all isomorphic to one another (in which case the packing is called emph{placement}) and when they are not. We give necessary and sufficient conditions for the placement of $h$ $Delta$-regular caterpillars and sufficient conditions for the packing of a set of $Delt{a}_1$-, $Delt{a}_2$-, $dots$, $Delt{a}_h$-regular caterpillars such that the degree $Delt{a}_i$ and the degree $Delt{a}_j$ of the non-leaf vertices can differ from one caterpillar to another, for $1leqi,jleqh$, $ieqj$.

Recommendations

• Packing trees into 1-planar graphs
• Packing trees into 1-planar graphs
• On the packing of two copies of a caterpillar in its third power
• The planar tree packing theorem
• The planar tree packing theorem

Cites work

• 1-planarity of complete multipartite graphs
• A note on k-placeable graphs
• An annotated bibliography on 1-planarity
• Beyond Clustered Planar Graphs
• Drawing graphs. Methods and models
• Edge disjoint placement of graphs
• Edge-disjoint placement of three trees
• Efficient generation of different topological representations of graphs beyond-planarity
• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3771651 (Why is no real title available?)
• scientific article; zbMATH DE number 3604921 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• On topological graphs with at most four crossings per edge
• Packing four copies of a tree into a complete graph
• Packing plane spanning trees and paths in complete geometric graphs
• Packing three copies of a tree into a complete graph
• Packing trees into 1-planar graphs
• Packing trees into planar graphs
• Packing two graphs of order n having total size at most 2n-2
• Packings of graphs and applications to computational complexity
• Planar packing of binary trees
• Planar packing of trees and spider trees
• The planar tree packing theorem
• Triple placement of graphs

Cited in

(1)

• The caterpillar-packing polytope

This page was built for publication: k-Planar Placement and Packing of Δ-Regular Caterpillars

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