Noncrossing Hamiltonian Paths in Geometric Graphs

Cerný, Jakub and Dvorák, Zdenek and Jelínek, Vít and Kára, Jan (2004) Noncrossing Hamiltonian Paths in Geometric Graphs. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 86-97 (Official URL:

Full text not available from this repository.


A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: Determine a function h, where h(n) is the largest number k such that when we remove arbitrary set of k edges from a complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that h(n) = \Omega (\sqrt{n}). We also determine the function exactly in case when the removed edges form a star or a matching, and give asymptotically tight bounds in case they form a clique.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_8
Classifications:Z Theory > Z.250 Geometry
ID Code:429

Repository Staff Only: item control page


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

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

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

J. Pach, R. Radoicic, G. Tardos, and G. Tóth: Geometric graphs with no self-intersecting path of length three, Graph Drawing, Lecture Notes in Computer Science 2528, Springer-Verlag, Berlin, 2002, 295-311

R. Pinchasi and R. Radoicic: On the number of edges in geometric graphs with no selfintersecting cycle of length 4, Proc. 19th Annual Symposium on Computational Geometry, submitted

G. Tardos: On the number of edges in geometric graph with no short self-intersecting paths, in preparation

P. Valtr: Graph drawings with no k pairwise crossing edges, Graph Drawing (Rome), Lecture Notes in Computer Science, vol. 1353 (1997), 205-218.