Triangle-Free Planar Graphs as Segments Intersection Graphs

De Castro, Natalia and Cobos, F. J. and Dana, J. C. and Márquez, Alberto and Noy, M. (1999) Triangle-Free Planar Graphs as Segments Intersection Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 341-350 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_35).

Full text not available from this repository.

Abstract

We prove that every triangle-free planar graph is the graph of intersection of a set of segments in the plane. Moreover, the segments can be chosen in only three directions (horizontal, vertical and oblique) and in such a way that no two segments cross, i. e., intersect in a common interior point.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_35
Classifications:Z Theory > Z.999 Others
Z Theory > Z.250 Geometry
M Methods > M.600 Planar
ID Code:377

Repository Staff Only: item control page

References

D. W. Barnette, "On Steinitz's theorem concerning convex 3-polytopes and on some properties of planar graphs", The many facets of graph theory. Lecture Notes in Mathematics Vol. 110, Springer, Berlin, pp. 27-39, 1969.

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

H. de Fraysseix, P. Ossona de Medez and J. Pach, "Representation of planar graphs by segments", Colloquia Mathematica Societatis János Bolyai, Intuitive Geometry, Szeged (Hungary), 1991.

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

J. Kratochvíl, "A special planar satisfiability problem and a consequence of its NP-completeness", Discrete Applied Math., Vol. 52, pp. 233-252, 1994.

W. Naji, "Reconnaisance des graphes de cordes", Discrete Math. Vol. 54, pp. 329-337, 1985.

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

J. Spinrad, "Recognition of circle graphs", J. of Algorithms, Vol. 16, pp. 264-282, 1994.

C. Thomassen, "Grötzsch's 3-colour theorem and its counterparts for the torus and the projective plane", J. Comb. Theory B Vol. 62, pp. 268-279, 1994.