Abstract
We constructively show that any cyclic Monge distance matrix can be represented as the graph distances between vertices on the outer face of a planar graph. The structure of the planar graph depends only on the number of rows of the matrix, and the weight of each edge is a fixed linear combination of constantly many matrix entries. We also show that the size of our constructed graph is worst-case optimal among all planar graphs.
| Original language | English |
|---|---|
| Title of host publication | Proc. 32nd Canadian Conference on Computational Geometry (CCCG) |
| Pages | 141-147 |
| Number of pages | 7 |
| Publication status | Published - 2020 |