Unit Contact Representations of Grid Subgraphs with Regular Polytopes in 2D and 3D - Graph Drawing - page 136

Unit Contact Representations of Grid Subgraphs
with Regular Polytopes in 2D and 3D

Linda Kleist and Benjamin Rahman

Institutfur Mathematik, Technische Universitat Berlin, Berlin, Germany
{ kleist,rahman } @math.tu-berlin.de

Abstract. We present a strategytoconstruct unit proper contact representations
(UPCR) for subgraphs of certain highly symmetric grids. This strategy can be
applied to obtain graphs admitting UPCRs with squares and cubes, whose recog-
nition is NP-complete.
We show that subgraphs of the square grid allow for UPCR with squares which
strengthens the previously known cube representation. Indeed, we give UPCR
for subgraphs of a d -dimensional grid with d -cubes. Additionally, we show that
subgraphs of the triangular grid admit a UPCR with cubes, implying that the same
holds for each subgraph of an Archimedean grid. Considering further polygons,
we construct UPCR with regular 3 k -gons of the hexagonal grid and UPCR with
regular 4 k -gons of the square grid.

1 Introduction

In this paper, we study unit contact representations (UCR) which are contact represen-
tations (CR) with congruent objects. We are particularly interested in proper contacts
(PCR), that is, contacts are realized by segments of non-zero length in 2D or polygons
with non-zero area in 3D. Contacts not of this type are disregarded. Typical objects
considered are regular polygons and cubes.

1.1 Related Work

Considering homothetic copies of disks, the celebrated circle packing theorem of Koebe
[10] states that every planar graph has a CR with disks. Schramm [11] gives the follow-
inggeneralization: Assigning a convex set in 2D with smooth boundary to each vertex,
every planar graph has a CR with non-degenerated homothetic copies of the prescribed
sets. Allowing convex sets without smooth boundary, this results in CRs with possi-
bly degenerated homothetic copies of the assigned sets [11, 12]. Gon¸alves, Leveque
and Pinlou [8] observe that this result can be exploited for triangle CRs with non-
degenerated homothetic triangles for 4-connected planar triangulations. Felsner and
Francis [6] employ possibly degenerated homothetic triangle representations to show
that all planar graphs have a CR with cubes, where contacts are not necessarily proper.
StudyingPCRs with polygons, Gansner et al. [7] show that every planar graph has a
PCR with hexagons, but not always with pentagons.