On String Contact Representations in 3D
share
An axis-aligned string is a simple polygonal path, where each line segment is parallel to an axis in R^3. Given a graph G, a string contact representation Ψ of G maps the vertices of G to interior disjoint axis-aligned strings, where no three strings meet at a point, and two strings share a common point if and only if their corresponding vertices are adjacent in G. The complexity of Ψ is the minimum integer r such that every string in Ψ is a B_r-string, i.e., a string with at most r bends. While a result of Duncan et al. implies that every graph G with maximum degree 4 has a string contact representation using B_4-strings, we examine constraints on G that allow string contact representations with complexity 3, 2 or 1. We prove that if G is Hamiltonian and triangle-free, then G admits a contact representation where all the strings but one are B_3-strings. If G is 3-regular and bipartite, then G admits a contact representation with string complexity 2, and if we further restrict G to be Hamiltonian, then G has a contact representation, where all the strings but one are B_1-strings (i.e., L-shapes). Finally, we prove some complementary lower bounds on the complexity of string contact representations.
READ FULL TEXT