Tilings of orthogonal polygons with similar rectangles or triangles

In this paper we prove two results about tilings of orthogonal polygons. (1) LetP be an orthogonal polygon with rational vertex coordinates and letR(u) be a rectangle with side lengthsu and 1. An orthogonal polygonP can be tiled with similar copies ofR(u) if and only ifu is algebraic and the real part of each of its conjugates is positive; (2) Laczkovich proved that if a triangle Δ tiles a rectangle then either Δ is a right triangle or the angles of Δ are rational multiples of π. We generalize the result of Laczkovich to orthogonal polygons.     

The boundary characteristic and Pick's theorem in the Archimedean planar tilings

The tiling of the plane by unit squares is only one of the 11 Archimedean tilings which use regular polygons and have only one type of vertex. In this paper, the boundary characteristic of a lattice polygon is defined for every Archimedean tiling, and related enumeration formulae are found. Pick's theorem (on the area of a lattice polygon in the tilling by squares) is then generalized for lattice polygons in each of the Archimedean tilings, by enumerating the number of tiles of each type in the polygon.     

Tiling Polygons with Lattice Triangles

Given a simple polygon with rational coordinates having one vertex at the origin and an adjacent vertex on the x-axis, we look at the problem of the location of the vertices for a tiling of the polygon using lattice triangles (i.e., triangles which are congruent to a triangle with the coordinates of the vertices being integer). We show that the coordinates of the vertices in any tiling are rationals with the possible denominators odd numbers dependent on the cotangents of the angles in the triangles.     

Tilings of Convex Polygons with Congruent Triangles

By the spectrum of a polygon A we mean the set of triples (??,??,??) such that A can be dissected into congruent triangles of angles ??,??,??. We propose a technique for finding the spectrum of every convex polygon. Our method is based on the following classification. A tiling is called regular if there are two angles of the triangles, ?? and ?? such that at every vertex of the tiling the number of triangles having angle ?? equals the number of triangles having angle ??. Otherwise the tiling is irregular. We list all pairs (A,T) such that A is a convex polygon and T is a triangle that tiles A regularly. The list of triangles tiling A irregularly is always finite, and can be obtained, at least in principle, by considering the system of equations satisfied by the angles, examining the conjugate tilings, and comparing the sides and the area of the triangles to those of A. Using this method we characterize the convex polygons with infinite spectrum, and determine the spectrum of the regular triangle, the square, all rectangles, and the regular N-gons with N large enough.     

On two questions concerning tilings

We prove that a tiling of the plane by topological disks is locally finite at most boundary points of tiles, confirming a conjecture by Valette. This comes by way of a much more general theorem on tilings of topological vector spaces. We also investigate a question raised by Klee as to whether or not there is a tiling of separable Hilbert space by bounded convex tiles. We present evidence to support the conjecture that the answer is negative.     

Aperiodic tiles

A set of tiles (closed topological disks) is calledaperiodic if there exist tilings of the plane by tiles congruent to those in the set, but no such tiling has any translational symmetry. Several aperiodic sets have been discussed in the literature. We consider a number of aperiodic sets which were briefly described in the recent bookTilings and Patterns, but for which no proofs of their aperiodic character were given. These proofs are presented here in detail, using a technique with goes back to R. M. Robinson and Roger Penrose. The research of Branko Grünbaum was supported in part by NSF Grants MCS8301971 and DMS-8620181.     

On a Theorem of Bandt and Wang and Its Extension to <Emphasis Type="Italic">p</Emphasis>2-tiles

We study tilings of the plane by a single prototile with respect to the lattice and to the crystallographic group p2. We are interested in the connection between the neighbors of a tile in the tiling and its topology. We show that lattice and p2-tiles always have at least six neighbors. We characterize self-affine tiles that are homeomorphic to a disk in a rather easy way by the set and number of neighbors of the central tile in the tiling. This extends the work of Bandt and Wang devoted to lattice self-affine disk-like tiles of the plane.     

The contractible subgraph of 5-connected graphs

An edge e of a k-connected graph G is said to be k-removable if G — e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction results still in a k-connected graph. A k-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k-connected. In this paper, we show that there is a contractible subgraph in a 5-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally 5-connected graph is contained in some triangle.     

Triangle Contact Representations and Duality

A?contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. De Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A?primal?Cdual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal?Cdual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a corner of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.     

Combinatorially Regular Polyomino Tilings

Let T be a regular tiling of ℝ² which has the origin 0 as a vertex, and suppose that φ: ℝ² → ℝ² is a homeomorphism such that (i) φ(0)=0, (ii) the image under φ of each tile of T is a union of tiles of T, and (iii) the images under φ of any two tiles of T are equivalent by an orientation-preserving isometry which takes vertices to vertices. It is proved here that there is a subset Λ of the vertices of T such that Λ is a lattice and φ|_Λ is a group homomorphism. The tiling φ(T) is a tiling of ℝ by polyiamonds, polyominos, or polyhexes. These tilings occur often as expansion complexes of finite subdivision rules. The above theorem is instrumental in determining when the tiling φ(T) is conjugate to a self-similar tiling.     

Superconnected and Hyperconnected Small Degree Transitive Graphs

A graph is said to be superconnected if every minimum vertex cut isolates a vertex. A graph is said to be hyperconnected if each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this paper, we characterize superconnected or hyperconnected vertex transitive graphs with degree 4 and 5. As a corollary, superconnected or hyperconnected planar transitive graphs are characterized.     

Cohomology in one-dimensional substitution tiling spaces

Anderson and Putnam showed that the cohomology of a substitution tiling space may be computed by collaring tiles to obtain a substitution which ``forces its border.' One can then represent the tiling space as an inverse limit of an inflation and substitution map on a cellular complex formed from the collared tiles; the cohomology of the tiling space is computed as the direct limit of the homomorphism induced by inflation and substitution on the cohomology of the complex. For one-dimensional substitution tiling spaces, we describe a modification of the Anderson-Putnam complex on collared tiles that allows for easier computation and provides a means of identifying certain special features of the tiling space with particular elements of the cohomology.

     

A strongly aperiodic set of tiles in the hyperbolic plane

We construct the first known example of a strongly aperiodic set of tiles in the hyperbolic plane. Such a set of tiles does admit a tiling, but admits no tiling with an infinite cyclic symmetry. This can also be regarded as a regular production system [5] that does admit bi-infinite orbits, but admits no periodic orbits.     

Triangulations (tilings) and certain block triangular matrices

For a convex polygonP withn sides, a ‘partitioning’ ofP inton−2 nonoverlapping triangles each of whose vertices is a vertex ofP is called a triangulation or tiling, and each triangle is a tile. Each tile has a given cost associated with it which may differ one from another. This paper considers the problem of finding a tiling ofP such that the sum of the costs of the tiles used is a minimum, and explores the curiosity that (an abstract formulation of) it can be cast as a linear program. Further the special structure of the linear program permits a recursive O(n ³) algorithm. Research and reproduction of this report were partially supported by the National Science Foundation Grants MCS-8119774, MCS-7926009 and ECS-8012974; Department of Energy Contract DE-AM03-76SF00326, PA# DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and donot necessarily reflect the views of the above sponsors.     

Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we proved that a vertex transitive bipartite graph is not super-connected if and only if it is isomorphic to the lexicographic product of a cycle C_n(n ≥ 6) by a null graph N_m. We also characterized non-hyper-connected vertex transitive bipartite graphs.     

上连通和超连通的三次Bi-Cayley图

Let G be a finite group and let S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G×{0, 1} and edge set {(g, 0) (sg, 1) : g∈G, s ∈ S}. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if every minimum vertex cut creates two components, one of which is an isolated vertex. In this paper, super-connected and/or hyper-connected cubic Bi-Cayley graphs are characterized.     

Super-connected arc-transitive digraphs

A digraph is said to be super-connected if every minimum vertex cut is the out-neighbor set or in-neighbor set of a vertex. A digraph is said to be reducible, if there are two vertices with the same out-neighbor set or the same in-neighbor set. In this paper, we prove that a strongly connected arc-transitive oriented graph is either reducible or super-connected. Furthermore, if this digraph is also an Abelian Cayley digraph, then it is super-connected.     

上连通和超连通三次点传递图

图G称为上连通的,若对每个最小割集C,G-C有孤立点,G称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为弧立点,本文刻划了上连通和超连通三次点传递图。     

上连通和超连通三次点传递图(英)

图G称为上连通的,若对每个最小割集C,G-C有孤立点.G称为超连通的,若对每个最小割集G,G-C恰有两个连通分支,且其中之一为孤立点.本文刻划了上连通和超连通三次点传递图.     

Drawing planar 3-trees with given face areas

We study straight-line drawings of planar graphs such that each interior face has a prescribed area. It was known that such drawings exist for all planar graphs with maximum degree 3. We show here that such drawings exist for all planar partial 3-trees, i.e., subgraphs of a triangulated planar graph obtained by repeatedly inserting a vertex in one triangle and connecting it to all vertices of the triangle. Moreover, vertices have rational coordinates if the face areas are rational, and we can bound the resolution. We also give some negative results for other graph classes.