Abstract 1 Introduction 2 Results 3 Future Work References

Graph Tiles

Oswin Aichholzer ORCID TU Graz, Austria Robert Ganian ORCID TU Wien, Austria Phillip Keldenich ORCID TU Braunschweig, Germany Maarten Löffler ORCID Utrecht University, The Netherlands Gert Meijer ORCID Stenden University of Applied Sciences, Leeuwarden, The Netherlands Alexandra Weinberger ORCID FernUniversität in Hagen, Germany Carola Wenk ORCID Tulane University, New Orleans, LA, USA
Abstract

We define a graph tile to be a unit square (or more generally, a polygon) on which a piece of a graph has been drawn/embedded; in particular, it may have vertices in its interior, edges connecting those vertices, or half-edges that extend to the boundary of the tile. In a graph tiling problem, we are given as input a set of graph tiles, with multiplicities, and the output is an arrangement of those tiles forming a graph of larger area. We focus on a simple tile set: unit square tiles with a central vertex and either a half-edge or no half-edge on each side. Up to symmetry this gives us six different types. We characterize which multiplicities are compatible for sets of at most three different tiles.

Keywords and phrases:
graph tiles
Category:
Poster Abstract
Copyright and License:
[Uncaptioned image] © Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer, Alexandra Weinberger, and Carola Wenk; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Computational geometry
Acknowledgements:
This research was initiated at Dagstuhl Seminar 25201, “Computational Geometry”. We thank the organizers and all participants for a stimulating atmosphere and valuable discussions. This research was made possible by the Centre for Unusual Collaborations (CUCo) under the project “Going Off the Grid”.
DOI:
10.4230/LIPIcs.GD.2025.51
Event:
33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)
Editors:
Vida Dujmović and Fabrizio Montecchiani
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Motivation from material engineering.

Irregular architected materials have outstanding mechanical properties, like high stiffness-to-weight ratios and energy absorption, but their rational design is still an open challenge. The recent development of computer-aided virtual growth algorithms (VGAs) has emerged as a new promising venue that allows the generation of architected materials with tailorable mechanical properties [3]. VGAs rely on a specific set of simplified tiles that are assembled on a predefined grid, following a precise set of connectivity rules. Depending on the relative concentration of different tiles, different materials architectures and patterns can be generated, leading in turn to completely different mechanical (and functional) material properties [2, 4].

Figure 1: A graph tiling problem and possible solution.

The graph tiling problem.

Underlying this engineering challenge lies a mathematical problem. We define a graph tile to be a unit square (or more generally, a polygon) on which a piece of a graph has been drawn/embedded; in particular, it may have vertices in its interior, edges connecting those vertices, or half-edges that extend to the boundary of the tile. In a graph tiling problem, we are given as input a set of graph tiles, with multiplicities, and the output is an arrangement of those tiles into a larger area. Figure 1 shows an example. We can then ask for the output graph to satisfy certain properties, or to optimize over certain criteria, e.g. connectedness, shortest paths, stretch factor, tortuosity, etc. In order to effectively inform VGAs, it is necessary to understand the relation between tile sets and the achievable graph properties in a resulting graph tiling.

Contribution.

In this work, we initiate the fundamental study into this area by considering one of the simplest possible sets of tiles: square tiles, with a single vertex in the center, and which do or do not have a half-edge extending to each of the four sides. Taking symmetries into account, this gives us six distinct tiles, see Figure 2. These tiles have been previously identified as the simplest set which is rich enough to encode meaningful material design [4].

Figure 2: The six different types of tiles considered in this work.

An instance can then be characterized by six integers, the multiplicities of each tile, and a desired output region. Already determining whether the tiles can be arranged with their sides matching is a non-trivial problem, and is related to well-studied topics such as Wang tiles [5], tile self-assembly [1], and more. However, those problems typically do not specify multiplicities of the available tiles, and understanding which multiplicities are compatible is a necessary first step towards solving graph tiling problems. In this work, we characterize which multiplicities are compatible for all sets of at most three different tiles. We restrict our attention to instances in which the total number of tiles is a square number n2, that need to be assembled into an n×n grid, and assume input integers are encoded in binary.

Table 1: Results for all sets of at most three distinct tiles. The class with the value “?” contains problems that are compatible and those that are not compatible and we conjecture that there exists a polynomial-time algorithm to distinguish them, but this is still open.
⟨  I,  II,  III⟩⁢=^⁢⟨  III,  V,  VI⟩ YES
⟨  I,  II⟩⁢=^⁢⟨  V,  VI⟩ YES ⟨  I,  II,  IV⟩⁢=^⁢⟨  IV,  V,  VI⟩ YES
⟨  I,  III⟩⁢=^⁢⟨  III,  VI⟩ 𝖯 ⟨  I,  II,  V⟩⁢=^⁢⟨  II,  V,  VI⟩ YES
⟨  I,  IV⟩⁢=^⁢⟨  IV,  VI⟩ YES ⟨  I,  II,  VI⟩⁢=^⁢⟨  I,  V,  VI⟩ ?
⟨  I⟩⁢=^⁢⟨  VI⟩ YES ⟨  I,  V⟩⁢=^⁢⟨  II,  VI⟩ 𝖯 ⟨  I,  III,  IV⟩⁢=^⁢⟨  III,  IV,  VI⟩ YES
⟨  II⟩⁢=^⁢⟨  V⟩ YES ⟨  I,  VI⟩ NO ⟨  I,  III,  V⟩⁢=^⁢⟨  II,  III,  VI⟩ 𝖯
⟨  III⟩ YES ⟨  II,  III⟩⁢=^⁢⟨  III,  V⟩ YES ⟨  I,  III,  VI⟩ 𝖯
⟨  IV⟩ YES ⟨  II,  IV⟩⁢=^⁢⟨  IV,  V⟩ YES ⟨  I,  IV,  V⟩⁢=^⁢⟨  II,  IV,  VI⟩ YES
⟨  II,  V⟩ YES ⟨  I,  IV,  VI⟩ 𝖯
⟨  III,  IV⟩ YES ⟨  II,  III,  IV⟩⁢=^⁢⟨  III,  IV,  V⟩ YES
⟨  II,  III,  V⟩ YES
⟨  II,  IV,  V⟩ YES

2 Results

We consider the setting where we need to fill an n×n grid with pre-specified numbers of tiles of each type. We will use the notation   I,  II,…,  VI to refer to the tiles in Figure 2. Note that, apart from rotational symmetry, the tiles also have another type of symmetry: if we replace all sides with half-edges by sides without half-edges and vice versa, we arrive at an equivalent dual problem (for the purpose of testing compatibility). We will write   I⁢=^⁢  VI,   II⁢=^⁢  V,   III⁢=^⁢  III, and   IV⁢=^⁢  IV to denote this duality.

We will use the notation ⟨x1,x2,…,xk⟩ for the problem class of determining whether a nonzero number of tiles of each type x1, x2, to xk (for 1≤k≤6) can be assembled into an n×n square grid. Each problem class may have value YES (if all problems in the class are compatible), NO (if none of the problems in the class are compatible), 𝖯 (if compatible and incompatible problems both exist in the class, but it is possible to distinguish them in polynomial time), or 𝖭𝖯 (if it is 𝖭𝖯-hard to distinguish them). Our results are summarized in Table 1. Some interesting cases can be seen in Figure 3.

Refer to caption
Refer to caption
Refer to caption
Figure 3: Example tilings for classes ⟨  I,  V⟩, ⟨  II,  III,  IV⟩, and ⟨  I,  III,  VI⟩.

3 Future Work

We have characterized which multiplicities of at most three tile types are compatible. The clear next step is to extend this classification to classes with up to six different tile types.

Once this is understood, we can begin to investigate graph properties that may be achieved for specific instances, such as obtaining a connected graph, or a tree, or minimizing the area of the largest face / maximizing the area of the smallest face, etc.

References

  • [1] Erik D. Demaine, Martin L. Demaine, Sandor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane Souvaine. Staged self-assembly: Nanomanufacture of arbitrary shapes with O(1) glues, 2008. arXiv:0803.0316.
  • [2] Chelsea Fox, Kyle Chen, Micaela Antonini, Tommaso Magrini, and Chiara Daraio. Extracting geometry and topology of orange pericarps for the design of bioinspired energy absorbing materials, 2024. (Accepted to Advanced Materials). URL: https://arxiv.org/abs/2404.13351.
  • [3] Ke Liu, Rachel Sun, and Chiara Daraio. Growth rules for irregular architected materials with programmable properties. Science, 377:975–981, 2022. doi:10.1126/science.abn1459.
  • [4] Tommaso Magrini, Chelsea Fox, Adeline Wihardja, Athena Kolli, and Chiara Daraio. Control of mechanical and fracture properties in two-phase materials reinforced by continuous, irregular networks. Advanced Materials, 36(6):2305198, 2024. doi:10.1002/adma.202305198.
  • [5] Hao Wang. Proving theorems by pattern recognition — II. The Bell System Technical Journal, 40(1):1–41, 1961. doi:10.1002/j.1538-7305.1961.tb03975.x.