On edges crossing few other edges in simple topological complete graphs (Q1011770): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Crossing-Free Subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Research Problems in Discrete Geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds for generalized thrackles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geometric graphs with no three disjoint edges / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4175595 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edges without crossings in drawings of complete graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3139539 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4862893 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New lower bound techniques for VLSI / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4422289 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4657589 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Discrete and Computational Geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Unavoidable configurations in complete topological graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial Geometry and Graph Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4657592 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5543310 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4853715 / rank | |||
Normal rank |
Latest revision as of 12:01, 1 July 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