Abstract | ||
---|---|---|
We show that the visibility graph of a set of non-intersecting translates of the same compact convex object in R 2 always contains a Hamiltonian path. Furthermore, we show that every other edge in the Hamiltonian path can be used to obtain a perfect matching that is realized by a set of non-intersecting lines of sight. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1016/S0166-218X(00)00270-5 | Discrete Applied Mathematics |
Keywords | Field | DocType |
convex translates,visibility graph,computational geometry,hamiltonian path,matching | Graph theory,Discrete mathematics,Visibility,Combinatorics,Visibility graph,Hamiltonian path,Matching (graph theory),Triangulation (social science),Hamiltonian path problem,Factor-critical graph,Mathematics | Journal |
Volume | Issue | ISSN |
113 | 2-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
3 | 0.57 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kiyoshi Hosono | 1 | 60 | 11.01 |
Henk Meijer | 2 | 753 | 100.25 |
David Rappaport | 3 | 3 | 0.57 |