Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
973138 | Mathematical Social Sciences | 2007 | 24 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Dale Peterson,