12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > On a class of metrics related to graph layout p...
View graph of relations

« Back

On a class of metrics related to graph layout problems

Research output: Contribution to journalJournal article

Published

Journal publication date2010
JournalLinear Algebra and its Applications
Journal number11-12
Volume433
Number of pages18
Pages1760-1777
Original languageEnglish

Abstract

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 characterize the unbounded edges of the convex hull and of its closure.