3
$\begingroup$

Background: Given a convex region C. One can define a graph corresponding to a planar arrangement of non overlapping congruent 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 such 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 copies of 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 - or 5 at each node.

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.

Further thought: If one alters the above definition of the graph corresponding to an infinite non-overlapping layout with congruent copies of some convex C as: "nodes are C units as before but an edge connects two units if they even touch at a point", then, how can we upper bound the average degree of the graph for any convex C? (Note: as per this new definition, the graph won't be planar).

$\endgroup$
5
  • 2
    $\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$
    – user44143
    Sep 25, 2019 at 8:38
  • $\begingroup$ Thanks.. Made an edit that has hopefully fixed the problem $\endgroup$ Sep 25, 2019 at 14:28
  • $\begingroup$ Do nodes have to have disjoint interiors? $\endgroup$
    – Wlod AA
    Mar 24, 2020 at 7:59
  • 1
    $\begingroup$ What is the relation between "copies"? Are they just isometric? Or are they parallel shifts one of another? ... $\endgroup$
    – Wlod AA
    Mar 24, 2020 at 8:04
  • $\begingroup$ To my knowledge, an infinite planar graph corresponding to a an infinte layout of mutually congruent polygonal regions cannot have arbitrarily high average degree (with each region a node and an edge connecting only regions which share some finite portion of their boundary). The average degree should be bounded by 6. Yes, by 'copies' I meant 'related by isometries'. And yes, the polygonal regions do not overlap so their interiors are disjoint. $\endgroup$ Mar 25, 2020 at 21:04

1 Answer 1

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$
2
  • 3
    $\begingroup$ I doubt the first statement. See the triakis tiling. Three triangles meet at a point, but no right angles. $\endgroup$
    – M. Winter
    Mar 24, 2020 at 8:10
  • $\begingroup$ You're right, this can also happen if the triangle has a $120^\circ$ degree angle. $\endgroup$
    – domotorp
    Mar 24, 2020 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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