Unavoidable Configurations in Complete Topological Graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 2003-08, Vol.30 (2), p.311-320
Main Authors: Pach, J nos, Solymosi, J zsef, T th, G za
Format: Article
Language:English
Subjects:
Geometry
Graphs
Mathematical analysis
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 clog1/8 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 clog1/6 n vertices. [PUBLICATION ABSTRACT]
ISSN:0179-5376
1432-0444
DOI:10.1007/s00454-003-0012-9