Geometric Graphs with No Three Disjoint Edges

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F05%3A00000978" target="_blank" >RIV/00216208:11320/05:00000978 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Geometric Graphs with No Three Disjoint Edges
Original language description
A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and edges are represented by straight line segments. We show that a geometric graph on n vertices with no three pairwise disjoint edges hasat most 2.5n edges. This result is tight up to an additive constant.
Czech name
Geometrické grafy bez tří disjunktních hran
Czech description
Geometrický graf je graf nakreslený do roviny tak, že vrcholy jsou body v rovině v obecné poloze a hrany jsou reprezenzovány úsečkami. Ukážeme, že geometrický graf na n vrcholech bez tří disjunktních hran má nejvýše 2.5n hran. Tento výsledek je až na aditivní konstantu nejlepší možný.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)