examples/flexrilog_Motions_of_Graphs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FlexRiLoG - A SageMath Package for Motions of Graphs\n",
    "\n",
    "Georg Grasegger<sup>1</sup> and Jan Legerský<sup>2,3</sup>\n",
    "\n",
    " *<sup>1</sup> Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences*\n",
    " \n",
    " *<sup>2</sup>Johannes Kepler University Linz, Research Institute for Symbolic Computation (RISC)*\n",
    " \n",
    " *<sup>3</sup>Department of Applied Mathematics, Faculty of Information Technology, Czech Technical University in Prague*\n",
    "\n",
    "**Abstract**\n",
    "In this paper we present the <span style=\"font-variant:small-caps;\">SageMath</span> package <span style=\"font-variant:small-caps;\">FlexRiLoG</span> (short for flexible and rigid labelings of graphs).\n",
    "Based on recent results the software generates motions of graphs\n",
    "using special edge colorings.\n",
    "The package computes and illustrates the colorings and the motions.\n",
    "We present the structure and usage of the package.\n",
    "$$\n",
    "\\newcommand{\\RR}{\\mathbb{R}}\n",
    "\\DeclareMathOperator{\\Upairs}{U}\n",
    "\\newcommand{\\upairs}[1]{\\Upairs(#1)}\n",
    "\\DeclareMathOperator{\\CDC}{CDC}\n",
    "\\newcommand{\\cdc}[1]{\\CDC(#1)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook is an interactive version of the paper *FlexRiLoG - A SageMath Package for Motions of Graphs* (doi:[10.1007/978-3-030-52200-1_44](https://doi.org/10.1007/978-3-030-52200-1_44)). It can be launched on-line using Binder:\n",
    "\n",
    "[![Binder](https://mybinder.org/badge_logo.svg)](https://jan.legersky.cz/flexrilogICMS2020)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1   Introduction\n",
    "A graph with a placement of its vertices in the plane is considered to be flexible if \n",
    "the placement can be\n",
    "continuously deformed by an edge length preserving motion into a non-congruent\n",
    "placement.\n",
    "The study of such graphs and their motions has a long history \n",
    "(see for instance ([Burmester 1893](#ref-Burmester1893), [Dixon 1899](#ref-Dixon), [Kempe 1877](#ref-Kempe1877), [Stachel 2013](#ref-Stachel), [Walter and Husty 2007](#ref-WalterHusty), [Wunderlich 1954](#ref-Wunderlich1954), [Wunderlich 1976](#ref-Wunderlich1976), [Wunderlich 1981](#ref-Wunderlich1981))).\n",
    "Recently we provided a series of results ([Grasegger, Legerský, and Schicho 2019a](#ref-flexibleLabelings), [(Grasegger, Legerský, and Schicho 2019b](#ref-movableGraphs)) \n",
    "with a deeper analysis of the existence of flexible placements.\n",
    "This is done via special edge colorings called\n",
    "NAC-colorings (“No Almost Cycles”, see ([Grasegger, Legerský, and Schicho 2019a](#ref-flexibleLabelings))).\n",
    "These colorings classify the existence of\n",
    "a flexible placement in the plane and give a construction of the motion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Basic definitions**\n",
    "\n",
    "We briefly give a precise definition of flexibility of a graph. \n",
    "A *framework* is a pair $(G,p)$\n",
    "where $G=(V_G,E_G)$ is a graph and $p : V_G \\rightarrow \\RR^2$\n",
    "is a *placement* of $G$ in $\\RR^2$.\n",
    "The placement might be possibly non-injective but for all edges $uv \\in E_G$ we require $p(u) \\neq p(v)$. \n",
    "\n",
    "Two frameworks $(G,p)$ and $(G,q)$ are *equivalent* if \n",
    "for all $uv \\in E_G$,\n",
    "\\begin{align}\\label{eq:equivalence}\n",
    "\t\\| p(u) - p(v) \\| = \\| q(u) - q(v)\\|\\,.\n",
    "\\end{align}\n",
    "Two placements $p,q$ of $G$ are said to be *congruent* if the equation above holds for all pairs of vertices $u,v \\in V_G$.\n",
    "Equivalently, $p$ and $q$ are congruent if there exists a Euclidean isometry $M$ of $\\RR^2$ such that $M q(v) = p(v)$ for all $v \\in V_G$.\n",
    "\n",
    "A *flex* of the framework $(G,p)$ is a continuous path $t \\mapsto p_t$, $t \\in [0,1]$,\n",
    "in the space of placements of $G$ such that $p_0= p$ and each $(G,p_t)$ is equivalent to $(G,p)$.\n",
    "The flex is called trivial if $p_t$ is congruent to $p$ for all $t \\in [0,1]$.\n",
    "\n",
    "We define a framework to be *flexible* if there is a non-trivial flex in $\\RR^2$.\n",
    "Otherwise is is called *rigid*.\n",
    "We say that a labeling $\\lambda: E_G\\rightarrow \\RR_{>0}$ of a graph $G$ is *flexible*\n",
    "if there is a flexible framework $(G,p)$ such that \n",
    "$p$ induces $\\lambda$, namely, $\\|p(u) - p(v) \\| = \\lambda(uv)$ for all $uv\\in E_G$.\n",
    "On the other hand,  $\\lambda$ is *rigid* if $(G,p)$ is rigid for all placements $p$ inducing $\\lambda$.\n",
    "A flexible labeling $\\lambda$ of a graph is *proper* if there exists a framework $(G,p)$ such that \n",
    "$p$ induces $\\lambda$ and it has a non-trivial flex with all but finitely many placements being injective. \n",
    "We call a graph *movable* if it has a proper flexible labeling."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Outline of the paper**\n",
    "\n",
    "We have given the necessary definitions.\n",
    "[Section 2](#2-The-Package) describes the main functionality of the <span style=\"font-variant:small-caps;\">FlexRiLoG</span> dealing with colorings and motions.\n",
    "In this paper we do not provide the algorithms themselves but refer to the respective theorems and literature.\n",
    "In [Section 3](#3-Movable-graphs) we describe how to use the package to ask for movable graphs.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 The Package\n",
    "\n",
    "<span style=\"font-variant:small-caps;\">FlexRiLoG</span> ([Grasegger and Legerský 2020a](#ref-flexrilog))\n",
    "is a package for <span style=\"font-variant:small-caps;\">SageMath</span> running in versions 8.9 and 9.0 ([The Sage Developers 2020](#ref-sagemath)).\n",
    "The latest release of the package can be installed by executing:\n",
    "\n",
    "``\n",
    "sage -pip install --upgrade flexrilog\n",
    "``\n",
    "\n",
    "The development version of <span style=\"font-variant:small-caps;\">FlexRiLoG</span> can be found in the repository ([Grasegger and Legerský 2020b](#ref-flexrilogGitHub)),\n",
    "where also other options of installation are described.\n",
    "\n",
    "A convenient way of using the package instead of the ``sage`` console is a Jupyter notebook\n",
    "(coming with \\sage, launch by ``sage -n jupyter``).\n",
    "The file ``examples/flexrilog_Motions_of_Graphs.ipynb`` in ([Grasegger and Legerský 2020b](#ref-flexrilogGitHub))\n",
    "provides a Jupyter notebook version of this paper\n",
    "(see [https://jan.legersky.cz/flexrilogICMS2020](https://jan.legersky.cz/flexrilogICMS2020)\n",
    "redirecting to a version of the notebook executable on-line using Binder).\n",
    "\n",
    "The package allows to check whether a graph has a NAC-coloring, in particular to list all of them.\n",
    "A motion or flex obtained from a NAC-coloring can be constructed and displayed.\n",
    "Moreover, it implements the results of ([(Grasegger, Legerský, and Schicho 2019b)](#ref-movableGraphs)) regarding the existence of proper flexible labelings,\n",
    "namely, the check of a necessary condition and construction of a proper flex from a pair of NAC-colorings.\n",
    "There is also functionality providing tools for classification of all proper flexible labeling,\n",
    "which is out of the scope of this paper (see ([Grasegger, Legerský, and Schicho 2020](#ref-ClassificationPaper)) for details). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Data types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The package provides data types in different classes for dealing with graphs, colorings and motions.\n",
    "In order to use the data types provided by the package, they have to be loaded."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sys.path.insert(0, \"..\") #this is necessary if flexrilog is not installed, only downloaded\n",
    "from flexrilog import FlexRiGraph, GraphMotion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main object will always be of type ``FlexRiGraph``.\n",
    "This class inherits properties of the standard ``Graph`` from <span style=\"font-variant:small-caps;\">SageMath</span> \n",
    "and adds specific properties for investigations of flexibility and rigidity.\n",
    "In this paper we focus on the flexibility part.\n",
    "A ``FlexRiGraph`` can be constructed by the following command."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "FlexRiGraph([[0,1],[1,2],[0,2]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Further constructions can be made via integer encoding described in ([Capco et al. 2018](#ref-ZenodoAlg)) and via objects of the standard ``Graph`` class.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "FlexRiGraph(graphs.CompleteBipartiteGraph(2,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Besides the class for graphs there is a class for colorings (``NACcoloring``).\n",
    "We do not discuss the class itself here but rather show how to compute colorings of graphs (see [Section 2.2](#2.2-NAC-colorings)).\n",
    "Furthermore, motions are stored in a third class, ``GraphMotion``. They are discussed in [Section 2.3](#2.3-Constructing-Motions).\n",
    "The ``GraphGenerator`` class stores the code for some important graphs from the area of rigidity and flexibility theory.\n",
    "We do not go into detail but some of the graphs are used in the paper."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 NAC-colorings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NAC-colorings are a special type of edge colorings using two colors.\n",
    "Unlike proper edge colorings in Graph Theory we do not require incident edges to have different colors.\n",
    "\n",
    "**Definition 1.**\n",
    "*Let $G$ be a graph. A coloring of edges $\\delta\\colon  E_G\\rightarrow \\{\\text{blue, red}\\}$*\n",
    "*is called a* NAC-coloring,\n",
    "*if it is surjective and for every cycle in $G$, either all edges have the same color, or there are at least 2 edges in each color.*\n",
    "\n",
    "<span style=\"font-variant:small-caps;\">FlexRiLoG</span> contains functionality for computing and showing NAC-col\\-or\\-ings of a given graph.\n",
    "The standard output is a textual list but the colorings can be shown in figures as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "C4 = FlexRiGraph([[0,1],[1,2],[2,3],[0,3]])\n",
    "C4.NAC_colorings()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C4.set_pos({0:(0,0), 1:(1,0), 2:(1,1), 3:(0,1)}) # this is to fix the positions of the vertices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "C4.show_all_NAC_colorings()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It can be checked in polynomial time whether a coloring is a NAC-coloring\n",
    "using  ([Grasegger, Legerský, and Schicho 2019a, Lemma 2.4](#ref-flexibleLabelings)).\n",
    "Hence, the question if a graph has a NAC-coloring is in NP,\n",
    "but it is subject to further investigations whether there is a polynomial time algorithm for a general graph.\n",
    "For instance every graph that is not generically rigid has a NAC-coloring due to Theorem 1.\n",
    "It can be checked in polynomial time whether a graph is generically rigid ([Jacobs and Hendrickson 1997](#ref-Jacobs)).\n",
    "\n",
    "In order to compute all NAC-colorings, lists of edges that necessarily have the same color\n",
    "due to being in 3-cycles (so called *$\\triangle$-connected components*, see ([Grasegger, Legerský, and Schicho 2019a](#ref-flexibleLabelings)))\n",
    "are determined. So far, we then test all possible combinations how to color them by red and blue.\n",
    "The edges colored the same in the following picture must have the same color in any NAC-coloring,\n",
    "but no combination satisfies the conditions of NAC-coloring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from flexrilog import GraphGenerator\n",
    "N = GraphGenerator.NoNACGraph()\n",
    "N.has_NAC_coloring()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N.plot(show_triangle_components=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For graphs with symmetries we get many similar colorings, in a sense that after applying the symmetry one NAC-coloring yields the other.\n",
    "We call such NAC-colorings isomorphic.\n",
    "In order to visualize this, NAC-colorings can be named so that isomorphic ones have the same Greek letter but differ by their index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C4.set_NAC_colorings_names()\n",
    "C4.NAC_colorings_isomorphism_classes()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Constructing Motions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a NAC-coloring we are able to construct a motion. The following result from ([Grasegger, Legerský, and Schicho 2019a](#ref-flexibleLabelings)) describes the relation.\n",
    "\n",
    "**Theorem 1.**\n",
    "*A connected non-trivial graph has a flexible labeling if and only if it has a NAC-coloring.*\n",
    "\n",
    "The main idea to construct a flex is to place the vertices on a grid in such a way that all the edges lie on grid lines.\n",
    "This can be achieved by placing vertices according to the color component of the graph.\n",
    "For color components we remove all edges of the other color and then take connected components of the remaining graph.\n",
    "Then all vertices which lie in the same red component are placed in the same column of the grid and\n",
    "all vertices from the same blue component are placed in the same row of the grid.\n",
    "By this procedure each vertex is assigned a unique grid point and all edges of the graph lie on the grid lines.\n",
    "In <span style=\"font-variant:small-caps;\">FlexRiLoG</span> this can be done with the classmethod ``GraphMotion.GridConstruction``.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from flexrilog import GraphMotion, GraphGenerator\n",
    "P = GraphGenerator.ThreePrismGraph()\n",
    "delta = P.NAC_colorings()[0]\n",
    "motion_P = GraphMotion.GridConstruction(P, delta)\n",
    "motion_P.parametrization()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is also the option to generate an animated SVG showing the NAC-coloring,\n",
    "which is automatically displayed when used in a Jupyter notebook (the picture below is a screenshot).\n",
    "If the ``fileName`` is specified, the SVG animation is stored and a web browser can be used to view it.\n",
    "Note that not all web browsers support SVG animations.\n",
    "It can be chosen, whether the edges are colored according to the NAC-coloring in use.\n",
    "The package also distinguishes the vertex layout depending on whether it is drawing a graph having no specific placement properties (dark vertices),\n",
    "or drawing a motion, in which edge lengths are fixed (light vertices)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_P.animation_SVG(edge_partition=\"NAC\",\n",
    "                       fileName=\"3-prism_grid\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More generally the base points of the grid can be chosen arbitrarily to get a zig-zag grid.\n",
    "This can be used to avoid degenerate subgraphs.\n",
    "Base points consist of two lists. The standard values consists of lists with points $(i,0)$ and $(0,i)$ respectively.\n",
    "Using them we get a rectangular initial grid.\n",
    "A zig-zag grid in general does not need to be initially rectangular.\n",
    "It is uniquely determined by the base points and drawing parallel lines.\n",
    "Doing so the grid consists of parallelograms.\n",
    "Usually the grid itself is not easily visible from the output motion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_P = GraphMotion.GridConstruction(P, delta, \n",
    "    zigzag=[[[0,0], [3/4,1/2], [2,0]], \n",
    "            [[0,0], [1,0]]])\n",
    "motion_P.animation_SVG(edge_partition=\"NAC\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3 Movable graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the grid construction, non-adjacent vertices might overlap, i.e., the constructed framework is not proper.\n",
    "Note, that this cannot be avoided by zig-zag constructions either but depends solely on the NAC-coloring in use.\n",
    "For some graphs all NAC-colorings result in overlapping vertices.\n",
    "In <span style=\"font-variant:small-caps;\">FlexRiLoG</span> it can be checked whether this is the case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P.has_injective_grid_construction()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q1 = GraphGenerator.Q1Graph()\n",
    "Q1.has_injective_grid_construction()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For some graphs, a proper flexible labeling exists due to the following lemma ([(Grasegger, Legerský, and Schicho 2019b)](#ref-movableGraphs)),\n",
    "which relates movability to spatial embeddings.\n",
    "\n",
    "**Lemma 1.**\n",
    "*Let $G$ be a graph with an injective embedding $\\omega:V_G\\rightarrow\\RR^3$ such that for every edge $uv\\in E_G$, the vector $\\omega(u)-\\omega(v)$ is parallel to one of the four vectors $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, $(-1,-1,-1)$, and all four directions are present. Then $G$ is movable. Moreover, there exist two NAC-colorings of $G$ such that two edges are parallel in the embedding $\\omega$ if and only if they receive the same pair of colors.*\n",
    "\n",
    "The package tries to construct such a spatial embedding for all pairs of NAC-colorings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inj, nacs = Q1.has_injective_spatial_embedding(certificate=True); inj"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphics_array([d.plot() for d in nacs])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the spatial embedding we can construct a motion of the graph.\n",
    "The motion can be transformed in such a way that a particular edge is fixed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_Q1 = GraphMotion.SpatialEmbeddingConstruction(Q1, nacs)\n",
    "motion_Q1.fix_edge([5,6])\n",
    "motion_Q1.parametrization()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_Q1.animation_SVG()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Besides the sufficient condition on movability above, there is also a necessary condition given in ([(Grasegger, Legerský, and Schicho 2019b)](#ref-movableGraphs)).\n",
    "For this condition we consider all NAC-colorings and look for monochromatic paths.\n",
    "Adding certain edges according to these paths we get a bigger graph with similar movability properties.\n",
    "\n",
    "For a graph $G$, let $\\upairs{G}$ denote the set of all pairs $\\{u,v\\}\\subset V_G$ such that $uv\\notin E_G$ and \n",
    "there exists a path from $u$ to $v$ which is monochromatic for all NAC-colorings $\\delta$ of $G$.\t\n",
    "If there exists a sequence of graphs $G_0, \\dots, G_n$ such that\n",
    "\t$G=G_0$,\n",
    "\t$G_i=(V_{G_{i-1}},E_{G_{i-1}} \\cup \\upairs{G_{i-1}})$ for $i\\in\\{1,\\dots,n\\}$, and\n",
    "\t$\\upairs{G_n}=\\emptyset$,\n",
    "then the graph $G_n$ is called *the constant distance closure of $G$*, denoted by $\\cdc{G}$.\n",
    "\n",
    "**Theorem 2.**\n",
    "*A graph $G$ is movable if and only if $\\cdc{G}$ is movable. Particularly, if $\\cdc{G}$ is the complete graph, then $G$ is not movable.*\n",
    "\n",
    "We can see that the following graph $G$ is not movable\n",
    "($G_1$ has no NAC-coloring since $\\{3,4\\},\\{5,6\\}\\in \\upairs{G}$, \n",
    "hence, $\\upairs{G_1}$ are all non-edges of $G_1$). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = GraphGenerator.MaxEmbeddingsLamanGraph(7)\n",
    "G.show_all_NAC_colorings()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.constant_distance_closure().is_complete()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "We gave a brief overview of the package and therefore did not cover all functionality.\n",
    "The package contains a documentation.\n",
    "As research in the field of flexible and movable graphs is going on the package is further developed,\n",
    "both regarding improvements as well as new functionality (for instance $n$-fold rotationally symmetric frameworks, see ([Dewar, Grasegger, and Legerský 2020](#ref-RotSymmetry))).\n",
    "The most current version of <span style=\"font-variant:small-caps;\">FlexRiLoG</span> can be found in ([Grasegger and Legerský 2020b](#ref-flexrilogGitHub)).\n",
    "\n",
    "**Acknowledgments**\n",
    "\n",
    "This project was supported by the Austrian Science Fund (FWF): P31061, P31888 and W1214-N15, \n",
    "and by the Ministry of Education, Youth and Sports of the Czech Republic, project no. CZ.02.1.01/0.0/ 0.0/16\\_019/0000778.\n",
    "The project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 675789."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "<a name=\"ref-Burmester1893\"></a>\n",
    "Burmester, L. 1893. \"Die Brennpunktmechanismen.\" *Zeitschrift Für\n",
    "Mathematik Und Physik* 38: 193–223.\n",
    "\n",
    "<a name=\"ref-ZenodoAlg\"></a>\n",
    "Capco, J., Gallet, M., Grasegger, G., Koutschan, C., Lubbes, N.,\n",
    "and Schicho, J. 2018. \"An algorithm for computing the number\n",
    "of realizations of a Laman graph.\" Zenodo.\n",
    "<https://doi.org/10.5281/zenodo.1245506>.\n",
    "\n",
    "<a name=\"ref-RotSymmetry\"></a>\n",
    "Dewar, S., Grasegger, G., and Legerský, J. 2020. \"Flexible\n",
    "Placements of Graphs with Rotational Symmetry.\"\n",
    "<https://arxiv.org/abs/2003.09328>\n",
    "\n",
    "<a name=\"ref-Dixon\"></a>\n",
    "Dixon, A. C. 1899. \"On certain deformable frameworks.\" *Messenger* 29\n",
    "(2): 1–21.\n",
    "\n",
    "<a name=\"ref-ClassificationPaper\"></a>\n",
    "Grasegger, G., Legerský, J., and Schicho, J. 2020. \"On the\n",
    "Classification of Motions of Paradoxically Movable Graphs.\"\n",
    "<https://arxiv.org/abs/2003.11416>\n",
    "\n",
    "<a name=\"ref-flexrilog\"></a>\n",
    "Grasegger, G., and Legerský, J. 2020a. \"FlexRiLoG — package for\n",
    "Flexible and Rigid Labelings of Graphs.\" Zenodo.\n",
    "<https://doi.org/10.5281/zenodo.3078757>\n",
    "\n",
    "<a name=\"ref-flexrilogGitHub\"></a>\n",
    "Grasegger, G., and Legerský, J. 2020b. \"FlexRiLoG — package for Flexible and Rigid\n",
    "Labelings of Graphs, repository.\"\n",
    "<https://github.com/Legersky/flexrilog/>.\n",
    "\n",
    "<a name=\"ref-flexibleLabelings\"></a>\n",
    "Grasegger, G., Legerský, J., and Schicho, J. 2019a. \"Graphs with Flexible\n",
    "Labelings.\" *Discrete & Computational Geometry* 62 (2): 461–80.\n",
    "<https://doi.org/10.1007/s00454-018-0026-9>.\n",
    "\n",
    "<a name=\"ref-movableGraphs\"></a>\n",
    "Grasegger, G., Legerský, J., and Schicho, J. 2019b. \"Graphs with Flexible Labelings allowing Injective\n",
    "Realizations.\" *Discrete Mathematics* 343 (6), Art. 111713.\n",
    "<https://doi.org/10.1016/j.disc.2019.111713>.\n",
    "\n",
    "<a name=\"ref-Jacobs\"></a>\n",
    "Jacobs, D.J., Hendrickson, B. 1997. \"An algorithm for two-dimensional rigidity percolation: The pebble game.\" *Journal of Computational Physics* 137 (2): 346-365.\n",
    "<https://doi.org/10.1006/jcph.1997.5809>.\n",
    "\n",
    "<a name=\"ref-Kempe1877\"></a>\n",
    "Kempe, A. B. 1877. \"On Conjugate Four-piece Linkages.\" *Proceedings of\n",
    "the London Mathematical Society* s1-9 (1): 133–49.\n",
    "<https://doi.org/10.1112/plms/s1-9.1.133>.\n",
    "\n",
    "<a name=\"ref-Stachel\"></a>\n",
    "Stachel, H. 2013. \"On the Flexibility and Symmetry of Overconstrained\n",
    "Mechanisms.\" *Philosophical Transactions of the Royal Society of London\n",
    "A: Mathematical, Physical and Engineering Sciences* 372.\n",
    "<https://doi.org/10.1098/rsta.2012.0040>.\n",
    "\n",
    "<a name=\"ref-sagemath\"></a>\n",
    "The Sage Developers. 2020. *SageMath, the Sage Mathematics Software\n",
    "System (Version 9.0)*. <https://www.sagemath.org>.\n",
    "\n",
    "<a name=\"ref-WalterHusty\"></a>\n",
    "Walter, D., and Husty, M. L. 2007. \"On a Nine-Bar Linkage, Its Possible\n",
    "Configurations and Conditions for Paradoxical Mobility.\" In *12th World\n",
    "Congress on Mechanism and Machine Science, Iftomm*.\n",
    "\n",
    "<a name=\"ref-Wunderlich1954\"></a>\n",
    "Wunderlich, W. 1954. \"Ein merkwürdiges Zwölfstabgetriebe.\"\n",
    "*Österreichisches Ingenieur-Archiv* 8: 224–28.\n",
    "\n",
    "<a name=\"ref-Wunderlich1976\"></a>\n",
    "Wunderlich, W. 1976. \"On Deformable Nine-Bar Linkages with Six Triple\n",
    "Joints.\" *Indagationes Mathematicae (Proceedings)* 79 (3): 257–62.\n",
    "<https://doi.org/10.1016/1385-7258(76)90052-4>.\n",
    "\n",
    "<a name=\"ref-Wunderlich1981\"></a>\n",
    "Wunderlich, W. 1981. \"Mechanisms Related to Poncelet's Closure Theorem.\"\n",
    "*Mechanisms and Machine Theory* 16 (6): 611–20.\n",
    "<https://doi.org/10.1016/0094-114X(81)90067-7>."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.0",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": true,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {
    "height": "143px",
    "width": "207px"
   },
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}