Charles Explorer logo
🇨🇿

Geometric Graphs with No Three Disjoint Edges

Publikace na Matematicko-fyzikální fakulta |
2005

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and edges are represented by straight line segments. We show that a geometric graph on n vertices with no three pairwise disjoint edges has at most 2.5n edges.

This result is tight up to an additive constant.