Leírás
We prove some natural generalizations of well known Ramsey-type results for abstract graphs, for graphs drawn in the plane. An example: It is well known that for every graph G, either G or its complement is connected. So, G or its complement contains a spanning tree. We show that every geometric graph (graph drawn with straight line segments as edges) or its complement contains a NONCROSSING spanning tree.
Bibliography:
G. Károlyi, J. Pach, G. Tóth: Ramsey-Type Results for Geometric Graphs, I, Discrete and Computational Geometry 18 (1997), 247-255. Also in: Proceedings of the 12th Annual ACM Symposium on Computational Geometry 1996, 359-365.
J. Pach, J. Solymosi, G. Tóth: Unavoidable configurations in complete topological graphs, Discrete and Computational Geometry 30 (2003), 311-320. Also in: Lecture Notes in Computer Science 1984 Springer-Verlag, 2001, 328-337.