Open AccessA New Characterization of Graphs Based on Interpretation Relations
Author(s) -
Azaria Paz,
Judea Pearl,
Shmuel Ur
Publication year - 1993
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v22i444.6761
Subject(s) - axiom , interception , characterization (materials science) , relation (database) , graph , adjacency list , representation (politics) , interpretation (philosophy) , mathematics , computer science , discrete mathematics , combinatorics , data mining , political science , programming language , ecology , materials science , geometry , politics , law , biology , nanotechnology
While graphs are normally defined in terms of the 2-place relation of adjacency, we take the 3-place relation of interception as the basic primitive of the definition. The paper views graphs as an economic scheme for encoding interception relations, and establishes as axiomatic characterization of relations that lend themselves to representation in terms of graph interception, thus providing a new characterization of graphs.