Cerný, Jakub and Dvorák, Zdenek and Jelínek, Vít and Kára, Jan (2004) Noncrossing Hamiltonian Paths in Geometric Graphs. [Conference Paper]
Full text not available from this repository.
Abstract
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 |
|---|---|
| Classifications: | Z Theory > Z.250 Geometry |
| ID Code: | 429 |
| Deposited By: | Maciejak, Agnes |
| Deposited On: | 06 Dec 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=86 |
Repository Staff Only: item control page
