On representations by contact and intersection of segments

de Fraysseix, Hubert and Ossona de Mendez, Patrice (2007) On representations by contact and intersection of segments. [Journal (Paginated)]

Full text not available from this repository.

Abstract

A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a contact 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 C4 using 4 colors is the intersection graph of a family of straight line segments.

Item Type:	Journal (Paginated)
Classifications:	Z Theory > Z.500 Representations M Methods > M.999 Others P Styles > P.999 Others Z Theory > Z.250 Geometry
ID Code:	750
Deposited By:	Ossona de Mendez, Patrice
Deposited On:	27 Mar 2007
Last Modified:	18 Sep 2008 13:09
Alternative Locations:	http://www.springerlink.com/content/18054672k16u7364/

Repository Staff Only: item control page

References

J. Czyziwicz, 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. Marquez, 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.

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

H. de Fraysseix, A Characterization of Circle Graphs, European Journal of Combinatorics 5 (1984), 223–238.

H. de Fraysseix and P. Ossona de Mendez, Intersection Graphs of Jordan 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.

H. de Fraysseix and P. Ossona de Mendez, On a Characterization of Gauss Codes, Discrete and Computational Geometry 22 (1999), no. 2, 287–295.

H. de Fraysseix and P. Ossona de Mendez, Barycentric systems and stretchability, Discrete Applied Mathematics (2007), (in press).

H. de Fraysseix and P. Ossona de Mendez, Stretching of Jordan arc contact systems, Graph Drawing, Lecture Notes in Computer Science, vol. 2912, Springer Verlag, 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.

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

J.E. Goodman and R. Pollack, Allowable sequences and order types in discrete and computational geometry, New Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, 1993, pp. 103–134.

B. Grünbaum, Arrangements and Spreads, RI, American Mathematical Society, Providence, 1972.

I.B.-A. Hartman, I. Newman, 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. Kratochvıl, String graphs I : the number of critical nonstring graphs is infinite, J. Combin. Theory Ser. B 52 (1991), 53–66.

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

J. Kratochvıl and J. Matousek, String graphs requiring exponential representations, J. Combin. Theory Ser. B 52 (1991), 1–4.

J. Kratochvıl and J. Matousek, Intersection graphs of segments, Journal of Combinatorial Theory 62(B) (1994), no. 2, 289–315.

F. Levi, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade, Ber. Math.-Phys. Kl. sachs. Akad. Wiss. (1926), no. 78, 251–267, (Leipzig).

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

N.E. Mnëv, 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.