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.
Partially supported by DGES-MEC-PB96-0005-C02
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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. Lectures 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. Osona de Mendez and J. Pach, “Representation of planar graphs by segments”, Colloquia Mathematica Societatis Jáanos 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.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Castro, N., Cobos, F.J., Dana, J.C., Márquez, A., Noy, M. (1999). Triangle-Free Planar Graphs as Segments Intersection Graphs. In: Kratochvíyl, J. (eds) Graph Drawing. GD 1999. Lecture Notes in Computer Science, vol 1731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46648-7_35
Download citation
DOI: https://doi.org/10.1007/3-540-46648-7_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66904-3
Online ISBN: 978-3-540-46648-2
eBook Packages: Springer Book Archive