Connected Rectilinear Graphs on Point Sets

Mumford, Elena and Löffler, Maarten (2009) Connected Rectilinear Graphs on Point Sets. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 313-318(Official URL:

Full text not available from this repository.


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(n2 ) time

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_30
Classifications: G Algorithms and Complexity > G.560 Geometry

Actions (login required)

View Item View Item