On Intersection Graphs of Segments with Prescribed Slopes

Cerný, Jakub and Král, Daniel and Nyklová, Helena and Pangrác, Ondrej (2002) On Intersection Graphs of Segments with Prescribed Slopes. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 261-271 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_21).

Full text not available from this repository.

Abstract

We study intersection graphs of segments with prescribed slopes in the plane. A sufficient and necessary condition on tuples of slopes in order to define the same class of graphs is presented for both the possibilities that the parallel segments can or cannot overlap. Classes of intersection graphs of segments with four slopes are fully described; in particular, we find an infinite set of quadruples of slopes which define mutually distinct classes of intersection graphs of segments with those slopes.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_21
Classifications:Z Theory > Z.250 Geometry
ID Code:514

Repository Staff Only: item control page

References

T. Asano. Difficulty of the maximum independent set problem on intersection graphs of geometric objects. Graph theory, combinatorics and applications, vol. 1. Wiley-Intersci. Publ., 1991, pages 9-18.

A. Bouchet. Reducing prime graphs and recognizing circle graphs. Combinatorica 7, 1987, pages 243-254.

N. de Castro, F.J. cobos, J.C. Dana, A. Marquez, and M. Noy. Triangle-free planar graphs as segments intersection graphs. In J. Kratochvíl, editor, Proc. Graph Drawing: 7th International Symp. (GD '99), Lecture Notes in Comput. Sci. 1731, pages 341-350, Berlin. Springer, 1991.

G. Ehrlich, S. Even, and R. E. Tarjan, Intersection graphs of curves in the plane, Journal of Combinatorial Theory, Series B 21 (1976), 8-20.

J.C. Fournier. Une caracterization des graphes de cordes. C.R. Acad. Sci. Paris 286A, 1978, pages 811-813.

H. de Fraysseix: A characterization of circle graphs, Eur. J. Comb. 5 (1984) 223-238.

H. de Fraysseix, P. Ossona de Medez and J. Pach, "Representation of planar graphs by segments", Intuitive Geometry 63, pages 109-117, Szeged (Hungary), 1991.

M. Goljan, J. Kratochvíl, and P. Kucaera. String graphs. Technical report, Academia Prague, 1986.

I. Ben-Arroyo Hartman, I. Newman and R. Ziv, "On grid intersection graphs", Discrete Math. Vol. 87, pp. 41-52, 1991.

V.B. Kalinin. On intersection graphs. Algorithmic constructions and their efficiency (in russian), Yaroslav. Gos. Univ., 1983, pages 72-76.

S. Klavzar, M. Petkovsek. Intersection graphs of halflines and halfplanes. Discrete Math. 66, 1987, no. 1-2, pages 133-137.

J. Kratochvíl. Personal comunication.

Kratochvíl, J., Matousek, J.: Intersection graphs of segments, J. Combin. Theory Ser. B 62 (1994), 289-315.

J. Kratochvíl, J. Matousek. NP-hardness results for intersection graphs. Comment. Math. Univ. Carolin. 30 (1989), 761-773.

J. Kratochvíl and J. Nesetril. Independent set and clique problems in intersection defined classes of graphs. Comment. Math. Univ. Carolin. 31, 1990, pages 85-93.

A. C. Tucker. An algorithm for circular-arc graphs. SIAM J. Comput. 31.2, 1980, pages 211-216.