1. Connected rectilinear graphs on point sets
- Author
-
Löffler, M., Mumford, E., Tollis, I.G., Patrignani, M., and Algorithms
- Subjects
Combinatorics ,Set (abstract data type) ,Discrete mathematics ,symbols.namesake ,Existential quantification ,Perpendicular ,symbols ,Point (geometry) ,Pairwise comparison ,Space (mathematics) ,Connectivity ,Mathematics ,Planar graph - 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.
- Published
- 2009