Geometric Graphs with No Selfintersecting Path of Length ThreePach, János and Pinchasi, Rom and Tardos, Gábor and Tóth, Géza (2002) Geometric Graphs with No Selfintersecting Path of Length Three. In: Graph Drawing 10th International Symposium, GD 2002, August 2628, 2002 , pp. 295311(Official URL: http://dx.doi.org/10.1007/3540361510_28). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540361510_28
AbstractLet G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straightline edges. It is shown that if G has no selfintersecting path of length 3, then its number of edges is O(n log n). This result is asymptotically tight. Analogous questions for curvilinear drawings and for longer paths are also considered.
Actions (login required)
