On String Contact Representations in 3D

Abstract

An axis-aligned string is a simple polygonal path, where each line segment is parallel to an axis in ${\mathbb{R}}^3$. Given a graph $G$, a string contact representation $\Psi$ 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 $\Psi$ is the minimum integer $r$ such that every string in $\Psi$ 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.

References in corpus (2)

• Contact Representations of Sparse Planar Graphs
• Balanced Circle Packings for Planar Graphs