Discrete Realizations of Contact and Intersection Graphs (Extended Abstract)

Known realizations of geometric representations of graphs, like contact, intersection etc., are "continuous", in the sense that the geometric objects are drawn in Euclidean space with real numbers as coordinates. In this paper, we initiate the study of discrete versions of contact and intersection graphs and examine their relation to their cintinuous counterparts. The classes of graphs arising appear to have interesting properties and are thus interesting on their own right. We also study realizability, characterizations as well as intractability questions for the resulting new classes of graphs. 1980 Mathematics Subject Classification: 68R10, 68U05 CR Categories: F.2.2 Key Words and Phrases: Coin, Contact, Intersection, Interval graphs, Discrete, Planar graphs, NP