9
$\begingroup$

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$:

Solutions 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:

Arrangement for C_4

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ A natural first question is whether there is a difference between the two kinds of embeddings. I don't have a rigorous proof of this, but after playing around with it, I think the following graph can be embedded the first way, but not the second: it's a seven vertex graph formed by taking a 6-cycle, and connecting the seventh vertex to a pair of opposite vertices in the cycle. $\endgroup$ – Andrew Morgan Nov 2 '16 at 23:06
  • $\begingroup$ Can the interiors intersect? ​ ​ $\endgroup$ – user6973 Nov 2 '16 at 23:14
  • 2
    $\begingroup$ This looks closely related to recognizing unit distance graphs, which is NP-hard. Without the interior-intersection condition it would be exactly the same as recognizing unit distance graphs with the extra property that every edge belongs to exactly one triangle, but I don't know the status of that special case. $\endgroup$ – David Eppstein Nov 3 '16 at 0:03
  • $\begingroup$ I clarified that the interiors can't intersect and fixed some spelling errors. $\endgroup$ – lakantu Nov 3 '16 at 0:13
  • 3
    $\begingroup$ You write that "K_n has no arrangement for n>3". But we can arrange five triangles with just one common vertex, and represent K_5 (and K_4). $\endgroup$ – Gamow Nov 3 '16 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.