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

A $3$-connected $3$-outerplanar graph that does not admit any square-contact representation, even an improper one


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.

In 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Giordano Da Lozzo
Assistant Professor (RTDb)

My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.