On edges crossing few other edges in simple topological complete graphs (Q1011770)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On edges crossing few other edges in simple topological complete graphs |
scientific article |
Statements
On edges crossing few other edges in simple topological complete graphs (English)
0 references
9 April 2009
0 references
A simple topological graph is a representation in the plane of a graph such that the vertices of the graph correspond to distinct points in the plane and the edges correspond to Jordan curves connecting the corresponding points and having at most one point in common, either a vertex-point or a crossing. Now let \(h=h(n)\) be the smallest integer such that every simple topological complete graph on \(n\) vertices contains an edge crossing at most \(h\) other edges. The authors show that \(\Omega(n^{3/2}) \leq h(n) \leq O(n^2/\log^{1/4} n)\). They also show that the analogous function on the torus and the Klein bottle grows as \(cn^2\).
0 references
complete graph
0 references
crossings
0 references
drawings in the plane
0 references