Charles Explorer logo
🇨🇿

Geometrické grafy bez tří disjunktních hran

Publikace na Matematicko-fyzikální fakulta |
2005

Abstrakt

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ý.