On edges crossing few other edges in simple topological complete graphs (Q1011770): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2008.03.005 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2012800930 / rank | |||
Normal rank |
Revision as of 03:29, 20 March 2024
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