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 , 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

Actions (login required)

View Item View Item