Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon

DOI10.1016/j.comgeo.2016.05.004zbMath1378.05024OpenAlexW2362274435MaRDI QIDQ679748

Prosenjit Bose, Ahmad Biniaz, Anil Maheshwari, Michiel H. M. Smid

Publication date: 19 January 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2016.05.004

zbMATH Keywords

Hamiltonian cyclesperfect matchingsspanning treesgeodesic graphsnon-crossing graphs

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

Plane bichromatic trees of low degree ⋮ Geometric planar networks on bichromatic collinear points ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relative convex hulls in semi-dynamic arrangements
• Geodesic ham-sandwich cuts
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• The furthest-site geodesic Voronoi diagram
• Bipartite embeddings of trees in the plane
• Computing a geodesic two-center of points in a simple polygon
• Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane
• The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon
• An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs
• Optimal Search in Planar Subdivisions
• GEODESIC-PRESERVING POLYGON SIMPLIFICATION
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes

This page was built for publication: Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon