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.

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
ID Code:917

Repository Staff Only: item control page

References

Durocher, S., Kirkpatrick, D.: On the hardness of turn-angle-restricted rectilinear cycle cover problems. In: CCCG 2002. pp. 13–16 (2002)

Edelsbrunner, H., Guibas, L.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38, 165–194 (1989)

Efrat, A., Erten, C., Kobourov, S.: Fixed-location circular-arc drawing of planar graphs. In: Liotta G. (ed.)GD 2003. LNSC, vol. 2912, pp. 147–158, Springer, Heidelberg (2004)

Fekete, S., Woeginger, G.: Angle-restricted tours in the

plane. Comput. Geom. Theory Appl. 8(4), 195–218 (1997)

Fredman, M.: How good is the information theory bound in sorting? Theoret. Comput. Sci. 1, 355–361

(1976)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. on Computing 31(2), 601–625 (2002)

Hoffman, F., Kriegel, K.: Embedding rectilinear graphs in linear time. Inf. Process. Lett. 29(2), 75–79 (1988)

Jansen, K., Woeginger, G.: The complexity of detecting crossingfree configurations in the plane. BIT 33(4), 580–595 (1993)

Löffler, M., Mumford, E.: Connected rectilinear polygons on point sets (2008), http://www.cs.uu.nl/research/techreps/UU-CS-2008-028.html

O’Rourke, J.: Uniqueness of orthogonal connect-the-dots. In: Toussaint, G. (ed.) Computational Morphology, pp. 97–104 (1988)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. In: Whitesides, S. (ed.) GD 1998. LNCS, vol. 1547, pp. 263–274 (1998)

Rappaport, D.: On the complexity of computing orthogonal polygons from a set of points. Technical Report TR-SOCS-86.9, McGill Univ., Montreal, PQ (1986)

Vijayan, G., Wigderson, A.: Rectilinear graphs and their embeddings. SIAM J. on Computing 14(2), 355–372 (1985)