On the visibility graph of convex translates

DOI10.1016/S0166-218X(00)00270-5zbMATH Open1003.68114MaRDI QIDQ5951963FDOQ5951963

Kiyoshi Hosono, David Rappaport, Henk Meijer

Publication date: 28 October 2002

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

Recommendations

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

zbMATH Keywords

matchingHamiltonian pathvisibility graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Computational Geometry in C
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hamiltonian cycles in planar triangulations with no separating triangles
• Convex Polygons
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Growing a Tree from Its Branches
• 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\)

Cited In (3)

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

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)