2001 | OriginalPaper | Buchkapitel
Unavoidable Configurations in Complete Topological Graphs
verfasst von : János Pach, Géza Tóth
Erschienen in: Graph Drawing
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 log1/6n vertices.