On the visibility graph of convex translates

DOI10.1016/S0166-218X(00)00270-5MaRDI QIDQ5951963zbMATH OpenFDO

Authors Kiyoshi Hosono, Henk Meijer, David Rappaport

Publication date 28 October 2002

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

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00270-5

zbMATH Keywords

Hamiltonian pathmatchingvisibility graph

Mathematics Subject Classification ID

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

Recommendations

• The visibility graph of congruent discs is Hamiltonian
• Segment endpoint visibility graphs are Hamiltonian
• scientific article; zbMATH DE number 4085050
• Two segment classes with Hamiltonian visibility graphs
• Minimal visibility graphs

Cites work

• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Computational Geometry in C
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Convex Polygons
• Graph theory
• Growing a Tree from Its Branches
• Hamiltonian cycles in planar triangulations with no separating triangles
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 1049272 (Why is no real title available?)
• On the perfect matching of disjoint compact sets by noncrossing line segments in \(\mathbb R^n\)

Cited in

(4)

• The visibility graph of congruent discs is Hamiltonian
• Tight bounds for visibility matching of \(f\)-equal width objects
• On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane
• Visibility in crowds of translates of a centrally symmetric convex body

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

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