Gridline indifference graphs

Indifference graphs can be realized on a line with vertices adjacent whenever they are within a given distance. These well-studied graphs have applications to many fields including ecology, cluster theory, and psychology, in the placement of objects in a single dimension. The extension to the grid and higher dimensions has been considered in e.g. Goodman's study of perception (1977); we introduce gridline indifference graphs, which can be realized in the plane with vertices adjacent whenever they are within a given distance and on a common vertical or horizontal line. We obtain full and partial characterizations when these graphs are triangulated in terms of forbidden subgraphs, extreme points, and tree-clique graphs. These results are extended to higher dimensions.