Geometric Graphs with No Self-intersecting Path of Length Three

Pach, János and Pinchasi, Rom and Tardos, Gábor and Tóth, Géza (2002) Geometric Graphs with No Self-intersecting Path of Length Three. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 295-311 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_28).

Full text not available from this repository.

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(n log n). This result is asymptotically tight. Analogous questions for curvilinear drawings and for longer paths are also considered.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_28
Classifications:Z Theory > Z.999 Others
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
ID Code:223

Repository Staff Only: item control page

References

P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir, Quasiplanar graphs have a linear number of edges, Combinatorica 17 (1997), 1-9.

S. Avital and H. Hanani, Graphs (in Hebrew), Gilyonot Lematematika 3 (1966), 2-8.

B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978.

A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory, Ser. B 16 (1974), 97-105.

Z. Füredi, On a Turán type problem of Erdös, Combinatorica 11 1 (1991), 75-79.

Z. Füredi and P. Hajnal, Davenport-Schinzel theory of matrices, Discrete Mathematics 103 (1992), 233-251.

H. Hanani (C. Chojnacki), Über wesentlich unplättbare Kurven in dreidimensionalen Raume, Fundamenta Mathematicae 23 (1934), 135-142.

Y. Kupitz, Extremal Problems in Combinatorial Geometry, Aarhus University Lecture Notes Series 53, Aarhus University, Denmark, 1979.

J. Pach, Geometric graph theory, in: Surveys in Combinatorics, 1999 (J.D. Lamb and D.A. Preece, eds.), London Mathematical Society Lecture Notes 267, Cambridge University Press, Cambridge, 1999, 167-200.

J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427-439.

R. Pinchasi and R. Radoicic, On the number of edges in geometric graphs with no self-intersecting cycle of length 4, to appear.

G. Tardos, On the number of edges in a geometric graph with no short self-intersecting paths, to appear.

W.T. Tutte, Toward a theory of crossing numbers, J. Combinatorial Theory 8 (1970), 45-53.

P. Valtr, On geometric graphs with no k pairwise parallel edges, Discrete and Computational Geometry 19 (1998), 461-469.