The convex dimension of a graph |
| |
| Authors: | Nir Halman Shmuel Onn Uriel G Rothblum |
| |
| Institution: | a MIT—Massachusetts Institute of Technology, Cambridge, MA 02138, USA
b Technion—Israel Institute of Technology, 32000 Haifa, Israel |
| |
| Abstract: | The convex dimension of a graph G=(V,E) is the smallest dimension d for which G admits an injective map f:V?Rd of its vertices into d-space, such that the barycenters of the images of the edges of G are in convex position. The strong convex dimension of G is the smallest d for which G admits a map as above such that the images of the vertices of G are also in convex position. In this paper we study the convex and strong convex dimensions of graphs. |
| |
| Keywords: | Graph embedding Discrete geometry Convex combinatorial optimization |
| 本文献已被 ScienceDirect 等数据库收录！ |
