On edges crossing few other edges in simple topological complete graphs
Result description
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. We show that $Omega(n^{3/2})le h(n) le O(n^2/log^{1/4}n)$. We also show that the analogous function on other surfaces (torus, Klein bottle) grows as $cn^2$.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On edges crossing few other edges in simple topological complete graphs
Original language description
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. We show that $Omega(n^{3/2})le h(n) le O(n^2/log^{1/4}n)$. We also show that the analogous function on other surfaces (torus, Klein bottle) grows as $cn^2$.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Graph Drawing
ISBN
3-540-31425-3
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
—
Publisher name
Springer
Place of publication
Berlin
Event location
Berlin
Event date
Jan 1, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000235806300025
Basic information
Result type
D - Article in proceedings
CEP
BA - General mathematics
Year of implementation
2006