Axis-Aligned Square Contact Representations

03/15/2021

∙

by   Andrew Nathenson, et al.

∙

0

∙

share

We introduce a new class 𝒢 of bipartite plane graphs and prove that each graph in 𝒢 admits a proper square contact representation. A contact between two squares is proper if they intersect in a line segment of positive length. The class 𝒢 is the family of quadrangulations obtained from the 4-cycle C_4 by successively inserting a single vertex or a 4-cycle of vertices into a face. For every graph G∈𝒢, we construct a proper square contact representation. The key parameter of the recursive construction is the aspect ratio of the rectangle bounded by the four outer squares. We show that this aspect ratio may continuously vary in an interval I_G. The interval I_G cannot be replaced by a fixed aspect ratio, however, as we show, the feasible interval I_G may be an arbitrarily small neighborhood of any positive real.