Density Theorems for Intersection Graphs of t-Monotone CurvesSuk, Andrew (2013) Density Theorems for Intersection Graphs of t-Monotone Curves. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 352-363(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/978-3-642...
AbstractA curve γ in the plane is t-monotone if its interior has at most $t − 1$ vertical tangent points. A family of t-monotone curves F is simple if any two members intersect at most once. It is shown that if F is a simple family of n t-monotone 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)
|