Density Theorems for Intersection Graphs of tMonotone CurvesSuk, Andrew (2013) Density Theorems for Intersection Graphs of tMonotone Curves. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 352363(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractA curve γ in the plane is tmonotone if its interior has at most $t − 1$ vertical tangent points. A family of tmonotone curves F is simple if any two members intersect at most once. It is shown that if F is a simple family of n tmonotone curves with at least $εn^2$ intersecting pairs (disjoint pairs), then there exists two subfamilies $F_1 , F_2 ⊂ F$ of size δn each, such that every curve in $F_1$ intersects (is disjoint to) every curve in $F_2$, where δ depends only on ε. We apply these results to find pairwise disjoint edges in simple topological graphs.
Actions (login required)
