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

DOI10.1016/J.COMGEO.2016.05.004MaRDI QIDQ679748zbMATH OpenOpenAlexFDO

Authors Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel 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

spanning treesperfect matchingsHamiltonian cyclesgeodesic graphsnon-crossing graphs

Mathematics Subject Classification ID

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

Recommendations

• Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
• Maximum plane trees in multipartite geometric graphs
• Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane
• Maximum plane trees in multipartite geometric graphs
• On geometric independency trees for points in the plane

Cites work

• scientific article; zbMATH DE number 1507297 (Why is no real title available?)
• scientific article; zbMATH DE number 6789192 (Why is no real title available?)
• scientific article; zbMATH DE number 2209732 (Why is no real title available?)
• An optimal algorithm for plane matchings in multipartite geometric graphs
• Bipartite embeddings of trees in the plane
• Edge-removal and non-crossing configurations in geometric graphs
• Geodesic ham-sandwich cuts
• Geodesic-preserving polygon simplification
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimal Search in Planar Subdivisions
• Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane
• Relative convex hulls in semi-dynamic arrangements
• The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon
• The furthest-site geodesic Voronoi diagram
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes

Cited in

(3)

• Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
• Convex hulls in polygonal domains
• Geometric planar networks on bichromatic collinear points

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679748)