On maximal and minimal triangular planar graphs: an optimization approach
Sydney C. K. Chu · International Journal of Mathematical Education in Science and Technology · 1993
A triangular planar graph (TPG) is defined to be a connected simple planar graph with every edge being a side of some triangle. Given a fixed number of nodes, a maximal (respectively minimal) TPG is a TPG that has a maximum (respectively minimum) possible number of edges. Here we suggest a novel idea of constructively characterizing a minimal TPG by way of a simple integer optimization formulation, which leads readily to solutions as well as generalizations for planar graphs with edges being sides of polygons. Simple results for the easier problem of maximal TPG are also provided.