Generator-Preserving Contractions and a Min-Max Result on the Graphs of Planar Polyminoes

In this paper, we deal with the convex generators of a graph \(G = (V(G), E(G))\). A convex generator being a minimal set whose convex hull is \(V(G)\), we show that it is included in the “boundary” of \(G\). Then we show that the “boundary” of a polymino’s graph, or more precisely the seaweed’s “boundary”, enjoys some nice properties which permit us to prove that for such a graph \(G\), the minimal size of a convex generator is equal to the maximal number of hanging vertices of a tree \(T\), obtained from \(G\) by a sequence of generator-preserving contractions.