Copyright 2008 INIST-CNRS CC BY 4.0 Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Mathematics
Accession Number:
edscal.18788144
Database:
PASCAL Archive
Weitere Informationen
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 the largest number h(n) such that when we remove any set of h (n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that h in)≥ (1 /2√2)√n. We also establish several results related to special classes of geometric graphs. Let h1(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h1 (n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that 1 √2√n < h1 (n) <3√n. Let h2(n) denote the largest number such that when we remove an arbitrary star with at most h2 (n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h2(n) = [n /2]- 1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.
