19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

News on graphs of small and large distances

Presented by Mr. Filip MORIC
Type: Oral presentation
Track: Representations of Graphs


Given a set $P$ of $n$ points in a Euclidean space, let $d_1>d_2>...$ be the distances generated by the set. The graph of $k$-th largest distances on $P$ is a geometric graph with vertex set $P$ whose edges correspond to the pairs of points at distance $d_k$ (the graph of $k$-th smallest distances is defined analogously). The best studied instance of this notion are probably so called diameter graphs. We investigated the structure of large-distance graphs and proved several results concerning the number of cliques of certain size. We payed special attention to the case when $P$ is a set of points in the plane in convex position and showed that the number of smallest and second smallest distances in that case is bounded from above by n+O(1). (Joint work with János Pach)


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors