On edges crossing few other edges in simple topological complete graphs
type: Item
instance of: scholarly article
title: On edges crossing few other edges in simple topological complete graphs
zbMATH Open document ID: 1175.05042
author: Jan Kynčl
author: Pavel Valtr
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: 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\).
reviewed by: Josef Lauri
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5542418
zbMATH Keywords: complete graph
zbMATH Keywords: crossings
zbMATH Keywords: drawings in the plane
MaRDI profile type: Publication
full work available at URL: j.disc.2008.03.005
OpenAlex ID: W2012800930
cites work: Crossing-Free Subgraphs
cites work: Research Problems in Discrete Geometry
cites work: Bounds for generalized thrackles
cites work: Geometric graphs with no three disjoint edges
cites work: Q4175595
cites work: Edges without crossings in drawings of complete graphs
cites work: Q3139539
cites work: Q4862893
cites work: New lower bound techniques for VLSI
cites work: Q4422289
cites work: Q4657589
cites work: Discrete and Computational Geometry
cites work: Unavoidable configurations in complete topological graphs
cites work: Combinatorial Geometry and Graph Theory
cites work: Q4657592
cites work: Q5543310
cites work: Q4853715
DOI: 10.1016/J.DISC.2008.03.005
description: scientific article; zbMATH DE number 5542418