Many Touchings Force Many Crossings

Pach, János and Tóth, Géza (2017) Many Touchings Force Many Crossings. In: Graph Drawing and Network Visualization, GD 2017, September 25-27 , pp. 153-159(Official URL: https://doi.org/10.1007/978-3-319-73915-1_13).

Full text not available from this repository.

Abstract

Given n continuous open curves in the plane, we say that a pair is touching if they have only one interior point in common and at this point the first curve does not get from one side of the second curve to its other side. Otherwise, if the two curves intersect, they are said to form a crossing pair. Let t and c denote the number of touching pairs and crossing pairs, respectively. We prove that c≥1105t2n2, provided that t≥10n. Apart from the values of the constants, this result is best possible. (Mathematical formula not displayed correctly!)

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.420 Crossings P Styles > P.300 Curved Z Theory > Z.250 Geometry
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1600

Actions (login required)

View Item