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

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

On a class of metrics related to graph layout problems

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On a class of metrics related to graph layout problems. / Letchford, A N; Reinelt, G; Seitz, H et al.
In: Linear Algebra and its Applications, Vol. 433, No. 11-12, 2010, p. 1760-1777.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, AN, Reinelt, G, Seitz, H & Theis, DO 2010, 'On a class of metrics related to graph layout problems', Linear Algebra and its Applications, vol. 433, no. 11-12, pp. 1760-1777. https://doi.org/10.1016/j.laa.2010.06.038

APA

Letchford, A. N., Reinelt, G., Seitz, H., & Theis, D. O. (2010). On a class of metrics related to graph layout problems. Linear Algebra and its Applications, 433(11-12), 1760-1777. https://doi.org/10.1016/j.laa.2010.06.038

Vancouver

Letchford AN, Reinelt G, Seitz H, Theis DO. On a class of metrics related to graph layout problems. Linear Algebra and its Applications. 2010;433(11-12):1760-1777. doi: 10.1016/j.laa.2010.06.038

Author

Letchford, A N ; Reinelt, G ; Seitz, H et al. / On a class of metrics related to graph layout problems. In: Linear Algebra and its Applications. 2010 ; Vol. 433, No. 11-12. pp. 1760-1777.

Bibtex

@article{16e6c01d070f4850967219766544f340,
title = "On a class of metrics related to graph layout problems",
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.",
keywords = "metric spaces, graph layout problems, convex analysis, polyhedral combinatorics",
author = "Letchford, {A N} and G Reinelt and H Seitz and Theis, {D O}",
year = "2010",
doi = "10.1016/j.laa.2010.06.038",
language = "English",
volume = "433",
pages = "1760--1777",
journal = "Linear Algebra and its Applications",
publisher = "Elsevier Inc.",
number = "11-12",

}

RIS

TY - JOUR

T1 - On a class of metrics related to graph layout problems

AU - Letchford, A N

AU - Reinelt, G

AU - Seitz, H

AU - Theis, D O

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - metric spaces

KW - graph layout problems

KW - convex analysis

KW - polyhedral combinatorics

U2 - 10.1016/j.laa.2010.06.038

DO - 10.1016/j.laa.2010.06.038

M3 - Journal article

VL - 433

SP - 1760

EP - 1777

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

IS - 11-12

ER -