Discrete Realizations of Contact and Intersection Graphs (Extended Abstract)

Czyzowicz, Jurek and Kranakis, Evangelos and Krizanc, Danny and Urrutia, Jorge (1998) Discrete Realizations of Contact and Intersection Graphs (Extended Abstract). In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 359-370(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_81).

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_81
Classifications: G Algorithms and Complexity > G.560 Geometry
Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/151

Actions (login required)

View Item View Item