Search

This paper studies a 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 Δ -regular caterpillars, that are caterpillars whose non-leaf vertices have the same degree Δ. 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 placement) and when they are not. We give necessary and sufficient conditions for the placement of h Δ -regular caterpillars and sufficient conditions for the packing of a set of Δ 1 -, Δ 2 -, ... , Δ h -regular caterpillars such that the degree Δ i and the degree Δ j of the non-leaf vertices can differ from one caterpillar to another, for 1 ≤ i , j ≤ h , i ≠ j. [ABSTRACT FROM AUTHOR]

The edge-length ratio of a planar straight-line drawing of a graph is the maximum ratio between the lengths of any two of its edges. When the edges to be considered in the ratio are required to be adjacent, the ratio is called local edge-length ratio. The (local) edge-length ratio of a graph G is the infimum over all (local) edge-length ratios in the planar straight-line drawings of G. We prove that the edge-length ratio of the n -vertex 2-trees is Ω (log n) , which proves a conjecture by Lazard et al. [TCS 770, 2019, pp. 88–94] and complements an upper bound by Borrazzo and Frati [JoCG 11(1), 2020, pp. 137–155]. We also prove that every partial 2-tree admits a planar straight-line drawing whose local edge-length ratio is at most 4 + for any arbitrarily small > 0. [ABSTRACT FROM AUTHOR]