Noncrossing Hamiltonian Paths in Geometric GraphsCerný, 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 2124, 2003 , pp. 8697(Official URL: http://dx.doi.org/10.1007/9783540245957_8). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540245957_8
AbstractA 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.
Actions (login required)
