On a class of metrics related to graph layout problems

Details On a class of metrics related to graph layout problems On a class of metrics related to graph layout problems

2007-09-06

arxiv.org/abs/0709.0910v4

Mathematics

Combinatorics

Linear Algebra & Applications

Scientific paper

We examine the metrics that arise when a finite set of points is embedded in the real line, in such a way that the distance between each pair of points is at least 1. These metrics are closely related to some other known metrics in the literature, and also to a class of combinatorial optimization problems known as graph layout problems. We prove several results about the structure of these metrics. In particular, it is shown that their convex hull is not closed in general. We then show that certain linear inequalities define facets of the closure of the convex hull. Finally, we characterise the unbounded edges of the convex hull and of its closure.

Affiliated with

Also associated with

No associations

Rating

On a class of metrics related to graph layout problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a class of metrics related to graph layout problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a class of metrics related to graph layout problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-658204