Complete combinatorial characterization of greedy-drawable trees
| Autor: | Miyata, Hiroyuki, Nosaka, Reiya |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A (Euclidean) greedy drawing of a graph is a drawing in which, for any two vertices $s,t$ ($s \neq t$), there is a neighbor vertex of $s$ that is closer to $t$ than to $s$ in the Euclidean distance. Greedy drawings are important in the context of message routing in networks, and graph classes that admit greedy drawings have been actively studied. N\"{o}llenburg and Prutkin (Discrete Comput. Geom., 58(3), pp.543-579, 2017) gave a characterization of greedy-drawable trees in terms of an inequality system that contains a non-linear equation. Using the characterization, they gave a linear-time recognition algorithm for greedy-drawable trees of maximum degree $\leq 4$. However, a combinatorial characterization of greedy-drawable trees of maximum degree 5 was left open. In this paper, we give a combinatorial characterization of greedy-drawable trees of maximum degree $5$, which leads to a complete combinatorial characterization of greedy-drawable trees. Furthermore, we give a characterization of greedy-drawable pseudo-trees. It turns out that greedy-drawable pseudo-trees admit a simpler characterization than greedy-drawable trees. Comment: 16 pages, 17 fugures |
| Databáze: | arXiv |
| Externí odkaz: |
|