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: http://dx.doi.org/10.1007/978-3-642-00219-9_30).

Full text not available from this repository.

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

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_30
Classifications: G Algorithms and Complexity > G.560 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/917

Actions (login required)

View Item View Item