Convex Neighborhood Polynomial of Planar Grids

Convexity in networks has been defined as a property of each subgraph to include all shortest paths between its nodes. It has practical applications in network optimization problems, distributed algorithms, and graph-based machine learning, impacting the complexity of graph algorithms and enabling the analysis of real-world networks. While convex substructures are important, the neighborhood systems of these substructures contribute significantly to the entire functionality of the network structure. In this paper, we introduce the idea of convex neighborhood polynomial as a representation of convex substructures with corresponding cardinality of their neighborhood systems. In particular, we determine the convex neighborhood polynomial of planar grids.