Connected rectilinear graphs on point sets

M. Löffler; E. Mumford

doi:10.1007/978-3-642-00219-9_30

Connected rectilinear graphs on point sets

M. Löffler, E. Mumford

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

Abstract

Given n points in d-dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d¿=¿2 we present an algorithm for computing these directions (if they exist) in O (n 2) time.

Original language	English
Title of host publication	Graph Drawing (16th International Symposium, GD'08, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers)
Editors	I.G. Tollis, M. Patrignani
Place of Publication	Berlin
Publisher	Springer
Pages	313-318
ISBN (Print)	978-3-642-00218-2
DOIs	https://doi.org/10.1007/978-3-642-00219-9_30
Publication status	Published - 2009

Publication series

Name	Lecture Notes in Computer Science
Volume	5417
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-00219-9_30

Cite this

@inproceedings{f8a3b476a7f64c26bdb9414f97a61b5d,

title = "Connected rectilinear graphs on point sets",

abstract = "Given n points in d-dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d¿=¿2 we present an algorithm for computing these directions (if they exist) in O (n 2) time.",

author = "M. L{\"o}ffler and E. Mumford",

year = "2009",

doi = "10.1007/978-3-642-00219-9_30",

language = "English",

isbn = "978-3-642-00218-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "313--318",

editor = "I.G. Tollis and M. Patrignani",

booktitle = "Graph Drawing (16th International Symposium, GD'08, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers)",

address = "Germany",

}

Connected rectilinear graphs on point sets. / Löffler, M.; Mumford, E.

Graph Drawing (16th International Symposium, GD'08, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers). ed. / I.G. Tollis; M. Patrignani. Berlin : Springer, 2009. p. 313-318 (Lecture Notes in Computer Science; Vol. 5417).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Connected rectilinear graphs on point sets

AU - Löffler, M.

AU - Mumford, E.

PY - 2009

Y1 - 2009

N2 - Given n points in d-dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d¿=¿2 we present an algorithm for computing these directions (if they exist) in O (n 2) time.

AB - Given n points in d-dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d¿=¿2 we present an algorithm for computing these directions (if they exist) in O (n 2) time.

U2 - 10.1007/978-3-642-00219-9_30

DO - 10.1007/978-3-642-00219-9_30

M3 - Conference contribution

SN - 978-3-642-00218-2

T3 - Lecture Notes in Computer Science

SP - 313

EP - 318

BT - Graph Drawing (16th International Symposium, GD'08, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers)

A2 - Tollis, I.G.

A2 - Patrignani, M.

PB - Springer

CY - Berlin

ER -