Abstract: We study contact representations of graphs in the plane and in 3D space, where vertices are represented by polygons or polyhedra and each edge is realized by a common boundary between two polygons or polyhedra. In the weighted version of the problem, we find contact representations with the additional restriction that the areas for the polygons or the volumes for the polyhedra realize some pre-specified value for the vertices. We address different variants of the problem depending on the types of polygons or polyhedra (convex or non-convex, axis-aligned or not), types of contacts (proper contacts with common boundaries of non-zero lengths in 2D or non-zero areas in 3D or improper contacts where common boundaries of zero lengths or areas are allowed), and whether holes are allowed in the representation or not.
In the plane we mainly focus on the weighted version of the problem. We find optimal (in terms of polygonal complexity) contact representations for planar graphs (both for axis-aligned and non-axis-aligned polygons) and some subclasses of planar graphs. With non-axis-aligned polygons we show that non-convex polygons with 4 sides are sometimes necessary and always sufficient for proportional contact representation of a planar graph, when point contacts are allowed; otherwise for proper contacts, 7-sided polygons are sometimes necessary and always sufficient. We give a linear-time algorithm in each case to compute the optimal representation. We also give polynomial-time algorithms to construct optimal proportional contact representations for (2, 0)-sparse graphs and for maximal outerplanar graphs. In case only axis-aligned polygons are used, we show that 8 sides are sometimes necessary and always sufficient for a planar graph. While we do not have a polynomial-time algorithm to construct such a representation, we give a linear-time algorithm to compute representation with 10-sided axis-aligned polygons. We also give linear-time construction algorithms for optimal proportional contact representations with 8-sided polygons for planar 3-trees and Hamiltonian maximal planar graphs, and with rectangles for maximal outerplanar graphs. For contact representation with 3D polyhedra, we consider both the weighted and the unweighted variants of the problem for both planar and non-planar graphs and have some preliminary results. We find several subclasses of planar graphs that have contact representations using cubes or proportional boxes. We also consider (improper) contact representations using tetrahedra, and show that planar graphs, complete bipartite and tripartite graphs, and complete graphs with at most 10 vertices have such representations.