Unavoidable Configurations in Complete Topological Graphs

Pach, János and Tóth, Géza (2001) Unavoidable Configurations in Complete Topological Graphs. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 328-337(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_31).

Full text not available from this repository.

Abstract

A topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by Jordan curves connecting the corresponding points, with the property that any two curves have at most one point in common. We define two canonical classes of topological complete graphs, and prove that every topological complete graph with n vertices has a canonical subgraph of size at least $c\log\log n$, which belongs to one of these classes. We also show that every complete topological graph with n vertices has a non-crossing subgraph isomorphic to any fixed tree with at most $c\log^{1/6}n$ vertices.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-44541-2_31
Classifications:	Z Theory > Z.999 Others Z Theory > Z.750 Topology
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/411

Actions (login required)

View Item