Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (with any arbitrary translation or rotation) such that:
- Every pair of triangles share a finite number points on their perimeter (can't have collinear, touching sides) and do not intersect
- If two triangles are adjacent in $G$, they share a vertex (a stronger restriction than just sharing any point on the perimeter)
Here are two valid non-isomorphic arrangements for $K_3$:
$K_n$ has no arrangement for $n>5$.
$\forall n \geq 3$, $C_n$ has an arrangement as a "necklace" of triangles. One such arrangement for $C_4$ is shown:
What is the complexity of this problem? What algorithm could you use to recognize arrangeable graphs (or at least a sketch of how it would work)? Would this algorithm be able to provide a solution rather than just assert its existence?
One observation is that if $G$ is arrangeable, all of its subgraphs are as well.