On the visibility graph of convex translates

DOI10.1016/S0166-218X(00)00270-5zbMath1003.68114MaRDI QIDQ5951963

Kiyoshi Hosono, David Rappaport, Henk G. Meijer

Publication date: 28 October 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

matchingvisibility graphHamiltonian path

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

The visibility graph of congruent discs is Hamiltonian ⋮ Visibility in crowds of translates of a centrally symmetric convex body ⋮ On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane

Cites Work

• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• On the perfect matching of disjoint compact sets by noncrossing line segments in \(\mathbb R^n\)
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Hamiltonian cycles in planar triangulations with no separating triangles
• Computational Geometry in C
• Growing a Tree from Its Branches
• Convex Polygons
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the visibility graph of convex translates