<p>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:</p>

<ul>
<li>Every pair of triangles share a finite number points on their perimeter (can't have collinear, touching sides) and do not intersect</li>
<li>If two triangles are adjacent in $G$, they share a vertex (a stronger restriction than just sharing any point on the perimeter)</li>
</ul>

<p>Here are two valid non-isomorphic arrangements for $K_3$:</p>

<p><img src="https://i.sstatic.net/Wc9HY.png" height="150" alt="Solutions for K_3"></p>

<p>$K_n$ has no arrangement for $n&gt;5$.</p>

<p>$\forall n \geq 3$, $C_n$ has an arrangement as a "necklace" of triangles.  One such arrangement for $C_4$ is shown:</p>

<p><img src="https://i.sstatic.net/ByTwh.png" height="170" alt="Arrangement for C_4"></p>

<p>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?</p>

<p>One observation is that if $G$ is arrangeable, all of its subgraphs are as well.</p>

CC BY-SA 3.0
2016-11-02T23:06:11.860Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-11-03T00:03:44.030Z
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.
David Eppstein
CC BY-SA 3.0
2016-11-03T00:13:49.987Z
I clarified that the interiors can't intersect and fixed some spelling errors.
pimlu
CC BY-SA 3.0
2016-11-03T03:36:52.110Z
I suspect that the wobbly logic engine technique of http://link.springer.com/10.1007%2F3-540-63938-1_69 should be able to prove this NP-hard (maybe even when your graph is a tree), but there are a lot of details to work out, and the right result is not NP-hard but ∃R-complete.
David Eppstein
CC BY-SA 3.0
2016-11-03T15:40:41.320Z
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).
Gamow
CC BY-SA 3.0
2016-11-03T20:37:12.633Z
Oops, I should have said n>5.  I should have played around with it more.  Thanks for catching that.
pimlu
<graph-theory><graph-algorithms><np-hardness><cg.comp-geom>
Triangle arrangement problem
pimlu
# Triangle arrangement problem

(Asked by: username_0 on 2016-11-02)

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](https://i.sstatic.net/Wc9HY.png)

$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](https://i.sstatic.net/ByTwh.png)

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.

**Tags:** graph-theory, graph-algorithms, np-hardness, cg.comp-geom

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: I clarified that the interiors can't intersect and fixed some spelling errors.  
> **username_2**: I suspect that the wobbly logic engine technique of http://link.springer.com/10.1007%2F3-540-63938-1_69 should be able to prove this NP-hard (maybe even when your graph is a tree), but there are a lot of details to work out, and the right result is not NP-hard but ∃R-complete.  
> **username_3**: 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).  
> **username_0**: Oops, I should have said n>5.  I should have played around with it more.  Thanks for catching that.  

---

## 0 answers

