The convex dimension of a graph

被引：10

作者：

Halman, Nir ^{[1
]}

Onn, Shmuel

Rothbjum, Uriel G.

机构：

[1] MIT, Cambridge, MA 02138 USA

[2] Technion Israel Inst Technol, IL-32000 Haifa, Israel

来源：

DISCRETE APPLIED MATHEMATICS | 2007年 / 155卷 / 11期

基金：

以色列科学基金会;

关键词：

graph embedding; discrete geometry; convex combinatorial optimization;

D O I：

10.1016/j.dam.2007.02.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The convex dimension of a graph G = (V, E) is the smallest dimension d for which G admits an injective map f : V -> R-d 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. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：1373 / 1383

页数：11