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
Pages :
19
From page :
793
To page :
811
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
Serial Year :
2004
Journal title :
European Journal of Combinatorics
Record number :
1549454
Link To Document :
بازگشت