Long non-crossing configurations in the plane

DOI10.1007/s00454-010-9277-9zbMath1207.68416OpenAlexW2109075893MaRDI QIDQ603879

Adrian Dumitrescu, Csaba D. Tóth

Publication date: 8 November 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-010-9277-9

zbMATH Keywords

approximation algorithmnon-crossingHamiltonian cycle problemHamiltonian path problemmaximization problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

New variants of perfect non-crossing matchings, Euclidean maximum matchings in the plane -- local to global, On the Heaviest Increasing or Decreasing Subsequence of a Permutation, and Paths and Matchings on Weighted Point Sets, Maximum plane trees in multipartite geometric graphs, On the longest spanning tree with neighborhoods

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Noncrossing Hamiltonian paths in geometric graphs
• Ramsey-type results for geometric graphs. II
• Bipartite embeddings of trees in the plane
• Ramsey-type results for geometric graphs. I
• Improved bounds for planar \(k\)-sets and related problems
• On the number of line separations of a finite set in the plane
• Encompassing colored planar straight line graphs
• Point sets with many \(k\)-sets