Series parallel linkages. (English) Zbl 1226.05131

Summary: We study spaces of realizations of linkages (weighted graphs) whose underlying graph is a series parallel graph. In particular, we describe an algorithm for determining whether or not such spaces are connected.


05C22 Signed and weighted graphs
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI arXiv Euclid


[1] M. Belk and R. Connelly, Realizability of graphs, Discrete Comput. Geom. 37(2) (2007), 125\Ndash137. · Zbl 1114.05067
[2] R. J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl. 10 (1965), 303\Ndash318. · Zbl 0128.37002
[3] D. Eppstein, Parallel recognition of series-parallel graphs, Inform. and Comput. 98(1) (1992), 41\Ndash55. · Zbl 0754.68056
[4] M. Farber, “Invitation to topological robotics” , Zurich Lectures in Advanced Mathematics, European Mathematical Society (EMS), Zürich, 2008. · Zbl 1148.55011
[5] J.-C. Hausmann, Sur la topologie des bras articulés, in: “Algebraic topology Poznań 1989” , Lecture Notes in Math. 1474 , Springer, Berlin, 1991, pp. 146\Ndash159. · Zbl 0736.57014
[6] J.-C. Hausmann and A. Knutson, The cohomology ring of polygon spaces, Ann. Inst. Fourier (Grenoble) 48(1) (1998), 281\Ndash321. · Zbl 0903.14019
[7] B. Hendrickson, The molecule problem: exploiting structure in global optimization, SIAM J. Optim. 5(4) (1995), 835\Ndash857. · Zbl 0844.05093
[8] M. Kapovich and J. Millson, On the moduli space of polygons in the Euclidean plane, J. Differential Geom. 42(2) (1995), 430\Ndash464. · Zbl 0854.51016
[9] J. McLaughlin, Moduli spaces of planar realizations of weighted graphs, Ph.D. thesis, National University of Ireland Galway (2009).
[10] R. J. Milgram and J. C. Trinkle, The geometry of configuration spaces for closed chains in two and three dimensions, Homology Homotopy Appl. 6(1) (2004), 237\Ndash267. · Zbl 1065.55010
[11] J. Milnor, “Morse theory” , Based on lecture notes by M. Spivak and R. Wells, Annals of Mathematics Studies 51 , Princeton University Press, Princeton, N.J., 1963. · Zbl 0108.10401
[12] J. Oxley, Graphs and series-parallel networks, in: “Theory of matroids” , Encyclopedia Math. Appl. 26 , Cambridge Univ. Press, Cambridge, 1986, pp. 97\Ndash126. · Zbl 0587.05020
[13] D. Shimamoto and C. Vanderwaart, Spaces of polygons in the plane and Morse theory, Amer. Math. Monthly 112(4) (2005), 289\Ndash31 · Zbl 1215.52012
[14] J. Valdes, R. E. Tarjan, and E. L. Lawler, The recognition of series parallel digraphs, SIAM J. Comput. 11(2) (1982), 298\Ndash313. · Zbl 0478.68065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.