Title of article :
Geometric graphs with no self-intersecting path of length three
Author/Authors :
Pach، نويسنده , , Jلnos and Pinchasi، نويسنده , , Rom and Tardos، نويسنده , , Gلbor and Tَth، نويسنده , , Géza، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Abstract :
Let G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straight-line edges. It is shown that if G has no self-intersecting path of length 3, then its number of edges is O(nlogn). This result is asymptotically tight. Analogous questions for longer forbidden paths and for graphs drawn by not necessarily straight-line edges are also considered.
Journal title :
European Journal of Combinatorics
Journal title :
European Journal of Combinatorics