Logo

Login | Create Account

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). [Conference Paper]

Full text not available from this repository.

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.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.560 Geometry
Z Theory > Z.250 Geometry
ID Code:151
Deposited By:Martinez Leon, Victoria
Deposited On:02 Nov 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

1. S. Abramowski, B. Lang, and H. Miller, "Moving Regular k-gons in Contact", In Proceedings of International Workshop WG '88 on Graph-Theoretic Concepts in Computer Science, Jan van Leewen, editor, Springer Verlag Lecture Notes in Computer Science, vol. 344, pp. 229-242, 1989.

2. S.N. Bhatt and S.S. Cosmadakis, "The Complexity of Minimizing Wire Lenghts in VLSI Layouts", Information Processing Letters 25 (1987) 263-267.

3. H. Breu and D.G. Kirkpatrick, "On the Complexity of Recognizing Intersection and Touching Graphs of Disks", In Proceedings of Graph Drawing 95, pp. 88-98. Springer Verlag Lecture Notes in Computer Science.

4. G.R. Brightwell, and R.E. Scheinerman, "Representations of Planar Graphs", Siam Journal on ???, Vol. 6, No. 2, pp. 214-229, May 1993.

5. D.G. Corneil, H. Kim, S. Natarajan, S. Olariu, and A.P. Sprague, " Simple Linear Time Recognition of Unit Interval Graphs", Information Processing Letters 56 (1995) 99-104.

6. C.M. Herrera de Figueiredo, J. Meidanis, C. Picinin de Mello, " A Linear-Time Algorithm for Proper Interval Graph Recognition", Information Processing Letters 55 (1995) 179-184.

7. H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl, "On Triangle Contact Graphs", Combinatorics, Probability and Computing (1994) 3, 233-246.

8. D.R. Fulkerson and O.A. Gross, "Incidence Matrices and Interval Graphs". Pacific Journal of Mathematics, 15, 835-855, 1985.

9. M.C. Golumbic, "Algorithmic Graph Theory and Perfect Graphs", Academic Press, New York, 1980.

10. N. Korte and R.H. Möhring, " A Simple Linear-Time Algorithm to Recognize Interval Graphs", In Proceedings of International Workshop WG '86 on Graph-Theoretic Concepts in Computer Science, G. Tinhofer and G. Schmidt, editors, Springer Verlag Lecture Notes in Computer Science, vol. 246, 1987.

11. Z. Miller and J.B. Orlin, "NP-Completness for Minimizing Maximum Edge Length in Grid Embeddings", Journal of Algorithms 6, 10-16 (1985).

12. H. Sachs, "Coin Graphs, Polyhedra, and Conformal Mapping", Discrete Mathematics 134 (1994) 133-138.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.