Unavoidable Configurations in Complete Topological Graphs

Pach, János and Tóth, Géza (2001) Unavoidable Configurations in Complete Topological Graphs. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 328-337 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_31).

Full text not available from this repository.

Abstract

A topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by Jordan curves connecting the corresponding points, with the property that any two curves have at most one point in common. We define two canonical classes of topological complete graphs, and prove that every topological complete graph with n vertices has a canonical subgraph of size at least $c\log\log n$, which belongs to one of these classes. We also show that every complete topological graph with n vertices has a non-crossing subgraph isomorphic to any fixed tree with at most $c\log^{1/6}n$ vertices.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_31
Classifications:Z Theory > Z.999 Others
Z Theory > Z.750 Topology
ID Code:411

Repository Staff Only: item control page

References

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

D. Archdeacon and B. R. Richter: On the parity of crossing numbers, J. Graph Theory 12 (1988), 307-310.

Ch. J. Colbourn: On drawings of complete graphs, J. Combin. Inform. System Sci. 6 (1981), 169-172.

G. Gairns and Y. Nokolayevsky: Bounds for generalized thrackles, Discrete Comput. Geom. 23 (2000), 191-206.

G. Ehrlich , S. Even, and R. E. Tarjan: Intersection graphs of curves in the plane, J. Combinatorial Theory, Ser. B 21 (1976), 8-20.

P. Erdös and R. K. Guy: Crossing number problems, Amer. Math. Monthly 80 (1973), 52-58.

P. Erdös and A. Hajnal: Ramsey-type theorems, Discrete Appl. Math. 25 (1989), 37-52.

P. Erdös and G. Szekeres: A combinatorial problem in geometry, Compositio Mathematica 2 (1935), 463-470.

P. Erdös and G. Szekeres: On some extremum problems in elementary geometry, Ann. Universitatis Scientiarum Budapestinensis, Eötvös, Sectio Mathematica III-IV (1960-61), 53-62.

M. R. Garey and D. S. Johnson: Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 4 (1983), 312-316.

P. Gritzmann, B. Mohar, J. Pach, and P. Pollack: Embedding a planar triangulation with vertices at specified points, Amer. Math. Monthly 98 (1991), 165-166.

H.-D. Gronau and H. Harborth: Numbers of nonisomorphic drawings for small graphs, in: Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congr. Numer. 71 (1990), 105-114.

R. K. Guy: The decline and fall of Zarankiewicz's theorem, in: Proof Techniques in Graph Theory, Academic Press, New York, 1969, 63-69.

H. Harborth and I. Mengersen: Edges without crossings in drawings of complete graphs, J. Combinatorial Theory, Ser. B 17 (1974), 299-311.

H. Harborth and I. Mengersen: Edges with at most one crossing in drawings of complete graph, in: Topics in Combinatorics and Graph Theory (Oberwolfach, 1990), Physica, Heidelberg, 1990, 757-763.

H. Harborth and I. Mengersen: Drawings of the complete graph with maximum number of crossings, in: Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1992), Congr. Numer. 88 (1992), 225-228.

H. Harborth, I. Mengersen and R. H. Schelp: The drawing Ramsey number Dr(Kn), Australasian J. Combinatorics 11 (1995), 151-156.

H. Harborth and Ch. Thürmann: Minimum number of edges with at most s Crossings in drawings of the complete graph, in: Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics Graph Theory and Computing (Boca Raton, FL, 1994), Congr. Numer. 102 (1994), 83-90.

Y. S. Kupitz: Extremal Problems in Combinatorial Geometry, Lecture Notes Series 53, Aarhus Universitet, Matematisk Institut, Aarhus, 1979.

L. Lavász, J. Pach and M. Szegedy: On Conway's thrackle conjecture, Discrete and Computational Geometry 18 (1997), 369-376.

I. Mengersen: Die Maximalzahl von kreuzungsfreien Kanten in Darstellungen von vollständigen n-geteilten Graphen (German), Math. Nachr. 85 (1978), 131-139.

J. Pach: Geometric graph theory, in: Surveys in Combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser. 267, Cambridge Univ. Press, Cambridge, 1999, 167-200.

J. Pach and P. K. Agarwal: Combinatorial Geometry, Wiley-Interscience, New York, 1995.

J. Pach, F. Shahrokhi, and M. Szegedy: Application of crossing numbers, Algorithmica 16 (1996), 111-117.

J. Pach and J. Töröcsik: Some geometric applications of Dilworth's theorem, Discrete and Computational Geometry 12 (1994), 1-7.

J. Pach and G. Tòth: Which crossing number is it, anyway? Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, 617-626.

G. Ringel: Extremal problems in the theory of graphs, in: Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czechoslovak Acad. Sci., Prague, 1964, 85-90.

G. Tóth and P. Valtr: Note on the Erdös-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457-459.

P. Turán: A note of welcome, J. Graph Theopry 1 (1977), 7-9.

D. R. Woodall: Thrackles and deadlock, in: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London, 1971, 335-347.

A. T. White and L. W. Beineke: Topological graph theory, in: Selected Topics in Graph Theory (L. W. Beineke and R. J. Wilson., eds.), Academic Press, Inc. [Harcourt Brace Javanovich, Publishers], London-New York, 1983, 15-49.