Disjoint edges in geometric graphs. (English) Zbl 0692.05037

Summary: Answering an old question in combinatorial geometry, we show that any configuration consisting of a set \(V\) of \(n\) points in general position in the plane and a set of \(6n-5\) closed straight line segments whose endpoints lie in \(V\), contains three pairwise disjoint line segments.


05C35 Extremal problems in graph theory
Full Text: DOI EuDML


[1] J. Akiyama and N. Alon, Disjoint simplices and geometric hypergraphs,Proc. 3rd New York Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences, to appear. · Zbl 0734.05064
[2] S. Avital and H. Hanani, Graphs,Gilyonot Lematematika3(2) (1966), 2-8 (in Hebrew).
[3] P. Erdös, On sets of distances ofn points,Amer. Math. Monthly53 (1946), 248-250. · Zbl 0060.34805 · doi:10.2307/2305092
[4] Y. S. Kupitz,Extremal Problems in Combinatorial Geometry, Aarhus University Lecture Notes Series, No. 53, Aarhus University, Denmark, 1979. · Zbl 0414.05029
[5] M. A. Perles, Unpublished notes.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.