3
$\begingroup$

Background: Given a convex region C. One can define a graph corresponding to a planar arrangement of copies of C - each unit C is a node and an edge connects it to another node iff the two C units share some finite length of boundary. Such a graph is necessarily planar. As is well known, the average degree of a planar graph can at most be 6.

Given any triangle, the intuitive (parallelogram based) tilings of the plane with it seem to correspond to graphs (defined above) with average degree = 3 or 4 - there appears a gap between these values and the maximum average degree of a planar graph (6).

Question: Can one have an infinite planar arrangement (not necessarily a tiling) with some triangle where the average degree of the corresponding graph is between 4 and 6?

Note: With squares, it is easy to form a tiling with the corresponding graph having degree 6 at every node - the highest possible average degree.

Generalization: Given a convex 2D shape C, not necessarily one that tiles. Suppose one is also somehow given the planar arrangement(s) with infinite copies of C that maximizes the average degree of the corresponding graph. How good are these arrangements at achieving max packing density? And analogous questions may be raised in 3D.

$\endgroup$
  • $\begingroup$ The use of the word “any” in the question is confusing, especially since it occurs twice. Words like “every” and “some” are clearer. $\endgroup$ – Matt F. Sep 25 at 8:38
  • $\begingroup$ Thanks.. Made an edit that has hopefully fixed the problem $\endgroup$ – Nandakumar R Sep 25 at 14:28
0
$\begingroup$

No, this is not possible. Notice that the degree of a dual-vertex (a point, where at least three triangles meet) can be $3$ if and only if the triangle is right angle, and the right angle meets with another right angle and a side. Practically, at every dual-vertex we need some triangles to meet whose respective angles sum to at least 180$^\circ$. (Only 180$^\circ$, because we can also have the side of another triangle covering the other 180$^\circ$ range.) But every triangle can contribute $3$ terms, summing to exactly 180$^\circ$ to such sums. In an equation, we have that if there are $n$ triangles and $f$ dual-vertices, then $3n\le \sum_v deg(v)\le 3n+f$ where the possible $+f$ comes from the sides at some vertices. So from Euler's formula, denoting the number of edges by $m$, we have $2m=\sum_v deg(v)\le 3n+f=2n+m+2$, from which the average degree in the primal graph is $2m/n\le 4+4/n$. This solves the problem for tilings, while for finite arrangements you have to be a bit more careful with the counting, like consider dual-vertices that neighbor the infinite face to reduce the $+f$ to just $+(f-3)$ or so.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.