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, Heraklion, Crete, Greece , pp. 313-318 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_30).
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
Repository Staff Only: item control page