Do all planar rigid graphs contain a triangle?

50 Views Asked by At

If one looks at rigid rod and joint linkages (such as the Laman graphs) one instantly notices a similarity between them, which is that all of them either contain $K_3$ or something which contains $K_{3,3}$. Of course $K_{3,3}$ is not a planar graph, and therefore no linkage which contains it can be drawn without overlaps. Does any linkages which is rigid and whose graph is planar contain a triangle (i.e. $K_3$)?

1

There are 1 best solutions below

0
On

A planar graph has an average face size of $\frac{2m}{f} = \frac{2m}{m-n+2}$.

A rigid graph has at least $2n-3$ edges (size of a Laman graph), so $m\geq 2n-3$, hence $m-n+2 \geq n-1 > m/2$. We get an average face $\frac{2m}{m-n+2}< 4$, so there is at least a triangle.