Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs

Abstract

A square-contact representation of a planar graph $G=(V,E)$ maps the vertices in $V$ to interior disjoint axis-aligned squares in the plane and the edges in $E$ to adjacencies between the sides of the squares corresponding to the endpoints of each edge. In this paper, we study proper square-contact representations of planar graphs, that is, square-contact representations in which any two squares are either disjoint or share infinitely many points.
We provide elegant characterizations for the partial $2$-trees and for the triconnected simply-nested graphs allowing for such representations. The characterization for the partial $2$-trees corresponds to the absence of a simple forbidden subgraph whose structure forces the presence of separating triangles in any embedding. The characterization for the triconnected simply-nested graphs is based on the outerplanarity index of the graph and on a new structural decomposition for a notable family of $2$-outerplanar simply-nested graphs that might be of independent interest.