Density Theorems for Intersection Graphs of t-Monotone Curves

Suk, 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.

Abstract

A 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.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-642-36763-2_32
Classifications:	P Styles > P.300 Curved Z Theory > Z.500 Representations Z Theory > Z.750 Topology
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1324

Actions (login required)

View Item