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
    Commented Sep 25, 2019 at 8:38
  • $\begingroup$ Thanks.. Made an edit that has hopefully fixed the problem $\endgroup$ Commented Sep 25, 2019 at 14:28
  • $\begingroup$ Do nodes have to have disjoint interiors? $\endgroup$
    – Wlod AA
    Commented 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
    Commented 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$ Commented 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
    Commented 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
    Commented Mar 24, 2020 at 13:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .