Contact and Intersection Representations

De Fraysseix, Hubert and Ossona de Mendez, Patrice (2004) Contact and Intersection Representations. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 217-227 (Official URL:

Full text not available from this repository.


A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a family of segments and points. We deduce that any 4-connected 3-colorable plane graph is the contact graph of a family of segments and that any 4-colored planar graph without an induced C_4 using 4 colors is the intersection graph of a family of straight line segments.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_23
Classifications:Z Theory > Z.250 Geometry
ID Code:589

Repository Staff Only: item control page


J. Czyziwics, E. Kranakis, and J. Urrutia, A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments, Information Processing Letters (1998), no. 66, 125-126.

N. de Castro, F. J. Cobos, J. C. Dana, and A. Márquez, Triangle-free planar graphs as segment intersection graphs, Journal of Graph Algorithms and Applications 6 (2002), no. 1, 7-26.

H. de Fraysseix, Local complementation and interlacement graphs, Discrete Mathematics 33 (1981), 29-35.

_____, A Characterization of Circle Graphs, European Journal of Combinatorics 5 (1984), 223-238.

H. de Fraysseix and P. Ossona de Mendez, Intersection Graphs of Jourdan Arcs, Contemporary Trends in Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, DIMATIA-DIMACS, 1999, Stirin 1997 Proc., pp. 11-28.

_____, On a Characterization of Gauss Codes, Discrete and Computational Geometry 2 (1999), no 2.

_____, Barycentric systems and strechability, Discrete Applied Mathematics (2004), (submited).

_____, Stretching of Jordan arc contact systems, Graph Drawing, Lecture Notes in Computer Science, vol. 2912, Springer, 2004, pp. 71-85.

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

H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl , On triangle contact graphs, Combinatorics, Probability and Computing 3 (1994), 233-246.

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

C. F. Gauss, Werke, pp. 272 and 282-285, Teubner Leipzig, 1900.

I. B. -A. Hartmann, and R. Ziv, On grid intersection graphs, Discrete Math. 87 (1991), 41-52.

Petr Hlineny, Contact graphs of line segments are NP-complete, Discrete Mathematics 235 (2001), no. 1-3, 95-106.

J. Kratochvil, String graphs I : the number of critical nonstring graphs is infinite J. Combin. Theory Ser. B 52 (1991), 53-66.

_____, String graphs II : Recognizing string graphs is NP-hard, J. Combin. Theory Ser. B 52 (1991b).

J. Kratochvil and J. Matousek, String graphs requiring exponential representations, J. Combin. Theory Ser. B 52 (1991), 1-4.

_____, Intersection graphs of segments, Journal of Combinatorial Theory 62(B) (1994), no. 2, 289-315.

N. E. Mnev, On manifolds of combinatorial types of projective configurations and convex polyhedra, Soviet Math. Deokl. (1985), no. 32, 335-337.

_____, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, Topology and Geometry - Rohlin Seminar (Berlin) (O. Ya. Viro, ed.), Lecture Notes in Mathematics, vol. 1346, Springer-Verlag, 1988, pp. 527-544.

J. Pach and G. Toth, Which crossing number is it anyway?, Journal of Combinatorial Theory, Ser. B 80 (2000), no. 2, 225-246.

J. Richter-Gebert, Realization spaces of polytopes, Lecture Notes in Mathematics 1643 (1996).

P. Rosenstiehl, A new proof of the Gauss interlace conjecture, Advances in Applied Mathematics 23 (1999), no. 1, 3-13.

M. Schaefer, E. Sedgwick, and D. Stefankovic, Recognizing string graphs in NP Journal of Computer and System Sciences 67 (2003), no. 2, 365-380.

E. R. Scheinerman, Intersection classes and multiple intersection parameters of graphs, Ph.D. thesis, Princeton, University, 1984.

P. W. Shor, Stretchability of pseudolines is NP-hard, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 4 (1991), 531-554.

F. W. Sinden, Topology of thin RC-circuits, Bell System Tech. J. (1966), 1639-1662.

D. West, Opem problems, SIAM J. Discrete Math. Newslett. 2 (1999), no. 1, 10-12.