<figure><img src="image_1.png" /></figure>

HAL
open science

# Constraint-preserving labeled graph transformations for topology-based geometric modeling

Thomas Bellet, Agnès Arnould, Pascale Le Gall

<figure><img src="image_2.png" /></figure>

## To cite this version:

Thomas Bellet, Agnès Arnould, Pascale Le Gall. Constraint-preserving labeled graph transformations for topology-based geometric modeling. [Research Report] XLIM. 2017. hal-01476860

HAL Id: hal-01476860

https://hal.science/hal-01476860

Submitted on 26 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Constraint-preserving labeled graph transformations
for topology-based geometric modeling

Thomas Bellet$^a$, Agnès Arnould$^b$, Pascale Le Gall$^a$

$^a$Laboratory Mathematics in Interaction with Computer Science (MICS), CentraleSupélec, Université Paris Saclay, France

$^b$Laboratory XLIM UMR CNRS 7252, University of Poitiers, France

**Abstract**

As labeled graphs are particularly well adapted to represent objects in the context of topology-based geometric modeling, graph transformation theory is an adequate framework to implement modeling operations and check their consistency. In this article, objects are defined as a particular subclass of labeled graphs in which arc labels encode their topological structure (i.e. cell subdivision: vertex, edge, face, etc.) and node labels encode their embedding (i.e. relevant data: vertex positions, face colors, volume density, etc.). Object consistency is therefore defined by labeling constraints which must be preserved along modeling operations that modify topology and/or embedding. In this article, we define a class of graph transformation rules dedicated to embedding computations. Dedicated graph transformation variables allow us to access the existing embedding from the underlying topological structure (e.g. collecting all the points of a face) in order to compute the new embedding using user-provided functions (e.g. compute the barycenter of several points). To ensure the safety of the defined operations, we provide syntactic conditions on rules that preserve the object consistency constraints.

***Keywords:*** DPO graph transformation, topology-based geometric modeling, graph transformation with variables, labeled graphs, generalized maps, consistency preservation, static analysis, algebraic data types.

# 1. Introduction

In the early 1970s, the concept of graph transformation became of interest in computer science. Derived from string and tree rewriting techniques, this rule-based approach offers a very natural way to describe complex transformations on an intuitive level. For example, anyone observing the transformation given in Figure 1 easily understands the change made in the company organization: the new CEO hires a plant director who is in charge of manufacturing and purchase. Nowadays, thanks to their expressiveness, graph transformations have applications in many areas such as software engineering [1], concurrent and distributed systems [2], visual modeling [3] or database design [4].

Our interest concerns the application of graph transformations to topology-based geometric mod-
eling [5], a field that deals with the representation and manipulation of objects according to their
topological structure (cell subdivision) and their embedding (other types of information attached to their
topological cells). As topological structures can be represented as a particular class of graphs, the use of
graph transformations to define modeling operations have already been proposed in the past [6, 7, 8].

In this article, we propose a generic graph transformation approach that allows the implementation
of modeling operations of any application domain. Indeed, object constructions and transformations
depend on the targeted domain; e.g. add or remove some matter to sculpt (arts), add a window on a
wall (architecture), rotate a gear (engineering), combine partial scans (archaeology), etc. The definition
and implementation of such operations are always time-comsuming and tedious. Every single operation
has to be designed, coded, debugged and optimized. It is even common nowadays that modelers include
a cleaning post-treatment function to fix inconsistencies in transformed objects when operations are too
complex to maintain object consistency along the operation code. As this article will show, this need
<figure><img src="image_4.png" /><figcaption>Figure 1: An example of graph transformation expressiveness</figcaption></figure>

for a reliable and flexible framework to define and implement modeling operations can be efficiently addressed by graph transformations.

Let us take consider two operation examples with the face triangulation of Figure 2(a) and the edge removal of Figure 2(b)) in the case of colored 2D objects. In both figures, the topological structure of the object under transformation contains four faces (two triangles, a square and a pentagon) glued all together, while the embedding associates a color to each face. Note that both operations simultaneously transform the topological structure and the embedding. The face triangulation topologically subdivides the face into triangles, while from the embedding point of view, colors are computed for the new faces as the mix of the subdivided face color and the neighboring face color. The edge removal topologically consists in merging two neighboring faces by removing the shared edge while the embedding modification consists in mixing the two original face colors.

<figure><img src="image_5.png" /><figcaption>Figure 2: Two modeling operations</figcaption></figure>

Using the topological model of generalized maps [9, 10, 5], objects are defined as a particular subclass of labeled graphs in which arc labels encode their topological structure and labeling constraints define their consistency. The implementation of modeling operations with graph transformations requires some dedicated features of graph transformations. In [11, 6, 12], we previously introduced dedicated rule variables to generically handle the topological genericity of modeling operations, i.e. to automatically compute the topological transformation depending on the cell size. For example, such variables allow to define the topological triangulation of any face (triangle, rectangle, pentagon, etc.) by a single rule.

This article addresses the embedding aspect of modeling operations. Considering a representation of embedded generalized maps as labeled graphs introduced in [13] and in which node labels and associated labeling constraints encode object embedding, we will study under which conditions relabeling graph transformations of [14] preserve the embedding consistency of the object under modeling. For example, in the case of the edge removal of Figure 2(b), we will ensure that by construction, after the application of the corresponding rules, all nodes of the resulting face end up labeled with the same color. Based on [15], we will then introduce a rule-based language that allows the new embedding to be generically computed (e.g. to compute the mix of face colors for any colored object). Using dedicated graph transformation variables and terms, the resulting rule schemes will provide the means of both accessing the existing embedding through the topological structure and applying functions provided by the user with embedding data types. For example, the triangulation of Figure 2(a) will be defined by a rule
scheme in which the colors of the created faces are computed by applying the user function “mix of two colors” to the subdivided face color and the respective adjacent face colors. As the safety of this user-oriented language is as essential as its expressiveness, we will provide syntactic conditions to guide rule scheme design and ensure object consistency preservation.

The presented variables and terms are comparable to the attribute variables introduced by B. Hoffman in [15] which allow one to associate new labels to arcs and nodes by applying computations on initial labels associated to arcs and nodes of the graph under transformation. However, aside from their embedding manipulation possibilities, they offer two additional benefits from a graph transformation point of view. First, they take advantage of the regularity of graphs representing nD objects (which can be retrieved in other graph structures) to avoid any additional identifier naming for variables: nodes are directly used as identifiers to access embedding data and are considered as the default variables of a rule (they are called node variables in the sequel). Secondly, the design of geometric modeling operations requires accessing and modifying embedding values of not only nodes occurring in the matched pattern of the rule, but also of nodes located beyond the rule pattern. Let us briefly illustrate this novelty. For the face triangulation of Figure 2(a), we need to access the colors of neighbor faces without matching the face in the rule pattern in order to allow the possibility of a non-existent neighbor (e.g. the yellow triangle has no adjacent face on the right). Similarly, for the edge removal of Figure 2(a), all nodes of the two adjacent faces must have their color changed to the mixed color, while the rule pattern must be limited to the removed edge in order to keep the operation generic in respect to the face sizes (otherwise, the rule would specifically define the removal of an edge between a triangle and a rectangle). We therefore introduce operators dedicated to the traversal of topological structures starting from a given node, and a step-by-step rule scheme instantiation mechanism that carefully propagates modifications of embedding values. To our knowledge, such traversals and modifications of graphs beyond the pattern matched by the rule are original with respect to all existing frameworks of graph transformations with variables, including our own approach for topological transformations [11, 6].

This paper is organized as follows. First, Section 2 presents related works mostly consisting of the existing L-system approaches of geometric modeling (usually referred as procedural modeling), and of some successful graph transformation applications which include the biological study case at the origin of this work. Section 3 then presents the labeled graph transformation fundamentals of our work. In particular, we describe relabeling graph transformations introduced by [14] that will allow us to modify objects. We also present the use of variables in graph transformations as introduced by [15]. The context of topological-based geometric modeling is then presented in Section 4. We focus on the topological model of generalized maps [10] and we give the conditions from [6] under which graph transformations preserve the topological consistency. Section 5 then similarly presents our embedded version of generalized maps and conditions under which basic graph transformations preserve the embedding consistency. The next three sections focus on the rule-based language dedicated to embedding modifications. Section 6 introduces the rule scheme syntax, in particular terms that allow generic computation of new embedding values from existing ones in the object (e.g. to mix two unspecified face colors). Section 7 presents the rule scheme application, especially how schemes are instantiated to propagate minimally defined modifications (e.g. automatically change the color of all nodes of one face). Section 8 provides syntactic conditions on rule schemes to ensure embedding consistency preservation. Section 9 then presents some applications of this work. In particular, after providing few other rule examples, we present both a practical application to physical simulation and the implemented software tool that runs this simulation and any other prototyped modeler. Finally, Section 10 presents some concluding remarks.

## 2. Related works

This section presents the motivations and the origins of our graph transformation-based approach of geometric modeling. First, we present the rule-based approaches of geometric modeling (mostly based on L-systems) that have already proved to be successful in order to model some particular object classes. Secondly, we present similar issues (i.e. issues involving similar structural transformations in a controlled and safe manner) that have already been tackled by graph transformations.
## 2.1. Procedural modeling

Formal rule languages have been used for twenty-five years in the context of geometric modeling, and are usually referred as procedural modeling techniques. These techniques focus on creating a model from a rule set, rather than editing the model via user input. They are particularly useful to model objects that are too cumbersome to be modeled by hand or objects that already exists in the physical world.

<figure><img src="image_6.png" /><figcaption>Figure 3: Fractals in nature</figcaption></figure>

The concept of procedural modeling originates in the fractal notion introduced by Benoit Mandelbrot [16]. Fractals are mathematical sets that exhibit repeating patterns displayed at every scale. They have proved particularly useful as similar regular patterns can be found in the shape of natural objects (e.g. symmetries, trees, spirals, meanders, waves, foams, tessellations, cracks and stripes). For example, the Romanesco broccoli, the nautilus shell and the frost fractals of Figure 3 can all be mathematically modeled by fractals.

<figure><img src="image_7.png" /><figcaption>Figure 4: Plants modeling based on L-Systems</figcaption></figure>

From the observation of similar, but weaker, regularities in most plants, biologist Aristid Lindenmayer introduced L-systems [17] to model plant growth and development. L-Systems basically consist in a set of production rules that have to be successively applied from a given axiom until a stop condition is satisfied. They are therefore suited to represent arborescent structures, such as the flowers in Figure 4(a) [18], or the trees in Figure 4(b) [19]. Moreover, L-systems have already been used in a topological-based context in [20] to model leaf growth as in Figure 4(d), in [21] to model flowers, or in [22] to model internal structure of fruits as in Figure 4(d). Nowadays, L-systems are behind the vegetation of most video games or movies involving CGI, usually created through the SpedTree toolkit<fnref n="1" />.

Applications of L-systems are not limited to plants. In particular, [23] introduced a new type of grammar dedicated to automatically model buildings. In the same way as with plants, building designs are derived using grammars that define building shapes. For example, the three buildings in Figure 5(a) from [24] are generated from the same shape grammar. Moreover, 3D models of existing buildings can also be generated from aerial pictures [25] in order to be displayed in navigation applications. For the

<footnote n="1">¹http://www.speedtree.com/</footnote>
<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>Figure 5: Urban modeling based on L-Systems</figcaption></figure>

same purpose, L-systems have also been extended to automatically model street networks of cities, as represented in Figure 5(b) from [26]. Note that similar grammars are also used as a corrective measure to build navigation maps from construction plans and aerial photographs. Indeed, because of human errors and necessary adaptive measures, the reality on the ground frequently differs from the construction plans.

Let us finally emphasize the reason why we ruled out L-systems to design the language of a generic
geometric modeler. Such a language must cover any potential application domain (computer-aided
design and manufacturing, mechanical engineering, architecture, geology, archaeology, medical image
processing, scientific visualization, movies, video games, ...), and therefore it must address a large
class of modeling operations. In all the presented applications, L-systems and graph grammars are
defined by a limited set of high-level operations such as creating a new branch, inserting a floor or
subdividing a district with a road. These high-level rules do not contain all the low-level transformations
on actual object representations and therefore each of them has its own dedicated implementation and
consistency preservation mechanism. This lack of adaptability and robustness entails that every added
rule requires additional implementation and debugging efforts, which is particularly undesirable for a
generic modeler. L-systems are therefore a good solution for specific modeling issues but not for generic
modeling purposes.

2.2. *Graph transformation applications*

As Section 3 will present the graph transformation theory, the following subsection outlines the
advantages of this approach without going into every detail. First, conversely to L-systems, graph
transformations operate at low-level on graph structures and therefore rules are self-contained. For a
given graph transformation class, it is therefore possible to apply all rules with a single rule application
engine. This point is crucial in the design of a generic modeling tool as it minimizes the implementation
and debugging efforts. Moreover, such a low-level definition ensures that given some required graph
properties (e.g. for geometric consistency), it is therefore possible to express conditions on rules that
will consistently maintain those properties along graph transformations. Finally, graph transformations
also allow the use of high-level variables based on this strong low-level theoretical ground, therefore
offering as much expressive power as L-systems.

Among applications that already take advantage of graph transformations, the best known is surely
software engineering as graph transformations provide the tools to tackle the variety of problems inherent
to software design. Graph transformations already address program refactoring, syntax and semantics of
visual languages, visual modeling of behavior and programming, software specifications and evolution,
security policies, etc. [2, 1, 27]. The variety of problems is also reflected in the multiplication of dedicated
tools (e.g. EMorF, Fujaba, Gremlin, Henshin, eMoflon, DiaGen) in addition to the established generic
graph transformation tools (e.g. GrGen.NET, GP, Groove, AGG, GMTE).

But graph transformations also have numerous applications aside from software engineering. In the
field of computer graphics, graph transformations have been used for shape recognition purposes. In
particular, in [28, 29], attributed grammars were defined to describe and classify the syntactic structures
of two-dimensional shapes. However, although it proved to be functional, the final system that was
using a combination of syntactic and statistical pattern recognition techniques was abandoned for purely
statistical approaches that were shown to be more efficient.

<figure><img src="image_10.png" /><figcaption>(a) Role of the Golgi Apparatus</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b) The “plates” hypothesis</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(c) The “tower” hypothesis</figcaption></figure>

<caption>Figure 6: Our first study case: the Golgi apparatus</caption>

As L-systems, graph transformations also have applications in biology. But as they operate at a lower
level on graph structures, their applications concern more specifically molecular biology [30, 31, 32], i.e.
the synthesis and interactions of DNA, RNA, and proteins. Among them, we investigated in [11] the
processing of proteins by the Golgi apparatus. In particular, as this process involves the packaging of
proteins into membrane-bound vesicles, the use of graph transformations is particularly useful to model
the involved topological evolutions illustrated in Figure 6(a). Transition vesicles carrying proteins are
absorbed by the Golgi apparatus and secretion vesicles are created while proteins have been processed
and packaged. To implement and run simulations on the different hypotheses proposed by biologists for
the Golgi’s operation (e.g. the “plates” and the “tower” hypothesis simulations illustrated in Figure 6(b)
and 6(c)), we proposed in [6] graph transformation variables dedicated to topological transformations,
along with syntactic conditions on rules that ensure the topological consistency of transformed objects.
These variables allowed us to generically abstract topological cells (vertices, edges, faces, volumes) and
their transformations.

To extend the use of these variables, we showed that they offer a safer and easier design of topological
operations to design a topological-based geometric modeler [33], rather that the use of traditional ad-hoc
implementations that are fastidious to code and vulnerable to consistency bugs. But the topological
transformations are not the only issues at stake to design topological-based geometric modeler. Concrete
applications deal with several data types attached to the topological structure and called embeddings.
Embeddings usually include standart geometric data describing the shape of the objects (e.g. points,
curves, surfaces) and specific data that depend on the targeted application (e.g. molecule concentration
for biology, rock density for geology, material for architecture). For example, the Golgi simulations of
Figure 6 involved several embeddings whose transformations had to be carefully hard-coded: vertex 3D
positions to define the evolving model shape, protein quantities carried by the different volumes, and
membrane porosity associated to the faces between volumes.

Therefore, the proposed graph transformation-based language must also address these multiple
embeddings. In [13], we defined a new graph category that allow nodes to have multiple labels in order
to simultaneously represent the multiple embedding types (e.g. a face being labelled by both its color
and its porosity) and proved the existence of graph transformations in this category. We also introduced
a new type of dedicated variables and operators to express embedding transformations in rules. In this article, we present the final version of these variables as they are implemented in the tool set Jerboa [34] that allows a geometric modeler kernel to be generated from a set of rules and that will be presented in Section 9. As for topological variables, we also introduce syntactic conditions on rules that ensure the embedding consistency of transformed objects.

### 3. Graph transformations

Graphs are non-linear structures, defined by a set of objects, usually called vertices or nodes, and a set of links between these objects, usually called edges or arcs. To avoid confusion with the specific vocabulary of geometric modeling, we will subsequently prefer to use the word “node” rather than the word “vertex”, and the word “arc” rather than “edge” when refering to graph elements. Graphs are often depicted in a diagrammatic form with dots or circles to represent nodes and lines or curves to represent arcs between nodes, directed or undirected. Graph transformations commonly refer to rule-based languages designed to manipulate graphs. Among all graph transformation approaches, we choose the so-called double-pushout approach (or DPO) [35, 36, 27] for several reasons: our previous works took place in the DPO framework; to our knowledge, [15] is the only framework dedicated to the generic manipulation of variables in graph transformations, which is expressed in the DPO framework; most importantly, we want to take advantage of the well-founded DPO framework given in [14] which allows the relabeling of nodes and arcs in graph transformations.

#### 3.1. Double-pushout graph transformation

In the DPO approach, a transformation is expressed using two gluing diagrams defined in terms of category theory. More precisely, these diagrams are pushouts in the category of graphs and graph morphisms. In order to make the presentation more intuitive, let us consider the simple example of a DPO graph transformation given in Figure 7. The rule is given at the top of Figure 7 by the three graphs $L, K$ and $R$ and by the two graph inclusions$^2$ $L \leftrightarrow K \leftrightarrow R$. In this example, nodes of graphs are identified by letters ($a, b$ or $c$) and are labeled by numbers (1, 3 or 5 while arcs are anonymous and labeled by numbers (2 or 4). Intuitively, the left-hand side of the rule $L$ is the pattern to transform, the right-hand side $R$ is the transformed pattern, and the interface $K$ is the preserved part common to both $L$ and $R$. The graph morphism $L \to G$ allows the matched pattern (graph $L$) to be identified inside the graph under transformation (graph $G$) (in Figure 7, the match morphism coincides with the inclusion).

<figure><img src="image_13.png" /><figcaption>Figure 7: DPO graph transformation</figcaption></figure>

In the first pushout (1), all elements (nodes and arcs) in $L$ that are not in $K$ are removed in $D$. In the example, the two arcs that loop on nodes $a$ and $b$ are removed: graph $D$ results from the removing of loops on both nodes $a$ and $b$ in graph $G$. In the second pushout (2), all elements of $R$ that are not already in $K$ are added while all elements in $K$ are preserved. In the example, an arc is added between

<footnote>$^2$One can generally consider standard graph morphisms instead of only considering inclusions.</footnote>
the two preserved nodes *a* and *b* (graph *H*). When the match *L* → *G* meets some conditions, then the transformation is well defined, and the double-pushout construction defines a unique graph *H* (up to graph isomorphism), that is the result of the application of the graph transformation *L* ↔ *K* ↔ *R* through the match morphism *L* → *G*.

<figure><img src="image_14.png" /><figcaption>Figure 8: A relabeling rule</figcaption></figure>

In classical DPO transformations, graph morphisms have to preserve both arc and nodes labels, and therefore prevent relabeling. Note that the relabeling of an arc can still be achieved by removing it while adding an arc with the new label between the same source and target nodes, but this not the case for the relabeling of a node. Consequently, we prefer the DPO approach of [14] that considers partially labeled graphs and therefore allows relabeling. Let us take the example of the relabeling rule of Figure 8. In the left-hand side *L*, node *b* is initially labeled by 7 while it is relabeled by 3 in the right-hand side *R*, and therefore unlabeled in the interface *K*. Note that the two morphisms *K* ↪*L* and *K* ↪*R* on partially labeled graphs *L*, *K*, *R* do not preserve labeling, in particular the undefined label of *b*.

We now present the main definitions and results of [14] on partially labeled graph transformations.

## 3.2. Graph transformations on partially labeled graphs

A partially labeled graph $G = (V_G, E_G, s_G, t_G, l_{G,V}, l_{G,E})$ consists of two finite sets $V_G$ and $E_G$ of nodes and arcs, two source and target functions $s_G, t_G : E_G \to V_G$, and two partial labeling functions$^3$ $l_{G,V} : V_G \to C_V$ and $l_{G,E} : E_G \to C_E$, where $C_V$ and $C_E$ are fixed sets of node and arc labels. We say that $G$ is totally labeled if $l_{G,V}$ and $l_{G,E}$ are total functions. A path in a graph $G$ is a sequence $e_1...e_k$ of arcs of $G$ with $1 \le k$, such $t_G(e_i) = s_G(e_{i+1})$ for each $1 \le i < k$. $s_G(e_1)$ and $t_G(e_k)$ are respectively called the *path source* and the *path target* and the word $l_{G,E}(e_1)...l_{G,E}(e_k)$ is called the *path label*. Moreover, if $s_G(e_1) = t_G(e_k)$, the path is called a *cycle*. From now on, partially labeled graphs are simply called *graphs*. Let us point out that in the following, all graphs $G$ of the form $(V_G, E_G, s_G, t_G, l_{G,V}, l_{G,E})$ will be symmetric, that is, for all edge $e$ in $E_G$, there will be an edge $e'$ in $E_G$, such that $s_G(e') = t_G(e)$, $t_G(e') = s_G(e)$ and $l_{G,E}(e')$ is defined if and only if $l_{G,E}(e)$ is defined, and in this case, $l_{G,E}(e') = l_{G,E}(e)$. So, instead of considering a framework built over directed graphs, we could have considered only undirected graphs. We finally prefer to manipulate directed graphs and to require them to be symmetric, both to directly benefit from the results of [14] expressed for directed graphs and to anticipate the adaptation of our work for topological models other than generalized maps.

A graph morphism $g : G \to H$ between two graphs $G$ and $H$ consists of two functions $g_V : V_G \to V_H$ and $g_E : E_G \to E_H$ that preserve sources, targets and labels, that is, $s_H \circ g_E = g_V \circ s_G$, $t_H \circ g_E = g_V \circ t_G$, and $l_H(g(x)) = l_G(x)$ for all$^4$ $x$ in $Dom(l_G)$. A morphism $g$ is *injective* (resp. *surjective*) if $g_V$ and $g_E$ are injective (resp. surjective), and is an *isomorphism* if it is injective, surjective and preserves undefinedness$^5$. In the latter case, $G$ and $H$ are *isomorphic*. Furthermore, we call $g$ an *inclusion* if $g(x) = x$ for all $x$ in $G$. An inclusion is denoted by the symbol ↪ (or the symbol ↔ if the target graph is introduced first). Finally, morphism composition is defined componentwise as function compositions.

**Definition 1 (Rule).** A rule $r : L \leftrightarrow K \leftrightarrow R$ consists of two inclusions $K \hookrightarrow L$ and $K \hookrightarrow R$ such that:

(1) for all $x \in L$, $l_L(x) = \perp$ implies $x \in K$ and $l_R(x) = \perp$,

(2) for all $x \in R$, $l_R(x) = \perp$ implies $x \in K$ and $l_L(x) = \perp$.

<figure><img src="image_15.png" /></figure>

<footnote>$^3$Given two sets $A$ and $B$, a partial function $f : A \to B$ is a function from subset $A'$ of $A$ to $B$. The set $A'$ is the domain of $f$ and is denoted by $Dom(f)$. We say that $f(x)$ is undefined, and write $f(x) = \perp$, if $x$ is in $A - Dom(f)$.</footnote>

<footnote>$^4$To simplify, we amalgamate nodes and arcs in statements that hold for both sets, by omitting the indices $E$ and $V$.</footnote>

<footnote>$^5$i.e. if $l_H(g(x)) = \perp$ for all $x$ in $G \setminus Dom(l_G)$.</footnote>
Regarding [14], our rules are simplified since they are built with two inclusions for both sides instead of only one for the left-hand side. We call *L* the *left-hand side*, *R* the *right-hand side* and *K* the *interface* of *r*. Note that conditions (1) and (2) are trivially satisfied when *L* and *R* are totally labeled.

Since objects will be represented by totally labeled graphs, a first idea would be to only consider totally labeled graphs in order to simplify definitions: unlabeled elements could be then handle with a dedicated label denoting its own irrelevance. However, this trick would later be inadequate to instantiate rule schemes in Section 7 as this process requires dedicated propagation mechanisms on partially labeled graphs in order to build consistently labeled graphs.

A diagram of graph morphisms, as Figure 9(a), is a *pushout* if (i) $K \to R \to H = K \to D \to H$ and (ii) for every pair of graph morphisms $(R \to H', D \to H')$ with $K \to R \to H' = K \to D \to H'$, there is a unique morphism $H \to H'$ such that $R \to H' = R \to H \to H'$ and $D \to H' = D \to H \to H'$. The same diagram is a *pullback* if property (i) holds and (iii) if for every pair of graph morphisms $(K' \to R, K' \to D)$ with $K' \to R \to H = K' \to D \to H$, there is a unique morphism $K' \to K$ such that $K' \to R = K' \to K \to R$ and $K' \to D = K' \to K \to D$. A pushout is *natural* if it is also a pullback.

<figure><img src="image_16.png" /><figcaption>Figure 9: A diagram and a direct derivation</figcaption></figure>

**Definition 2 (Direct derivation).** A direct derivation from a graph *G* to a graph *H* via a rule *r*: *L* ↔ *K* ↔ *R* consists of two natural pushouts as Figure 9(b), where *m*: *L* → *G*, called the match morphism, is injective. We write *G* ⇒<sub>*r*,m*</sub> *H* if there exists such a direct derivation. ◀

In [14], authors studied under which conditions usual constructions in the category of totally labeled graphs such as pushouts, pullbacks or direct derivations can be transferred into the category of partially labeled graphs. In particular, properties concerning direct derivations are similar to those on totally labeled graphs. A match morphism $m: L \to G$ satisfies the *dangling condition* with respect to the inclusion $L \leftarrow K$, if no node in $m(L) \setminus m(K)$ is incident to an arc in $G \setminus m(L)$. Given a rule $r: L \leftrightarrow K \leftrightarrow R$ and a match morphism $m: L \to G$, there exists a direct derivation as in Figure 9(b) if and only if $m$ satisfies the dangling condition. Moreover, in this case, $D$ and $H$ are unique up to isomorphism, and $H$ is totally labeled if and only if $G$ is totally labeled.

### 3.3. Graph transformation with variables

To meet the various application needs, graph transformations have been enriched with variables to make them generic. Intuitively, rules with variables describe as many concrete rules as there are possibilities to instantiate variables with concrete elements. Different types of variables have been introduced to enrich graph transformations. For example, attribute variables allow label computations [37] or labeling constraints [38, 39], while graph variables [40, 41] and hyperedge variables [42, 43] allow structural transformations (i.e. modifications of whole graphs connected to some attachment nodes designated by the rule pattern).

We will not use these variables in this article, but we will use the framework for graph transformation with variables introduced in [15] as it provides general guidelines to deal with any variable type in graph transformations. We briefly describe its main elements: the rule scheme syntax, the instantiation of variables, and the whole rule application process.
**Rule scheme.** The sets $C_V$ and $C_E$ of node and arc labels are extended by a set $X$ of variable names. Graphs built over$^6$ are called graph schemes. Then a rule scheme is a rule $r: L \leftrightarrow K \leftrightarrow R$ where $L, K$, and $R$ are graph schemes. The kernel $\underline{G}$ of $G$ is the graph obtained by removing all labels that contain a variable occurrence.

**Instantiation.** A substitution function $\sigma$ specifies how variable names occurring in a rule scheme are substituted. From the *instantiation* of variables in the graphs $L, K, R$, yielding to the graphs denoted respectively as $L_\sigma, K_\sigma$ and $R_\sigma$, the *instantiation* of a rule scheme $r: L \leftrightarrow K \leftrightarrow R$ according to $\sigma$ defines a particular *rule instance* $r_\sigma: L_\sigma \leftrightarrow K_\sigma \leftrightarrow R_\sigma$. Note that $r_\sigma$ is a rule without variables as defined in Definition 1.

**Rule application.** Let $G$ be a graph, and $r: L \leftrightarrow K \leftrightarrow R$ be a rule scheme.

1. Identify a *kernel match* $m: L \to G$ of the kernel $L$ of $L$ in $G$ (if it exists);

2. If possible, find a substitution $\sigma$ such that there exists a morphism $m: L_\sigma \to G$ extending $m$;

3. Construct the instance $r_\sigma: L_\sigma \leftrightarrow K_\sigma \leftrightarrow R_\sigma$ and apply $r_\sigma$ to get the direct derivation $G \Rightarrow_{r_\sigma, m} H$.

In [15], this framework is used for three types of variables with specific purposes: attribute variables, clone variables and graph variables. Depending on the variable type, the substitution, and therefore the instantiation, differ, but the generic framework remains valid. By following it, we already introduced in [6, 33] another type of variables that allow generic transformations of topological structures and which proved the relevance of [15] for introducing new types of graph transformation variables.

<figure><img src="image_17.png" /><figcaption>Figure 10: A rule scheme with attribute variables</figcaption></figure>

For the embedding aspect of geometric operations, we first thought that the *attribute variables* of [15] were expressive enough. Their usage is illustrated by the rule scheme of Figure 10. For the matched arc, the new label of the target node becomes the sum of the initial label of the source node and of the initial label of the arc. Intuitively, the application of this rule scheme to a graph allows one to deduce a substitution of attributed variables occurring on the left-hand side $L$, and to compute the new labels by evaluation of the expressions of the right-hand side $R$. Note that the substitution $\sigma = \{x \mapsto 1, y \mapsto 2, z \mapsto 7\}$ would allow to derive the previous rule of Figure 8, according that $+$ is evaluated as the usual addition operation.

But attribute variables do not exactly fit our usage as we need to access the node labels through the node names to allow topological structure traversal (e.g. to access the adjacent face color in the case of the colored triangulation given in the introduction). In the sequel, we will introduce dedicated variables, but, roughly speaking, they will come down to attribute variable indirections in the most basic cases. Note also that by convention, rule schemes will be identified by dotted double lines circling their $L, K$ and $R$ graphs (see Figure 10) while single dotted lines are used for rule instance graphs (see Figure 8).

### 3.4. Data types

In our setting, objects will be modeled by labeled graphs whose nodes are labeled by geometric or dedicated data (thereafter referred to as *embedding*) such as the color of a face or the 2D position of a point. These data are clearly typed and provided with functions to perform computations on them.

In addition, as a same embedding value can appear multiple times in an object (e.g. in the transformed object of Figure 2, two faces have the same color), we need to identify these multiple occurrences when

<footnote>$^6$Labels of nodes or arcs are either variables of $X$ or expressions built over variables of $X$.</footnote>
collecting object embedding values. We therefore consider for each type $\tau$, the type $\tau^\bullet$, multiset of elements of type $\tau$. A multiset may be viewed as a function that associates its multiplicity (a natural number) to each element. We use the following notation: $\llbracket \dots \rrbracket$ for the empty multiset (of any type $\tau^\bullet$), $\llbracket a_1, \dots, a_p \rrbracket$ for a multiset with $p$ occurrences of elements of type $\tau$. For example, the multiset that contains the element $A$ with the multiplicity 1, the element $B$ with the multiplicity 2, and where all other elements are of multiplicity 0, is denoted $\llbracket A, B, B \rrbracket$. Similarly, the multiset of face colors of the transformed object of Figure 2 is denoted $\textcolor{yellow}{\bullet, \bullet, \bullet, \bullet}$.

We then present the main elements of term construction and evaluation.

**Signature.** A data type signature $\Omega = (S, F)$ consists of a set $S$ of type names and a family of function names provided with a profile on $S \cup S^\bullet$ where $S^\bullet = \{s^\bullet | s \in S\}$ is the set of multisets over types in $S$. A function name $f$ provided with a profile $s_1 \dots s_{m+1}$ with $s_i \in S \cup S^\bullet$ for $i \in 1..m+1$ is denoted $f: s_1 \times \dots \times s_m \to s_{m+1}$.

**Terms.** For an $S$-indexed family $X = \coprod_{s \in S} X_s$ of variables, the set $T_\Omega(X) = \coprod_{s \in S \cup S^\bullet} T_\Omega(X)_s$ of terms over $\Omega$ is the least set satisfying:

* for all variables $x$ in $X_s$, $x \in T_\Omega(X)_s$;

* for all function names $f: s_1 \times \dots \times s_m \to s_{m+1}$ in $F$, for all terms $t_1 \in T_\Omega(X)_{s_1}, \dots, t_m \in T_\Omega(X)_{s_m}$, then $f(t_1, \dots, t_m) \in T_\Omega(X)_{s_{m+1}}$.

We note $t: s$ a term $t$ in $T_\Omega(X)_s$.

**Algebra.** An $\Omega$-algebra $\mathcal{A}$ consists of an $S$-indexed family of nonempty sets $\coprod_{s \in S} A_s$ and for each $f: s_1 \times \dots \times s_m \to s_{m+1}$ in $F$, of a function $f^A: A_{s_1} \times \dots \times A_{s_m} \to A_{s_{m+1}}$ where for $s_i \in S^\bullet$, that is $s_i = s^\bullet$ for some $s$ in $S$, $A_{s_i} = \{\llbracket a_1, \dots, a_p \rrbracket | 0 \le p, \forall k \in 0..p, a_k \in A_s\}$.

**Evaluation.** For $\sigma = \coprod_{s \in S} \sigma_s$ an $S$-indexed family of assignments $\sigma_s: X_s \to A_s$, the evaluation $\sigma: T_\Omega(X)_s \to A_s$ of a term $t: s$ is defined as:

* for all variables $x$ in $X_s$, $\sigma(x) = \sigma_s(x)$;

* for all function names $f: s_1 \times \dots \times s_m \to s_{m+1}$ in $F$ and all terms $t_1 : s_1, \dots, t_m : s_m$, $\sigma(f(t_1, \dots, t_m)) = f^A(\sigma(t_1), \dots, \sigma(t_m))$.

In order to design a modeling operation, the user is expected to provide both a data type signature $\Omega = (S, F)$ and an $\Omega$-algebra $\mathcal{A}$, with all the data types and functions required by its application domain to define its modeling operations. In the sequel, the considered user types are *point-2D*, *vector-2D* and *color*, that respectively model 2D positions, 2D vectors and face colors. They are provided with all classical functions such as $+$: *point-2D* $\times$ *vector-2D* $\to$ *point-2D* that represents the translation of a point by a vector, *center*: *point-2D* $\times$ *point-2D* $\to$ *point-2D* that computes the center of two points, *bary*: *point-2D* $^\bullet$ $\to$ *point-2D* that computes the barycenter of a multiset of points, or *mix*: *color* $\times$ *color* $\to$ *color* that defines the average color of two given colors. The algebra $\mathcal{A}$ will be left implicit. When needed, the carrier set $\mathcal{A}_\tau$ of a data type $\tau$ will be simply denoted $\lfloor \tau \rfloor$.

Note that multisets could also have been introduced by considering a higher order approach as a starting point, i.e. by introducing type constructions such as sets, lists or tuples of elements of the same type. But the resulting data types would have been richer than necessary, since we would have at our disposal types such as sets of sets of elements, and we only need a generic type for denoting multisets of basic type elements. Our presentation of data types minimally meets this need by semantically imposing all multiset properties such as commutativity of the element insertion, specification of the element multiplicity, etc., but also offers a simple and concise notation for multisets.

# 4. Topological generalized maps as partially labeled graphs

In topology-based modeling, objects are defined according to:
<figure><img src="image_18.png" /><figcaption>Figure 11: Object inconsistencies</figcaption></figure>

• their topological structure - i.e. their cell subdivision (vertices, edges, faces, volumes) and the adjacency relations between these cells; for example, the three objects of Figure 11(a) have the same topological structure: a closed face F that has four edges and four vertices;

• their embedding, which includes all other types of information attached to their topological cells, including the geometric information required to capture their shape; for the objects of Figure 11(a), geometric points are attached to topological vertices and colors are attached to faces.

There are many topological structures that allow one to represent different classes of objects: tetrahedral [44] or polyhedral [45, 46, 5], fixed dimension (2D [45] or 3D [46]) or dimension-independent [44, 5], and most of them can be seen as a particular class of graphs. Among those, we choose the topological model of generalized maps (or G-maps) [9, 10, 5] because its mathematical definition can be rather easily encoded within a formal framework. In G-maps, the topological structure is handled by both the graph structure and the arc labels, while the embedding is defined by the node labels.

More precisely, the class of G-maps that represents valid objects is defined by labeling constraints. Hence, to define modeling operations with graph transformations, we investigate under which conditions G-map constraints, and so object consistency, are preserved along transformations. Examples of inconsistencies are given in Figure 11: an edge with a single extremity instead of two, or two faces glued along a vertex instead of an edge are topological inconsistencies, while a face embedded with two colors instead of one, or without any defined color are embedding inconsistencies.

## 4.1. Generalized maps

<figure><img src="image_19.png" /><figcaption>Figure 12: Topological decomposition of a geometric 2D object</figcaption></figure>

The representation of an object as a G-map intuitively comes from its decomposition into topological cells (vertices, edges, faces, volumes, etc.). For example, the 2D topological object of Figure 12(a) can be decomposed into a 2-dimensional G-map. The object is first decomposed into faces in Figure 12(b). These faces are *linked* along their common edge with a 2-relation: the index 2 indicates that two cells of dimension 2 (faces) share an edge. In the same way, faces are split into edges connected with the 1-relation in Figure 12(c). At last, edges are split into vertices by the 0-relation to obtain the 2-G-map of
Figure 12(d). Nodes obtained at the end of the process are the G-map ones and the different *i*-relations become labeled arcs: for a 2-dimensional G-map, *i* belongs to {0, 1, 2}.

Therefore, G-maps are particular graphs whose arcs are labeled by integers: for a dimension *n*,
*n*-G-maps are partially labeled graphs such that arcs are totally labeled in $C_E = [0, n]$ where $[0, n]$ is
the interval of integers between 0 and *n*. G-maps are undirected<sup>7</sup>: thus, for each *i*-arc of source *v*, of
target *v'*, there is also a corresponding reversed *i*-arc of source *v'* and target *v*. As usual, double reversed
arcs are graphically represented by undirected arcs (see Figure 12(d)). Note that in order to be more
readable, in all figures given subsequently, we use the graphical codes introduced in Figure 12 (black line
for 0-arcs, red dashed line for 1-arcs and blue double line for 2-arcs) instead of writing a label near the
corresponding arc. So, the way undirected arcs will be drawn will implicitly indicate their label values.

<figure><img src="image_20.png" /><figcaption>Figure 13: Orbits adjacent to e</figcaption></figure>

Topological cells are not explicitly represented in G-maps but implicitly defined as subgraphs. They
can be computed using graph traversals defined by an originating node and a given set of arc labels. For
example, in Figure 13(a), the 0-cell (vertex) adjacent to *e* is the subgraph which contains *e*, the nodes
that can be reached from node *e* using 1-arcs or 2-arcs (nodes *c*, *e*, *g* and *i*) and the arcs themselves.
This subgraph is denoted by $G\langle 1\ 2\rangle(e)$, or simply $\langle 1\ 2\rangle(e)$ if the context (graph *G*) is obvious, and
models the vertex *B* of Figure 12(a). In Figure 13(b), the 1-cell adjacent to *e* (edge *w*) is the subgraph
$G\langle 0\ 2\rangle(e)$ that contains node *e* and nodes reachable through 0-arcs and 2-arcs (nodes *e*, *f*, *g* and *h*),
and the corresponding arcs. Finally, in Figure 13(c), the 2-cell adjacent to *e* (face $\mathcal{F}$) is the subgraph
denoted by $\langle 0\ 1\rangle(e)$ and built from node *e* with 1-arcs and 2-arcs.

In fact, topological cells (face, edge or vertex) are particular cases of *orbits* denoting subgraphs built
from an originating node and a set of labels. The different *orbit types* of an *n*-G-map are all possible
subsets of `[0, n]` and are classically denoted by an ordered word *o* of edge labels placed in brackets *⟨o⟩*.
In addition to the already mentioned orbit types (*⟨0 1⟩* for face, *⟨0 2⟩* for edge, *⟨1 2⟩* for vertex), let
us give some other examples of orbit types: the orbit *⟨0⟩*(*e*) in Figure 13(d) represents the half-edge
adjacent to *e*, and the orbit *⟨0 1 2⟩*(*e*) in Figure 13(e) represents the whole connected component. We
say that a label *i* belongs to an orbit *⟨o⟩* if *i* occurs in the word *o*.

The following definition introduces the notions of topological graphs (which include G-maps but also
their transformation patterns), orbits, orbit equivalences, and orbit completions. In particular, these
last two notions will be useful later in the article to handle embedding transformations. Note also that
according to the notation commonly used in geometric modeling, the arc labeling function of topological
graph is denoted by $\alpha$.

<footnote n="7"><sup>7</sup>Undirected graphs, also called symmetric graphs, are such that for each arc of source *n* and of target *n'*, there exists a symmetric arc, of source *n'* and of target *n*.</footnote>
**Definition 3 (n-topological graph and orbit).** A partially labeled graph $G = (V, E, s, t, l_V, \alpha)$ is an $n$-dimensional topological graph if the arc labeling function $\alpha$ is a total function with codomain $C_E = [0, n]$.

For $\langle o \rangle$ an orbit type of dimension $n$, let $\equiv_{G\langle o \rangle}$ be the equivalence orbit relation defined on $V \times V$ as the reflexive, symmetric and transitive closure built from arcs with labels in $o$, i.e., ensuring that for each arc $e$ of $G$ labeled by a letter in $o$, we have $s(e) \equiv_{G\langle o \rangle} t(e)$.

For any node $v$ of $G$, the $\langle o \rangle$-orbit of $G = (V, E, s, t, l_V, \alpha)$ adjacent to $v$, denoted by $G\langle o \rangle(v)$, is defined as the least subgraph $(V', E', s', t', l_V', \alpha')$ of $G$ whose set $V'$ of nodes includes $\{v\} \cup \{v' \mid v' \in E, \exists w \in V', v' \equiv_{G\langle o \rangle} w\}$, whose set $E'$ of arcs includes $\{e \mid s(e) \in V', t(e) \in V', \alpha(e) \in o\}$ and whose $s', t', l_V'$ and $\alpha'$ are restrictions of corresponding functions in $G$ to the sets $V'$ or $E'$. If the context is clear, $G\langle o \rangle(v)$ is simply denoted $\langle o \rangle(v)$.

<figure><img src="image_21.png" /></figure>

More generally, for any subgraph $G' \to G$, the $\langle o \rangle$-completion of $G'$ in $G$, denoted by $G\langle o \rangle(G')$, is defined as the least subgraph $(V'', E'', s'', t'', l_V'', \alpha'')$ of $G$ whose set $V''$ of nodes includes $V_{G'} \cup \{v'' \mid v'' \in E, \exists w \in V'', v'' \equiv_{G\langle o \rangle} w\}$, whose set $E''$ of arcs includes $\{e \mid s(e) \in V'', t(e) \in V'', \alpha(e) \in o\}$ and whose $s', t', l_V'$ and $\alpha'$ are restrictions of corresponding functions in $G$ to the sets $V''$ or $E''$.

<figure><img src="image_22.png" /><figcaption>(a) Vertex completion of the edge of $e$</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(b) Edge completion of the vertex of $e$</figcaption></figure>

<caption>Figure 14: Completions</caption>

Let us take two examples to illustrate the notion of completion. The topological graph of Figure 14(a) is the $\langle 1 \rangle$-completion of $\langle 0 \rangle$-completion of $\langle 2 \rangle$-completion of $\langle 0 \rangle$-symmetrically, the Figure 14(b) presents the $\langle 0 \rangle$-completion of the vertex $\langle 1 \rangle$-completion of $\langle 2 \rangle$-completion of $\langle 0 \rangle$-symmetrically.

Let us now give the consistency constraints that objects defined as G-maps must satisfy.

**Definition 4 (Generalized map).** An $n$-dimensional generalized map, or $n$-G-map, is a partially labeled $n$-topological graph $G = (V, E, s, t, l_V, \alpha)$ that satisfies the following topological consistency constraints:

* Symmetry constraint: $G$ is *undirected*,

* Adjacent arc constraint: each node is the source node of exactly $n+1$ arcs respectively labeled from 0 to $n$,

* Cycle constraint: for every $i$ and $j$ such that $0 \le i \le i+2 \le j \le n$, there exists a cycle labeled by $ijij$ starting from each node.

<figure><img src="image_24.png" /></figure>

These constraints ensure that objects represented by embedded G-maps are consistent manifolds [10]. In particular, the cycle constraint ensures that in G-maps, two $i$-cells can only be adjacent along $(i-1)$-cells. For instance, in the 2-G-map of Figure 12(d), the 0202-cycle constraint implies that faces are stuck along topological edges. Let us notice that thanks to loops (see 2-loops in Figure 12(d)), these three constraints also hold at the border of objects.
## 4.2. Basic topological transformations

Within a geometric modeler, operations defined on objects are called topological (respectively geometric) if their main purpose is to change the topological structure (respectively the embedding). Obviously, some operations fall under both aspects, as the rounding operation that consists in the replacement of a vertex or a sharp edge by a curved surface [47].

Roughly speaking, topological operations are applications that allow one to build new generalized maps from generalized maps. The definition of topological operations by graph transformation rules advantageously facilitates the study of stating whether or not the resulting graphs are also generalized maps. To achieve this, rules on generalized maps have to preserve by construction the topological constraints of Definition 4.

In previous works [11, 6, 12], we elaborated the following syntactic conditions that precisely ensure the preservation of topological consistency:

**Theorem 1 (Topological consistency preservation).** Let $r: L \leftrightarrow K \leftrightarrow R$ be a graph transformation rule, $G$ an $n$-G-map and $m: L \to G$ a match morphism.

The direct transformation $G \Rightarrow^{r,m} H$ produces an $n$-G-map $H$ if the following conditions of topological consistency preservation are satisfied:

* Symmetry condition: the three graphs $L, K$ and $R$ are undirected $n$-topological graphs.

* Adjacent arcs condition:

- preserved nodes of $K$ are sources of arcs having the same labels in both the left-hand side $L$ and the right-hand side $R$;

- removed nodes of $L \setminus K$ and added nodes of $R \setminus K$ must be source of exactly $n+1$ arcs respectively labeled from 0 to $n$.

* Cycle condition: for all $(i, j)$ such $0 \le i \le j + 2 \le j \le n$,

- any added node of $R \setminus K$ is the source of an *ijij-cycle*;

- any preserved node of $K$ which is the source of an *ijij-cycle* in $L$, is also the source of an *ijij-cycle* in $R$;

- any preserved node of $K$ which is not the source of an *ijij-cycle* in $L$ is source of the same *i-arcs* and *j-arcs* in $L$ and $R$. ◀

The interested reader can find the proof of this theorem in [6]. In particular, we demonstrated that the dangling condition (see Subsection 3.2) is always ensured when a rule that satisfies those conditions is applied to a G-map.

Theorem 1 only expresses sufficient conditions to produce $G$-maps starting from $G$-maps, and not necessary conditions. It is intended to be like this: first of all, in line with the way experts in geometric modeling manipulate models, we restrict ourselves to undirected graphs and thus, we require that all graphs are undirected, without this condition being necessary. Indeed, clearly, we could write rules with graphs which are not symmetric. Thus, conditions provided by Theorem 1 have the interest of corresponding to the intuitions of experts in geometric modeling: this is particularly the case for the last two conditions: for example, the adjacent arcs condition simply requires that after transformation, all nodes should have exactly $n+1$ arcs labeled from 0 to $n$, which is exactly part of the definition of $G$-maps. It is the same for the third condition of Theorem 1, with respect to the cycle constraint. Up to our knowledge, these conditions make it possible to write a sufficiently large class of representative modeling operations.

Intuitively, the adjacent arcs condition (combined with the symmetry condition) ensures that every node concerned by the rule application ends up being the source and the target of exactly one *i-arc*
<figure><img src="image_25.png" /><figcaption>Figure 15: Non-respect of adjacent arcs condition</figcaption></figure>

for each $i \in [0, n]$ in the transformed object. The first point requires that preserved nodes have their adjacent *i*-arcs in both sides of the rule. Indeed, by construction, *i*-arcs that are not matched by the rule are preserved in the transformed graph. For example, the rule of Figure 15(a) adds a 0-arc between nodes *e* and *h* in *R* without matching any 0-arc in *L*. Consequently, in the resulting graph *H*, nodes *e* and *h* have both their original 0-arc issued from *G* and the 0-arc added in *R*, and therefore *H* is not a G-map. The second point requires that added or removed nodes have exactly one *i*-arc for each $i \in [0, n]$. Indeed, nodes can only be consistently added with all their adjacent arcs. Similarly, removing a node without matching a given *i*-arc would imply that an *i*-arc remains in the transformed G-map with the source node or the target node missing. For example, the rule of Figure 15(b) removes node *f* without matching its adjacent 1-arc and 2-arc. Consequently, the resulting graph *H* contains two dangling arcs.

<figure><img src="image_26.png" /><figcaption>Figure 16: Non-respect of cycle condition</figcaption></figure>

The cycle condition ensures that every node transformed by the rule ends up belonging to an *ijij*-cycle for all $0 \le i \le i + 2 \le j \le n$. The first point requires that added nodes belong to an *ijij*-cycle in *R*, as all their adjacent arcs belong to *R*. For example, the rule of Figure 16(a) adds two nodes *o* and *p* without their 0202-cycle in *R*. Consequently, they do not belong to such a cycle in the resulting graph *H*. The second point requires that preserved nodes which belong to an *ijij*-cycle in *L* also belong to such a cycle in *R*. Similarly to the previous point, their adjacent *i*-arcs and *j*-arcs belong to *R*, therefore the *ijij*-cycle has to belong to *R*. The last point requires that preserved nodes which do not belong to an *ijij*-cycle in *L* have their adjacent *i*-arcs and *j*-arcs also preserved. As a matter of fact, any modification of those arcs might break the *ijij*-cycle as it is only partially matched by the rule. For example, in Figure 16(b), by removing the 0-arc between nodes *e* and *h* in the rule, we break the 0202-cycle in the resulting graph *H*.
# 5. Embedded generalized maps and their basic transformations

Our approach is generic, both in terms of the dimension of the objects and of the nature of the considered embedding. For simplicity purposes, in the following *n*-G-maps will be simply denoted as G-maps. Moreover, all illustrative examples will be given for 2D objects with either one of the two embedding data types of Figure 11(a): we will either consider 2D positions attached to topological vertices or colors attached to faces. However, realistic objects simultaneously handle several data types holding on different topological cells.

## 5.1. Embedding representation

The topological structure of *n*-G-maps have been defined as labeled graphs where the arc label set is $C_E = [0, n]$. We complete here this definition with node labels to represent the embedding. We already sketched that every dedicated embedding has its own data type and is defined on a particular kind of topological cell: in our example, positions are attached to vertices and colors to faces.

A node labeling function defining an embedding will be typed both by a topological orbit type and a data type. We characterize such a node labeling function as an *embedding operation* $\pi : \langle o \rangle \to \tau$ where $\pi$ is the operation name, $\tau$ is its data type and $\langle o \rangle$ is its domain given as an *n*-dimensional orbit type. Hence, for a G-map embedded on an embedding $\pi : \langle o \rangle \to \tau$, the node label set $C_V$ is the set of values $\lfloor \tau \rfloor$ of type $\tau$ and when the profile of $\pi$ is obvious, the node labeling function is simply noted $\pi$. Thus, a G-map provided with a single embedding will be a particular case of partially labeled graph, generically denoted as a tuple $(V, E, s, t, \pi, \alpha)$.

<figure><img src="image_27.png" /><figcaption>Figure 17: Two embedding operations</figcaption></figure>

In this article, we consider the following embedding operations:

* pos : $\langle 1 \ 2 \rangle \to \text{point.2D}$ the embedding that associates 2D positions (values of type `point_2D`) with vertices ($\langle 1 \ 2 \rangle$-orbits) of 2-G-maps (see Figure 17(a));

* col : $\langle 0 \ 1 \rangle \to \text{color}$ the embedding that associates colors (values of type `color`) with faces ($\langle 0 \ 1 \rangle$-orbits) of 2-G-maps (see Figure 17(b)).

Moreover, as an embedding operation $\pi : \langle o \rangle \to \tau$ is characterized by its domain orbit, it is expected that in an embedded G-map $G = (V, E, s, t, \pi, \alpha)$, all nodes of a common $\langle o \rangle$-orbit share the same label by $\pi$, also called $\pi$-label. For example, in Figure 17(a), nodes $c, e, g$ and $i$ that belong to the same vertex orbit $\langle 1 \ 2 \rangle$ are labeled by the same value $B$. Similarly, in Figure 17(b), nodes $a, b, c, d, e$ and $f$ that belong to the same face are labeled with the same yellow color. This property is captured by an embedding constraint that embedded<fnref n="8" /> G-maps have to satisfy [13].

<footnote n="8">⁸To be in agreement with the community of geometric modeling, we chose the term "embedded" rather than the term "attributed", most commonly used in the graph transformation community.</footnote>
**Definition 5 (Embedded graph and embedded generalized map).** Let $\pi : \langle o \rangle \to \tau$ be an embedding operation of dimension $n \ge 0$ with $\langle o \rangle$ an orbit type of dimension $n$ and $\tau$ a data type.

* Embedded graph: A graph embedded on $\pi$, or $\pi$-embedded graph, is an $n$-topological graph $G = (V, E, s, t, \pi, \alpha)$ where $\pi$ labels nodes on $C_V = [\tau]$.

* Embedding consistency constraint: A $\pi$-embedded graph satisfies the embedding consistency constraint if for all nodes $v$ and $w$ such that $v \equiv_{\langle o \rangle} w$, $\pi(v) = \pi(w)$ or $\pi(v) = \perp$ or $\pi(w) = \perp$.

* Embedded G-map: A $\pi$-embedded G-map is an $n$-G-map embedded on $\pi$ satisfying the embedding consistency constraint and such that $\pi$ is a total function (i.e. $\text{Dom}(\pi) = V$). $\triangleleft$

Note that the embedding consistency constraint allows an $\langle o \rangle$-orbit to be partially $\pi$-labeled as long as the defined $\pi$-labels are equal. Therefore, as embedded G-maps are totally labeled, the constraint entails that all nodes of any $\langle o \rangle$-orbit share the same embedding value, i.e. for all nodes $v$ and $w$ such that $v \equiv_{\langle o \rangle} w$, $\pi(v) = \pi(w)$ with $\pi(v) \neq \perp$.

Intuitively, the topological structure of any $\pi$-embedded graph $G$ can then be found by forgetting node labels. For $G = (V, E, s, t, \pi, \alpha)$, $G_\alpha = (V, E, s, t, \perp, \alpha)$ denotes the underlying topological structure where the everywhere undefined function $\perp$ replaces the node labeling function $\pi$.

As $\equiv_{\langle o \rangle}$ defines a partition of the set $V$ of nodes of a $\pi$-embedded graph $G$ that satisfies the embedding consistency constraint, it allows to build a quotient graph of $G$ along $\langle o \rangle$-orbits. For the quotient set of nodes, we consider the set of $\langle o \rangle$-orbits of $G$. As all nodes of an $\langle o \rangle$-orbit of $G$ are unlabelled or share the same $\pi$-label, the resulting quotient node directly inherits this shared $\pi$-label if this label exists. For the quotient set of arcs, we consider the set of arcs inherited from $G$ by redefining source and target nodes with their corresponding quotient nodes and by preserving their labels.

<figure><img src="image_28.png" /><figcaption>Figure 18: Quotients of the embedded 2-G-maps given in Figure 17</figcaption></figure>

For example, the quotient along $\langle 1 \rangle$-orbits of the embedded G-map of Figure 17(a) is the graph of Figure 18(a). As nodes $c$, $g$, $e$ and $i$ belong to the same vertex orbit, they share the same embedding $B$ and give rise to the $B$-labeled quotient node $v$ in Figure 18(a). The resulting quotient graph contains 5 nodes, one per $\langle 1 \rangle$-orbit, with a well-defined $\pi$-label. Let us note that by construction, arcs with labels belonging to the orbit type $\langle 1 \rangle$ become loops. As a consequence, all 1-arcs and 2-arcs adjacent to $c$, $e$, $g$ or $i$ are transformed into loops on node $v$ in the quotient graph.

Similarly, Figure 18(b) presents the quotient along $\langle 0 \rangle$-orbits of the 2-G-map of Figure 17(b). Nodes $a$, $b$, $c$, $d$, $e$ and $f$ of the triangle face give rise to the yellow quotient node $u$ while the nodes of the square face give rise the blue quotient node $v$. In the case of Figure 17(b), we get two nodes with two different colors. Of course, it would have been possible to get nodes sharing the same color. Indeed, it would suffice that the initial G-map contains several faces sharing the same color.
**Definition 6 (Embedding quotient).** Let $G = (V, E, s, t, \pi, \alpha)$ be a graph embedded on $\pi: \langle o \rangle \to \tau$ that satisfies the embedding consistency constraint.

The $\pi$-quotient<sup>9</sup> graph of $G$ is the graph $G_{/\pi} = (V_{/\pi}, E_{/\pi}, s_{/\pi}, t_{/\pi}, \pi_{/\pi}, \alpha_{/\pi})$ defined by:

* $V_{/\pi} = V_{\equiv \langle o \rangle}$;

* $E_{/\pi} = E$ with $\forall e \in E_{/\pi}, \alpha_{/\pi}(e) = \alpha(e), s_{/\pi}(e) = [s(e)]$ and $t_{/\pi}(e) = [t(e)];$

* for $[v]$ in $V_{\equiv \langle o \rangle}$, $\pi_{/\pi}([v]) = \pi(v)$ if there exists $w$ in $G\langle o \rangle(v)$ such that $\pi(w) \neq \perp$, otherwise $\pi_{/\pi}([v]) = \perp$.

The $\pi$-quotient morphism $q: G \to G_{/\pi}$ is defined by: $\forall v \in V, q_V(v) = [v]$ and $q_E = \text{id}$. $\quad \blacksquare$

Note that as embedded G-maps both satisfy the embedding consistency constraint and are totally labeled, their quotient graphs are also totally labeled.

## 5.2. Basic embedding transformations

As $\pi$-embedded G-maps constitute a particular class of partially labeled graphs, we now investigate how modeling operations on embedded G-maps that modify their geometry can be defined using graph transformation rules (see Definition 1). As an example, we consider the two operations given in Figure 19 that apply on objects with the position embedding $pos: \langle 1, 2 \rangle \to \text{point\_2D}$. The vertex translation of Figure 19(a) in a purely geometric operation as it does not affect the topological structure. Position $B$ is translated to $F$. Conversely, the edge folding of Figure 19(b) affects both the topological structure and the embedding. An edge of the square face is split into two edges by introducing a new vertex which is embedded by the point\_2D value $G$.

<figure><img src="image_29.png" /><figcaption>Figure 19: Two operations on the position embedding</figcaption></figure>

In this section, we explore to what extent basic geometric modeling operations designed for a particular embedded $G$-map can be defined as basic graph transformations as introduced in Definition 1. The key point is to ensure these consistency constraints of embedded $G$-maps are preserved along rules applications, provided that rules satisfy some syntactic conditions.

In the same way that we gave in Theorem 1 syntactic conditions for the preservation of topological consistency constraints, we here investigate syntactic conditions to ensure that embedded $G$-maps are transformed into embedded $G$-maps. Let us take the example of the vertex translation of Figure 19(a). Intuitively, we could consider at first sight the rule of Figure 20(a). Unfortunately, such a rule is not appropriate for our needs. Indeed, by matching node $e$ of the rule of Figure 20(a) with node $e$ of the $G$-map of Figure 17(a), its application results in the graph given in Figure 20(b). Clearly, this graph does not satisfy the embedding consistency constraint as node $e$ does not have the same label as the other nodes of its vertex orbit $(c, g$ and $i)$.

<footnote n="9">⁹Let $X$ be a set and $\equiv$ an equivalent relation on $X$, the equivalence class $[x]$ of any element $x \in X$ is defined as $[x] = \{y \in X \mid x \equiv y\}$, and the quotient set $X_{/\equiv}$ is the set $\{[x] \mid x \in X\}$.</footnote>
<figure><img src="image_30.png" /><figcaption>Figure 20: Incoherent translation</figcaption></figure>

To avoid this, all node labels of an embedding orbit should be modified simultaneously and in the same manner. For example, the rule of Figure 21(a) matches (respectively rewrites) a full vertex orbit in $L$ (respectively in $R$): indeed, all nodes are connected with both 1-arcs and 2-arcs. In fact, both $L$ and $R$ are full $\langle 1, 2 \rangle$-orbits. Thus, the application of this rule to the pos-embedded 2-G-map of Figure 17(a) along the identity match morphism gives the pos-embedded 2-G-map of Figure 21(b). The following theorem introduces syntactic conditions on rules that ensure embedding consistency preservation.

<figure><img src="image_31.png" /><figcaption>Figure 21: Coherent translation</figcaption></figure>

**Theorem 2 (Preservation of the embedding consistency).** Let $\pi : \langle o \rangle \to \tau$ be an embedding operation, $r : L \leftrightarrow K \leftrightarrow R$ be a $\pi$-embedded graph transformation rule that satisfies conditions of topological consistency preservation, $G$ a $\pi$-embedded $G$-map and $m : L \to G$ a match morphism.

The direct transformation $G \Rightarrow^{r,m} H$ produces a $\pi$-embedded $G$-map if the following conditions of embedding consistency preservation are satisfied:

* Embedding consistency: $L, K$ and $R$ satisfy the embedding consistency constraint of Definition 5.

* Full match of transformed embeddings: if $v$ is a node of $K$ such that $\pi_L(v) \neq \pi_R(v)$, then every node of $R\langle o \rangle(v)$ is labeled and is the source of exactly one $i$-arc for each $i$ of $\langle o \rangle$.

* Labeling of extended embedding orbits: if $v$ is a node of $K$ and there exists a node $w$ in $R\langle o \rangle(v)$ such that $w$ is not in $L\langle o \rangle(v)$, then there exist $v'$ in $K$ with $v' \equiv_{L\langle o \rangle} v$ and $v' \equiv_{R\langle o \rangle} v$ such that $\pi_L(v') \neq \bot$. $\triangleleft$

**Proof.** Let $\pi : \langle o \rangle \to \tau$ be an embedding operation, $r : L \leftrightarrow K \leftrightarrow R$ be a graph transformation rule that satisfies the conditions of topological consistency preservation, $G$ a $\pi$-embedded $G$-map and $m : L \to G$ a match morphism. We consider the following direct transformation:
<figure><img src="image_32.png" /></figure>

In double-pushout transformation, each element of $H$ (node, arc, or label) comes either from the right-hand side of the rule $R$, or from the graph $G$ (through $D$), or from both. Therefore, to check whether two nodes of $H$ linked with an arc labeled in $\langle o \rangle$ are labeled with the same embedding value, the proof considers all cases for the arc source, target and labelling.

Since the rule $r$ satisfies the conditions of topological consistency preservation of Theorem 1, the direct transformation $G \Rightarrow^{r,m} H$ is well-defined (i.e. the dangling condition is satisfied) and the resulting graph $H$ is an $n$-G-map. Moreover, with the result of [14] stating that total labeling is preserved by rule application, we know that $H$ is totally labeled, in particular that $\pi$ is defined on every node of $H$.

It remains to prove that thanks to the conditions listed in Theorem 2, $H$ is a $\pi$-embedded G-map.

We then show by exhaustion<fnref n="10" /> that for any label $i$ of the orbit type $\langle o \rangle$, and for any $i$-arc $e$ of $H$, the source node $v$ of $e$ and the target node $w$ of $e$ have the same defined $\pi$-label, i.e. $\pi_H(v) = \pi_H(w)$. As this will ease some symmetrical cases, let us note that thanks to the symmetry preservation (see Theorem 1), $e$ has always a symmetric $i$-arc with source $w$ and target $v$ in $H$ and also in $D$ (resp. $G$) if $e$ is also an arc of $D$ (resp. $G$).

1. $e$ has no antecedent in $R$. Then $e$ necessarily comes from $G$. More precisely $e$, $v$ and $w$ are arc and nodes of $D$ and $G$ respectively.

(a) Both $v$ and $w$ have no antecedent in $R$. Then $v$ (resp. $w$) has the same $\pi$-label in $G$ ($\pi_G(v) = \pi_H(v)$ and $\pi_G(w) = \pi_H(w)$), $D$ and $H$. As $G$ is a $\pi$-embedded G-map, $\pi_G(v) = \pi_G(w)$. Therefore $\pi_H(v) = \pi_H(w)$.

(b) Both $v$ and $w$ have two antecedents $v'$ and $w'$ in $R$. Because of the adjacent arcs condition of Theorem 1, $R$ has no $i$-arc neither with source $v'$ nor $w'$. And thus $R\langle o \rangle(v')$ and $R\langle o \rangle(w')$ are not full orbits. Because of the condition of full match of transformed embeddings, $v'$ and $w'$ are preserved nodes with preserved $\pi$-labels, i.e. $\pi_L(v') = \pi_R(v')$ and $\pi_L(w') = \pi_R(w')$. Thus $v$ and $w$ have the same defined $\pi$-label in $G$ and $H$, i.e. $\pi_G(v) = \pi_H(v)$ and $\pi_G(w) = \pi_H(w)$. As $G$ is a $\pi$-embedded G-map, $\pi_G(v) = \pi_G(w)$ and therefore $\pi_H(v) = \pi_H(w)$.

(c) $v$ has an antecedent $v'$ in $R$, and $w$ has no antecedent in $R$. According to case 1a, $w$ has the same defined $\pi$-labels in $G$ and $H$ ($\pi_G(w) = \pi_H(w)$). According to case1b, $v$ has the same defined $\pi$-labels in $G$ and $H$ ($\pi_G(v) = \pi_H(v)$). Finally, as $G$ is a $\pi$-embedded G-map, $\pi_G(v) = \pi_G(w)$ and therefore $\pi_H(v) = \pi_H(w)$.

(d) $v$ has no antecedent in $R$ and $w$ has an antecedent in $R$. This case is similar to case 1c.

2. $e$ has an antecedent $e'$ in $R$. Let $v'$ and $w'$ be the source and target nodes of $e'$ in $R$, respectively.

(a) Both $v'$ and $w'$ have defined $\pi$-labels in $R$, i.e. $\pi_R(v') \neq \perp$ and $\pi_R(w') \neq \perp$. Thanks to the embedding consistency condition, $v'$ and $w'$ have the same defined $\pi$-label, $\pi_R(v') = \pi_R(w')$ and therefore $\pi_H(v) = \pi_H(w)$.

(b) Both $v'$ and $w'$ have undefined $\pi$-labels in $R$, i.e. $\pi_R(v') = \perp$ and $\pi_R(w') = \perp$. Thanks to the rule definition (see Definition 1), $v'$ and $w'$ are nodes of $K$ and thus of $L$, with $\pi_L(v') = \perp$ and $\pi_L(w') = \perp$. Then $v$ and $w$ also come from $G$, but not necessarily from the same $\langle o \rangle$-orbit.

i. $v'$ and $w'$ do not come from the same $\langle o \rangle$-orbit, i.e. $v' \not\equiv_{L\langle o \rangle} w'$. Thanks to the condition of labeling of extended embedding orbits, there exists $x' \in K$ with $x' \equiv_{L\langle o \rangle} v'$ and $x' \equiv_{R\langle o \rangle} v'$ such that $\pi_L(x') \neq \perp$ and therefore $\pi_R(x') \neq \perp$. Symmetrically, there exists $y' \in K$ with $y' \equiv_{L\langle o \rangle} v'$ and $y' \equiv_{R\langle o \rangle} v'$ such that $\pi_L(y') \neq \perp$ and therefore $\pi_R(y') \neq \perp$. Moreover, as $x' \equiv_{R\langle o \rangle} y'$, the embedding consistency condition ensures that

<footnote n="10">¹⁰Cases are hierarchically numbered to ease proof commentary.</footnote>
$\pi_R(x') = \pi_R(y')$. Thanks to the condition of full match of transformed embeddings, $x'$ and $y'$ have their $\pi$-label preserved by the rule as their $\langle o \rangle$-orbit in $R$ is not totally labeled, and therefore $\pi_L(x') = \pi_L(y')$ (both defined). As $v' \equiv_{L\langle o \rangle} x'$ and $w' \equiv_{L\langle o \rangle} y'$, we have $v \equiv_{G\langle o \rangle} x$ and $w \equiv_{G\langle o \rangle} y$ with $x$ and $y$ the respective images of $x'$ and $y'$ in $G$. Then because $G$ is a $\pi$-embedded G-map, $\pi_G(v) = \pi_G(x)$ and $\pi_G(w) = \pi_G(y)$ and therefore $\pi_H(v) = \pi_H(w)$.

ii. $v'$ and $w'$ come from the same $\langle o \rangle$-orbits, i.e. $v' \equiv_{L\langle o \rangle} w'$. Then $v \equiv_{G\langle o \rangle} w$ and because $G$ is a $\pi$-embedded G-map, $\pi_G(v) = \pi_G(w)$ and then $\pi_H(v) = \pi_H(w)$.

(c) $v'$ has a defined $\pi$-label in $R$ but not $w'$, i.e. $\pi_R(v') \neq \bot$ and $\pi_R(w') = \bot$. Thanks to the rule definition, $w'$ is a node of $K$ and thus of $L$ with $\pi_L(v') = \bot$. Because of the condition of full match of transformed embeddings, $v'$ can not be an added node and is therefore also a node of $K$ and thus of $L$ with $\pi_L(v') \neq \bot$. The proof is then similar to case 2b, with two cases depending on whether $v'$ and $w'$ come from the same $\langle o \rangle$-orbit, but using directly $v'$ instead of $x'$ as it is labeled.

(d) $w'$ has a defined $\pi$-label in $R$ but not $v'$, i.e. $\pi_R(w') \neq \bot$ and $\pi_R(v') = \bot$. This case is similar to case 2c.

By transitivity of arcs labeled in $\langle o \rangle$, all nodes $v$ and $w$ of $H$ in the same $\langle o \rangle$-orbit ($v \equiv_{H\langle o \rangle} w$) have the same defined $\pi$-label, i.e. $\pi_H(v) = \pi_H(w)$. Thus $H$ is a $\pi$-embedded G-map. $\quad$

<figure><img src="image_33.png" /><figcaption>Figure 22: Two non-consistent rules that break conditions of Theorem 2</figcaption></figure>

Let us now make some comments on the constraints given in Theorem 2.

The first of these conditions is straightforward: it requires that all parts of the rule satisfy the embedding consistency constraint. For example, the rule of Figure 22(a) breaks this condition as it adds a new vertex (nodes $o$, $p$, $q$ and $r$) embedded with two different positions $F$ and $G$.

The second condition forbids the partial redefinition of the embedding shared by an $\langle o \rangle$-orbit as it would break the embedding consistency. If a preserved node has a transformed embedding, then its $\langle o \rangle$-orbit in $R$ is a totally labeled full orbit. The rule of Figure 20(a) falls in this case as node $e$ has its label changed from $B$ to $F$ without fully matching the topological vertex (1-arc and 2-arc are missing). Hence, an embedding value can only be modified if it is modified for the whole support orbit.

The last condition forbids the extension of an $\langle o \rangle$-orbit (by adding new nodes or merging with another $\langle o \rangle$-orbit) without matching the existing embedding value of the orbit. For example, the rule of Figure 22(b) breaks this condition as an half-edge whose embedding is unmatched is added to another half-edge whose vertices are embedded by the two positions $F$ and $G$. Therefore, the application of this rule to the object of Figure 17(a) along the identity morphism would break the embedding consistency: e.g. node $b$ would be labeled by $A$ while its added 2-neighbor $u$ would be labeled by $F$. As this third condition entails that nodes $b$ and $d$ are labeled in $L$ (and thus in $R$), the rule labeling should be completed. In $R$, nodes $b$ and $d$ should be labeled by $F$ and $G$ respectively due to the embedding consistency condition. In $L$, they should also be labeled by $F$ and $G$ as the condition of full match of transformed embeddings prevents to change their labels while the two vertex orbits are not fully matched by the rule (1-neighbors of $b$ and $d$ are not matched).
<figure><img src="image_34.png" /><figcaption>Figure 23: Application of the edge folding</figcaption></figure>

At last, let us illustrate some of the cases occurring in the proof of Theorem 2 with the example of Figure 23 that details the application of the edge folding operation presented in Figure 19(b) on the embedded G-map of Figure 17(a). The 1-arc that links nodes *a* and *b* in *H* falls into the trivial case 1a. The arc and the two nodes belong to object *G* and are not matched by the rule. As *G* satisfies the embedding consistency constraint of embedded G-maps, nodes *a* and *b* have the same *pos*-label in *G* and therefore in *H*. The 1-arc that links nodes *i* and *g* in *H* falls into the case 1c, as the arc and node *g* are not matched by the rule, conversely to node *i*. As the vertex orbit that contains both nodes *i* and *g* in *G* is not fully matched, the condition of the full match of transformed embeddings prevents the rule to modify the *pos*-labels of node *i*. This ensures that nodes *i* and *g* have the same *pos*-label in *H* as they have the same *pos*-label in *G*. Finally, the 1-arc that links nodes *u* and *v* with define labels in *H* falls into the case 2a and the embedding consistency condition ensures that their *π*-labels are equal in *R*.

# 6. Rule schemes

This section introduces the rule scheme syntax that allows us to define modeling operations indepen-
dently from the object embedding values. Following the approach of [15], this syntax includes the use of
dedicated variables.

## 6.1. *Node variables*

As mentioned in Section 3, attribute variables of [15] do not exactly fit our usage. Computing the
new embedding requires both to access the existing embedding (node labels in the transformed object)
and to traverse the topological structure (neighboring nodes in the transformed object). Therefore,
taking benefit from G-maps regular structures, this article introduces new variables called *node variables*
and provides dedicated operators. Instead of defining a new set of variable names, this approach consists
in directly using the identifiers of the nodes of *L* as variables, and therefore variable names freely exist
for all transformations.

The rule schemes of Figure 24 respectively define the translation of a vertex and the folding of an edge,
both previously illustrated in Figure 19. Scheme nodes are labelled with terms<fnref n="11" /> over node variables
of *L*, allowing both to match the existing embedding and to express the new embedding computation. In
Figure 24(a), the term *e.pos* in *L* gives access to the 2D position associated to the matched vertex, while
the term *e.pos* + *v̄* defines in *R* the new position for the translated position<fnref n="12" />. At scheme application, the

<footnote n="11">¹¹Note that terms are detailed on top of the rules for readability purposes.</footnote>

<footnote n="12">¹²In accordance with Definition 1, rule nodes must be labeled in *L* in order to relabel them.</footnote>
<figure><img src="image_35.png" /><figcaption>Figure 24: Rule schemes of the operations of Figure 19</figcaption></figure>

node variable *e* of *L* will be substituted by the node matched by *e* in the transformed object. The operator .pos (resp. .π) will then simply grant access to its pos-label (resp. π-label). Similarly in Figure 24(b), *i.pos* and *k.pos* are the two positions associated to the matched edge and *center*(*i.pos*, *k.pos*) defines the corresponding center.

<figure><img src="image_36.png" /><figcaption>Figure 25: Face triangulations on the color embedding</figcaption></figure>

As described in Section 4, *n*-G-maps are highly regular graphs. Every node has *n* + 1 neighbors respectively connected by 0, 1, ..., *n*. Therefore, for all *i* in [0, *n*], we can define an `.α*_i*` operator on node variables that gives access to their unique *i*-neighbor. Let us consider the face triangulation of Figure 25 in the case of the color embedding *col*: ⟨0 1⟩ → *color*. To smooth face colors, each created triangle is colored by the mix between the original color of the triangulated face and the color of its adjacent face. Using the `.α*_2*` operator to access adjacent faces, this operation is defined by the rule scheme of Figure 26(b). In the term *v* = *mix*(*e.col*, *e.α*_2*.col) that defines the color of the bottom face, *e.α*_2 allows the access to the 2-neighbor of *e* in the transformed object. At application to the object of 26(a) along the identity morphism (as in Figure 25(a)), this neighbor is *g* and the face color is therefore defined as *mix*(*e.col*, *g.col*) = *mix*(●, ●) = ●. Similarly, if the scheme is applied as in Figure 25(b)

<figure><img src="image_37.png" /><figcaption>Figure 26: Face triangulations of Figure 25 on a *col*-embedded *G*-map</figcaption></figure>
with a match morphism that associates node *e* in the rule with node *l* in the transformed object, the face color is defined as $mix(l.col, l.α_2.col) = mix(●, ●) = ●$. Finally, note that the case of nodes without adjacent face is covered thanks to the 2-loops - *e.g* in the first case of Figure 25(a), the term $u = mix(b.col, b.α_2.col)$ is evaluated as $mix(b.col, b.col) = mix(●, ●) = ●$.

## 6.2. Collect operators

In addition to basic operators (`.π` and `.α_i`), we introduce operators that collect all the embedding values carried by a given orbit. Let us illustrate these operators with the face triangulation, but in the case of the position embedding `pos`: $⟨1 2⟩ → point\_2D$. It is usually expected that the created vertex is positioned at the center of the triangulated face. For example, to triangulate the top triangle of the object of Figure 27(a), the added vertex should be positioned at the barycenter of A, B and C.

<figure><img src="image_38.png" /><figcaption>Figure 27: Face triangulation on a pos-embedded G-map</figcaption></figure>

To compute this barycenter, the rule scheme of Figure 27 uses the operator $pos_{⟨0 1⟩}$ to collect the positions carried by the adjacent face (adjacent $⟨0 1⟩$-orbit). At scheme application to the object of Figure 27(a) along the identity match morphism, $pos_{⟨0 1⟩}(a)$ will collect the multiset $[[A, B, C]]$. Similarly, its application to the second triangle will result in $[[B, C, D]]$. Intuitively, this operator is based on the quotient representation introduced in Definition 6 that associates each embedding orbit to a single node, and therefore to a single label.

Consequently, each position value appears only once in the resulting multisets regardless of how many times they appears in the object (*e.g* A appears 4 times while B appears 6 times in Figure 27(a)). If a same position was collected multiple times, this would entail that multiple vertices would be embedded with this same position. In the case of geometrical points, we usually do not want two vertices to coincide. However, for most applicative data such as colors, quantities or densities, it is common that the same value appears multiple time in the modeled object. Let us consider the example of the operator $col_{⟨0 1 2⟩}$ that collects the face colors of the adjacent connected component. The evaluation of $col_{⟨0 1 2⟩}(a)$ on the colored object of Figure 26(a) results in the multiset $[●, ●, ●, ●]$ in which ● has two occurrences as it labels two faces.

More generally, for all embedding $π: ⟨o⟩ → τ$ and all orbit type $⟨o'⟩$, we can define an operator $π_{⟨o'⟩}$ on nodes $v$. $π_{⟨o'⟩}(v)$ collects the embedding values of the $⟨o⟩$-orbit adjacent to $v$ and stores the collecting values with their multiplicity in a multiset, regardless of embedding orbit sizes. Until now, the family of collect operators has be introduced only from an intuitive point of view, we will formally define it in the next sections, syntactically in Section 6.3 and semantically in Section 6.4 using graph quotients introduced in Definition 6.

## 6.3. Terms and schemes

To sum up, node variables are available straightaway as they are the node identifiers of the left-hand side of the rule scheme *L*, and they will be substituted by nodes of the transformed G-map at rule
scheme application. New embedding values are defined by terms upon these nodes with the introduced
G-map operators: the embedding access $\pi$, the neighbor access $\alpha_i$, and the collect of orbit embeddings
$\pi_{\langle o \rangle}$. Note that in addition to these operators, terms may include various operators and types provided
by the user. For example, the translation scheme of Figure 24(a) uses the classical addition between a
point and a vector, while the triangulation scheme of Figure 27(b) uses the operator *bary* that defines
the barycenter of a point multiset. These operators and types provided by the user are referred in the
following as the user signature.

As in Subsection 3.4, we define embedding terms on the user signature extended by the node variables.
A dedicated type (called *Node*) provided with some predefined operations is introduced to manipulate
these variables in relation the underlying graph structure.

**Definition 7 (Terms signature and rule schemes).** Let $\pi : \langle o \rangle \rightarrow \tau$ be an embedding operation of dimension $n$.

**Terms signature.** Let $\Omega_\pi = (S_\pi, F_\pi)$ be a user signature with $S_\pi$ a set of type names including the $\pi$-type $\tau$ and $F_\pi$ a set of functions defined on $S_\pi \cup S_\pi^\bullet$.

$\Omega_{Map} = (S_{Map}, F_{Map})$ is the embedding term signature extended on G-maps defined as $S_{Map} = S_{\pi} \cup \{\text{Node}\}$ and $F_{Map} = F_{\pi} \cup F_{\text{Node}}$ with $F_{\text{Node}}$ the set of function names that contains :

* $\pi : \text{Node} \rightarrow \tau$;

* $\alpha_i : \text{Node} \rightarrow \text{Node for all } i \in [0, n]$;

* $\pi_{\langle o' \rangle} : \text{Node} \rightarrow \tau^\bullet$ for all orbit type $\langle o' \rangle$ of dimension $n$.

**Graph schemes.** Let $X$ be a set of node variables. A graph scheme $G = (V, E, s, t, \pi, \alpha)$ on $(\Omega_\pi, X)$ is a graph embedded on $\pi : \langle o \rangle \rightarrow T_{\Omega_{Map}}(X)_\pi$.

**Rule schemes.** A rule scheme $r: L \leftrightarrow K \leftrightarrow R$ on $\Omega_\pi$ is a rule on graph schemes on $(\Omega_\pi, V_L)$ with $V_L$ the node set of $L$. $\triangleleft$

For example, the triangulation rule scheme of Figure 26(b) on $\Omega_{col} = (S_{col}, F_{col})$ such that $S_{col}$ includes the type *color* and $F_{col}$ includes the operation *mix* : *color* $\times$ *color* $\rightarrow$ *color*. Similarly, the rule scheme of Figure 27(b) on $\Omega_{pos} = (S_{pos}, F_{pos})$ such that $S_{pos}$ includes the type *point_2D* and $F_{pos}$ includes the operation *bary* : *point_2D* $\bullet$ *point_2D*.

### 6.4. Evaluation of embedding terms

At rule scheme application, embedding terms have to be evaluated on the embedded G-map under
transformation. For example, when the triangulation scheme of Figure 27(b) is applied to the top
triangle Figure 27(a), the term $pos_{\langle 0 \ 1 \rangle}(a)$ has to be evaluated by the point multiset $[A, B, C]$ in order
to compute the barycenter. The evaluation of terms on G-maps operators is given in the following
definition as an extension of the algebra provided by the user on the signature $\Omega_\pi$ of his/her sorts
and functions. More precisely, given a $\pi$-embedded G-map and an $\Omega_\pi$-algebra, we define the extended
$\Omega_{Map}$-algebra on embedding terms (see Section 3.4).

**Definition 8 (Algebra extension by a G-map).** Let $G = (V, E, s, t, \pi, \alpha)$ be an $n$-G-map embedded on $\pi : \langle o \rangle \rightarrow \tau$, $\Omega_\pi = (S_\pi, F_\pi)$ be a user signature and an $\Omega_\pi$-algebra $\mathcal{A}$.

The extended algebra $\mathcal{A}_G$ from $\mathcal{A}$ by $G$ is the $\Omega_{Map}$-algebra defined as:

* $(\mathcal{A}_{Map})_s = \mathcal{A}_s$ for $s \in S_\pi \cup S_\pi^\bullet$;

* $(\mathcal{A}_{Map})_{\text{Node}} = V$;

* for each $f$ of $F_\pi$, $f^{A_{Map}} = f^A$;

* $\pi^{A_{Map}}$ is the labeling function $\pi$;
* for all $i \in [0, n]$, for each node $v \in V$, there exists a unique $i$-arc $e \in E$ such that $s(e) = v$ and the $\alpha_i^{A_{Map}}$ function associates $v$ to $t(e)$;

* for all orbit type $\langle o' \rangle$, for each node $v \in V$, let $G\langle o' \rangle(v)/\pi = (V', E', s', t', \pi', \alpha')$ be the embedding quotient of the orbit graph, the $\pi_{\langle o' \rangle}^{A_{Map}}$ function associates $v$ to the label multiset of the orbit quotient $^{13}[[\pi'(v') | v' \in V']]]$. $\quad \triangleleft$

<figure><img src="image_39.png" /><figcaption>Figure 28: Evaluation of the multiset of the face positions</figcaption></figure>

In particular, the evaluation of collect operators is defined with the graph quotient introduced in Definition 6. For example, to evaluate the term $pos_{\langle 0 \ 1 \rangle}(a)$ for the object of Figure 28, we construct the quotient $\langle 0 \ 1 \rangle(a)_{/\text{pos}}$ of the orbit $\langle 0 \ 1 \rangle(a)$. The term evaluation is then defined as the multiset of node labels of that quotient, i.e. $[[A, B, C]]$.

Note that an algebra extension from a G-map is well defined. Especially, thanks to G-maps constraints, one node is the source of one and only one $i$-arc and so $\alpha_i^{AG}$ is a well defined function. As a consequence, collect operators are also well defined functions.

<figure><img src="image_40.png" /><figcaption>Figure 29: Two evaluations of the rule scheme Figure 26</figcaption></figure>

To be evaluated, a scheme only requires a kernel match as described in Subsection 3.3. In our case, we will use a match morphism of the topological structure of the left-hand-side $m: L_\alpha \to G$ in order to remove variable occurrences with node labels, while still properly matching the structure thanks to arc labels. Practically, the node matching part $m_V$ of this morphism will be directly used for the substitution $\sigma: X \to V_G$. For example, an identity match morphism between the rule scheme and the object of Figure 26 assigns the variables $a, b$ and $e$ to the nodes $a, b$ and $e$ of the object, resulting in the rule Figure 29(a). Similarly, the rule of rule Figure 29(b) result from a match morphism assigning those nodes to the nodes $i, g$ and $l$ of the object.

<footnote>$^{13}$We write $[[\pi'(v') | v' \in V']]]$ the multiset of type $\tau^\bullet$ such that for all $x : \tau$, the multiplicity of $x$ is equal to the number of node of $V'$ labeled by $x$.</footnote>
**Definition 9 (Rule scheme evaluation).** Let $G$ be a $\pi$-embedded $G$-map, $\Omega_\pi$ a user signature and $A$ an $\Omega_\pi$-algebra.

**Graph scheme evaluation.** Let $S = (V, E, s, t, \pi, \alpha)$ be a graph scheme on $(\Omega_\pi, X)$ and $\sigma : X \to V_G$ an assignment of $X$. The evaluated graph $S^\sigma = (V, E, s, t, \pi^\sigma, \alpha)$ of $S$ along $\sigma$ is the $\pi$-embedded graph such as $\pi^\sigma(v) = \sigma(\pi(v))$ for each node $v \in V$.

**Rule scheme evaluation.** Let $r: L \leftrightarrow K \leftrightarrow R$ be a rule scheme on $\Omega_\pi$ and $m: L_\alpha \to G$ a kernel match morphism. The evaluated rule of $r$ along $m$ is the $\pi$-embedded rule $r^{mv}: L^{mv} \leftrightarrow K^{mv} \leftrightarrow R^{mv}$. ◀

# 7. Rule scheme instantiation

In this section, we define how rule schemes are instantiated without considering the consistency preservation which is postponed to Section 8.

## 7.1. Need for simplicity

<figure><img src="image_41.png" /><figcaption>Figure 30: Expected rule scheme of the translation</figcaption></figure>

So far, every considered operation has been defined in relation to the specific topological structure of the transformed object. This problem was illustrated in Section 5.2 by the rule of Figure 21 which specifically defines the translation for a vertex adjacent to three edges. This is very restrictive and counter-intuitive from a user-end perspective. On a semantic level, the translation of a vertex has a single meaning, independent from the number of adjacent edges. A user friendly rule scheme should be as simple as in Figure 30 in which a single node relabeling encodes a single embedding transformation.

<figure><img src="image_42.png" /><figcaption>Figure 31: Edge removal on the color embedding</figcaption></figure>

Let us take a more significant example with the edge removal of Figure 31. This operation that will be the red thread of this section involves both topological and embedding modifications: on the topological aspect, the edge is removed and the two adjacent faces are merged; on the embedding aspect, the color of the resulting face is obtained by mixing the colors of the two original faces.

Semantically, this operation does not depend on the configurations of the two faces and should be defined by the simple rule scheme of Figure 32(a). But similarly to the translation, the application of the evaluated rule of Figure 32(b) to the object of Figure 26(a) results in the inconsistent object of Figure 32(c). Indeed, the embedding modifications must be propagated to all nodes of the two faces in order to preserve the $G$-map consistency.

Therefore, it is the task of the instantiation process to extend the evaluated rule to propagate the embedding modification. In our example, the evaluated rule of Figure 32(b) has to be extended into the correct rule of Figure 32(d). This process is divided into two steps: the topological extension that matches all required nodes and the embedding propagation that ensures their consistent relabeling.
<figure><img src="image_43.png" /><figcaption>Figure 32: Rule scheme of the edge removal and its evaluation</figcaption></figure>

## 7.2. Topological extension

Intuitively, the topological extension uses the match morphism to complete the partial embedding orbits defined by the evaluated rule with the actual full orbits of the transformed G-map. First, the extension $L^{\oplus m}$ of the left-hand side is computed in Figure 33(a) by pushout between the topological structure of the $\langle o \rangle$-orbit adjacent to the matched pattern $G_\alpha\langle o \rangle(m(L_\alpha)_\alpha)$, and the left-hand side of the evaluated rule $L$. The full extended rule $L^{\oplus m} \leftarrow K^{\oplus m} \hookrightarrow R^{\oplus m}$ is then computed in Figure 33(b) by application of the evaluated rule on the extended left-hand side.

<figure><img src="image_44.png" /><figcaption>Figure 33: Construction of the topological extension</figcaption></figure>

**Definition 10 (Topological extension).** Let $\pi : \langle o \rangle \to \tau$ be an embedding operation and $m : L_\alpha \to G$
be a kernel morphism on a $\pi$-embedded G-map $G$ for a rule $r : L \leftarrow K \hookrightarrow R$.

Let $L^{\oplus m}$ be the result of the pushout between $m_{\langle o \rangle} : L_\alpha \to G_\alpha \langle o \rangle (m(L_\alpha)_\alpha)$, the restriction of $m$ to the topological structure of the $\langle o \rangle$-orbit adjacent to the matched pattern, and the inclusion $L_\alpha \hookrightarrow L$:
<figure><img src="image_45.png" /></figure>

The topological extension of $r$ along the match morphism $m$ is the rule $r^{\oplus m} : L^{\oplus m} \hookrightarrow K^{\oplus m} \hookrightarrow R^{\oplus m}$ defined by the following direct transformation:

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

Note that the pushout construction of $L^{\oplus m}$ is well founded since the morphisms $L_\alpha \hookrightarrow L$ and $m : L_\alpha \to G$ meet the conditions given in [14] ensuring the existence of natural pushouts. Also, note that the resulting rule of Figure 33 would still produce the inconsistent result of Figure 32(c) as extended parts' nodes are not relabeled.

### 7.3. Embedding propagation

The final step of rule scheme instantiation consists in propagating node labels of the extended rule. For example, for the extended rule of Figure 33(b), node labels have to be propagated in order to obtain the final of rule Figure 32(d). This step is a direct application of the quotient representation. For all graphs of the extended rule, each node is relabeled with the label of its images in the quotient graph. For example, in Figure 34 the three quotient graphs allow the embedding propagation of the extended rule of Figure 33(b) - e.g. node a unlabelled in $L^{\oplus m}$ can be labelled with the label of its image $u$ in $L_{\pi/\pi}^{\oplus m}$.

<figure><img src="image_48.png" /><figcaption>Figure 34: Quotients for the embedding propagation</figcaption></figure>

**Definition 11 (Embedding propagation).** Let $G = (V, E, s, t, \pi, \alpha)$ be a graph embedded on $\pi: \langle\cdot\rangle \to \tau$ such that $G$ satisfies the embedding consistency constraint and $q: G \to G_{/\pi}$ the quotient morphism with $G_{/\pi} = (V_{/\pi}, E_{/\pi}, s_{/\pi}, t_{/\pi}, \pi_{/\pi}, \alpha_{/\pi})$.

The $\pi$-embedding propagation of $G$ is the $\pi$-embedded graph $G^{\odot \pi} = (V, E, s, t, \pi', \alpha)$ such for each node $v \in V$, $\pi'(v) = \pi_{/\pi}(q_v(v))$.

For $r: L \hookrightarrow K \hookrightarrow R$ an $n$-topological $\pi$-embedded rule, we denote $r^{\odot \pi}$ the rule $L^{\odot \pi} \hookrightarrow K^{\odot \pi} \hookrightarrow R^{\odot \pi}$. $\quad \blacksquare$

<figure><img src="image_49.png" /></figure>

Note that as the quotient existence depends on the satisfaction of the embedding consistency constraint, the embedding propagation only applies to rules for which all parts satisfy the constraint. The extended patterns must contain only one label value per embedding orbit in order for their quotient representation to preserve these unique labels. Let us consider the counterexample of Figure 35. The rule scheme defines the edge removal without consistently relabeling the face colors and therefore the face can be labeled by two different colors in the right-hand side of the extended evaluated rule. As this prevents the quotient existence, the embedding propagation cannot be applied.

Moreover, the satisfaction of the embedding consistency constraint by all parts of a rule scheme does not entail the same property on its extended rule, because of the overlap phenomenon that will be detailed in Section.
<figure><img src="image_50.png" /><figcaption>Figure 35: Inconsistent edge removal</figcaption></figure>

<figure><img src="image_51.png" /></figure>

### 7.4. Rule scheme application

Regardless of consistency preservation, the application of a rule scheme $r$ to an object defined as an embedded G-map $G$ along a kernel match morphism $m$ consists in the three instantiation steps of Figure 36(a):

1. the evaluation $r^{mv}$ of the rule scheme $r$ along $m_V$ to substitute node variables by nodes of $G$;

2. the topological extension $(r^{mv})^{\oplus m}$ along $m$ of the evaluated rule $r^{mv}$;

3. the embedding propagation $((r^{mv})^{\oplus m})^{\odot \pi}$ along the extended rule $(r^{mv})^{\oplus m}$;

followed by the application of the final rule $((r^{mv})^{\oplus m})^{\odot \pi}$ on the targeted object $G$ by the DPO transformation of Figure 36(a).

<figure><img src="image_52.png" /><figcaption>Figure 36: Rule scheme application</figcaption></figure>

Note that as the embedding propagation existence depends on the satisfaction of the embedding consistency constraint by all parts of the extended rule. This will be ensured by conditions on rule schemes provided in Section 8 to preserve G-map consistency. Therefore, rule schemes satisfying those conditions can always be instantiated for any kernel match morphism.

**Definition 12 (Instantiation and application of rule scheme).** Let $r : L \leftrightarrow K \leftrightarrow R$ be a rule scheme on a user signature $\Omega_\pi$, and $m : L_\alpha \to G$ a kernel match morphism on a $\pi$-embedded G-map $G$.

Let $r^{mv} = L^{mv} \leftrightarrow K^{mv} \leftrightarrow R^{mv}$ be the evaluation of $r$ along $m$ (Definition 9).

Let $(r^{mv})^{\oplus m}$ be the topological extension of $r^{mv}$ along $m$ (Definition 10).

<footnote n="14">¹⁴Thanks to Definition 9 of graph scheme evaluations, $L_\alpha^{mv} = L_\alpha$. Thus the rule can be directly extended along $m$.</footnote>
If all parts of $(r^{mv})^{\oplus m}$ satisfy the embedding consistency constraint, let $((r^{mv})^{\oplus m})^{\odot \pi}$ be the $\pi$-embedding propagation of $(r^{mv})^{\oplus m}$ (Definition 11).

The instantiation of $r$ along $m$ is $((r^{mv})^{\oplus m})^{\odot \pi}$ denoted $r^m : L^m \leftrightarrow K^m \leftrightarrow R^m$.

If there exists a morphism $m^* : L^m \to G$ extending $m$, the application of $r$ to $G$ along $m$ denoted by $G \xrightarrow{r,m} H$ is defined by the direct transformation $G \xrightarrow{r^m, m^*} H$. ◀

Finally, note that similarly to the approach of [15] recalled in Subsection 3.3, the substitution given by the kernel match morphism can not always result in an extended full match of the instantiated rule.

<figure><img src="image_53.png" /><figcaption>Figure 37: Edge removal between two faces of same color</figcaption></figure>

Let us take an example with the operation of edge removal of Figure 37. This time, the rule scheme of Figure 37(a) removes an edge between two faces of the same color e.col. The instantiation of the rule scheme along the identity morphism on the object G of Figure 36 results in the rule of Figure 37(b) where the term e.col has been evaluated to yellow. As the extension process rests on the kernel match, the rule can always be extended regardless of the label of the matched object. However, the resulting rule can obviously not be applied to the object as an application match morphism can not be induced because nodes *g*, *h*, *i* and *j* of the object are blue.

# 8. Consistency preservation

This section establishes and proves the conditions on rule schemes that ensure the preservation of G-map constraints. Subsection 8.1 addresses the topological consistency while Subsections 8.2 and 8.3 focus on the embedding consistency. More precisely, we show that rule schemes that satisfy some given conditions can always be instantiated and that the instantiated rules satisfy the original conditions of embedding consistency preservation of Definition 2.

## 8.1. Topological consistency preservation

As the topological extension is the only part of the instantiation that transforms the rule topological structure, let us show that it preserves the conditions of topological consistency preservation of Theorem 1.

**Lemma 1 (Topological consistency preservation of topological extension).** Let $r: L \hookleftarrow K \hookrightarrow R$ be a rule embedded on $\pi: \langle o \rangle \to \tau$ and $m: L_\alpha \to G$ a kernel match morphism on a $\pi$-embedded G-map $G$.

If $r$ satisfies the conditions of topological consistency preservation of Theorem 1, then the topological extended rule $r^{\oplus m}$ also satisfies these conditions.

**► Proof.** Let us show the three conditions of topological consistency preservation.

### Symmetry

Because an $n$-G-map and its $\langle o \rangle$-orbits are symmetric graphs, the part added by the topological extension is also symmetric. And because $L, K$ and $R$ are symmetric graphs, then $L^{\oplus m}, K^{\oplus m}$ and $R^{\oplus m}$ are also symmetric graphs. Consequently, $r^{\oplus m}$ satisfies the symmetry condition.
## Adjacent arcs

As $K^{\oplus m}$ and $R^{\oplus m}$ are computed by application of $r$ on $L^{\oplus m}$, all new nodes added by the topological extension step are preserved nodes of $K^{\oplus m}$. Consequently, those nodes are the sources of the same arcs with the same labels on both sides $L^{\oplus m}$ and $R^{\oplus m}$. Thus all nodes added by the topological extension satisfy the adjacent arc condition. And because $r$ satisfies the adjacent arc condition, $r^{\oplus m}$ also does.

## Cycle condition

As already mentioned, all nodes added by the topological extension are preserved nodes of $K^{\oplus m}$ and are the source of the same arcs with the same labels in $L^{\oplus m}$ and $R^{\oplus m}$. Thus, we have multiple cases to consider depending on what portion of a cycle belong to the extended part. Let us prove the three points of the cycle condition of Theorem 1 for all couple $(i, j)$ such $0 \le i \le i + 2 \le j \le n$:

* By definition of the topological extension, any added node $v$ of $R^{\oplus m} \setminus K^{\oplus m}$ comes from $R \setminus K$. And as the rule $r$ satisfies the cycle condition, $v$ is the source of an *ijij-cycle* in $R$ and also in $R^{\oplus m} \setminus K^{\oplus m}$.

* If $v$ is a preserved node of $K^{\oplus m}$ and is the source of an *ijij-cycle* in $L^{\oplus m}$, then either:

- If $v$ is source of a *ijij-cycle* in $L$, because the rule $r$ satisfies the cycle condition, $v$ is the source of an *ijij-cycle* in $R$, and so in $R^{\oplus m}$.

- If some of the four arcs come from $L$ and some others have been added by the topological extension step. Then, due to the cycle condition on $r$, the old arcs of $L$ are preserved in $R$, and thus also in $L^{\oplus m}$ and $R^{\oplus m}$. And, due to topological extension, new arcs are also preserved in $L^{\oplus m}$, $K^{\oplus m}$ and $R^{\oplus m}$. Thus, in this case, the preserved node $v$ of $K^{\oplus m}$ is the source of an *ijij-cycle* in $L^{\oplus m}$, and is also the source of an *ijij-cycle* in $R^{\oplus m}$.

- If the four arcs are added by the topological extension step. Then, as previously, these new arcs are preserved in $L^{\oplus m}$, $K^{\oplus m}$ and $R^{\oplus m}$. And thus the preserved node $v$ of $K^{\oplus m}$ is the source of an *ijij-cycle* in $L^{\oplus m}$, and is also the source of an *ijij-cycle* in $R^{\oplus m}$.

* Finally, if $v$ is a preserved node of $K^{\oplus m}$ and is not the source of an *ijij-cycle* in $L^{\oplus m}$, then, as previously, the *i-arc* and the *j-arc* of source $v$ can be either old arcs from $r$, or new arcs added during topological extension step. In both cases, these arcs are preserved in $R^{\oplus m}$, respectively due to cycle condition of $r$ and topological extension. Consequently, the *i-arc* and the *j-arc* of source $v$ are preserved in $R^{\oplus m}$.

Thus, $r^{\oplus m}$ satisfies the cycle condition.

Consequently, $r^{\oplus m}$ satisfies the conditions of topological consistency preservation of Theorem 1. ◀

This result can directly be extended to the whole rule instantiation.

**Theorem 3 (Topological consistency preservation of instantiation).** Let $r: L \leftrightarrow K \leftrightarrow R$ be a rule scheme on a user signature $\Omega_\pi$, and $m: L_\alpha \to G$ a kernel match morphism on a $\pi$-embedded $G$-map $G$.

If $r$ satisfies the conditions of topological consistency preservation of theorem 1, then the instantiated rule $r^m = ((r^{mv})^{\oplus m})^{\odot \pi}$, if it exists, also satisfies these conditions.

► **Proof.** As $r^{mv}$ has the same topological structure as $r$, $r^{mv}$ satisfies the conditions of topological consistency preservation. Then, according to Lemma 1, $(r^{mv})^{\oplus m}$ also does. Finally, as the embedding propagation preserves the topological structure, $((r^{mv})^{\oplus m})^{\odot \pi}$ satisfies these conditions. ◀

## 8.2. Case of overlap

Before we study the embedding consistency preservation, we mention a risk occurring with topological extension: the overlap of embedding orbits. By allowing a minimal match of the transformed embeddings that relies on the automatic completion of transformed embedding orbits, we are exposed to unexpected merges of different embedding orbits. Let us consider the face stretching defined by the rule scheme of Figure 38.
<figure><img src="image_54.png" /><figcaption>Figure 38: Face stretching rule scheme</figcaption></figure>

The operation consists in matching two edges to translate their vertices in the two opposed directions $\vec{v}$ and $-\vec{v}$. When the rule scheme is correctly applied to the square face, the extended rule of Figure 39 contains four vertices in $R$ respectively embedded by $B' = B - \vec{v}$, $D' = D - \vec{v}$, $C' = C + \vec{v}$ and $E' = E + \vec{v}$.

<figure><img src="image_55.png" /><figcaption>Figure 39: Consistent face streching</figcaption></figure>

However, when the rule is applied to the triangle face, the extended rule of Figure 40 is inconsistent as the top vertex ends up embedded in $R$ with two different values $A' = A - \vec{v}$ and $A'' = A + \vec{v}$. This is a clear case of misapplication as we wanted to match and translate four vertices but only match three. We call an overlap such a situation where different embedding orbits manipulated in the rule end up merged in the extended rule and we define a condition on the kernel morphism that prevent it. This condition can be seen as an extension of the injective condition on the match morphism to the embedding orbits.

<figure><img src="image_56.png" /><figcaption>Figure 40: Inconsistent face streching</figcaption></figure>
**Lemma 2 (Non-overlap).** Let $r: L \leftrightarrow K \hookrightarrow R$ be a rule embedded on $\pi: \langle o \rangle \to \tau$ and $m: L_\alpha \to G$ a kernel match morphism on a $\pi$-embedded $G$-map $G$.

We say that the topological extension of $r$ along $m$ produces an overlap if for $v$ and $w$ two nodes of $L$ (resp. $K$, $R$) such that $v \not\equiv_{L\langle o \rangle} w$ (resp. $v \not\equiv_{K\langle o \rangle} w$, $v \not\equiv_{R\langle o \rangle} w$) then $v \equiv_{L \oplus^m \langle o \rangle} w$ (resp. $v \equiv_{K \oplus^m \langle o \rangle} w$, $v \equiv_{R \oplus^m \langle o \rangle} w$).

The topological extension of $r$ along $m$ does not produce overlap if $m$ satisfies the following condition of non-overlap: for two nodes $v$ and $w$ of $L$ such as $v \not\equiv_{L\langle o \rangle} w$, $m(v) \not\equiv_{G\langle o \rangle} m(w)$.

**Proof.** Let us show that $L^{\oplus m}$ does not contain overlap. Let us suppose that there exist $v$ and $w$ two nodes of $L$ such that $v \not\equiv_{L\langle o \rangle} w$ and $v \equiv_{L \oplus^m \langle o \rangle} w$. Then, the overlap comes from the topological extension, i.e the node images $m(v)$ and $m(w)$ belong to the same orbit in $G$, $m(v) \equiv_{G\langle o \rangle} m(w)$. This is contrary to the condition of non-overlap. The proof is similar for $K^{\oplus m}$ and $R^{\oplus m}$. ◀

## 8.3. Embedding consistency preservation

We now study how the non-overlap condition combined with the conditions of embedding consistency preservations on evaluated rule schemes ensure that the instantiated rules satisfy the conditions of embedding consistency preservation on rules given in Theorem 2. In particular, we will release the condition of full match of transformed embeddings as it was the goal of the automatic orbit completion of transformed embeddings.

We start with the topological extension step. Note that as the nodes added by the topological extension are not labeled, the extended rule is only expected to satisfy a weak version of the full match of transformed embeddings of Theorem 2 that does not require a total labelling of the orbit.

**Lemma 3 (Embedding consistency preservation of topological extension).** Let $r: L \leftrightarrow K \to R$ be a rule embedded on $\pi: \langle o \rangle \to \tau$ and $m: L_\alpha \to G$ a kernel match morphism on a $\pi$-embedded $G$-map $G$.

If $r$ satisfies the conditions of topological consistency preservation of Theorem 1, the conditions of embedding consistency and of labeling of extended embedding orbits of Theorem 2, and if $m$ satisfies the condition of non-overlap of Lemma 2, then the topological extended rule $r^{\oplus m}: L^{\oplus m} \leftrightarrow K^{\oplus m} \to R^{\oplus m}$ satisfies the following conditions:

* Embedding consistency of Theorem 2: $L$, $K$ and $R$ satisfy the embedding consistency constraint of Definition 5.

* Weak full match of transformed embeddings: if a preserved node $v$ has a transformed embedding, then $R^{\oplus m}\langle o \rangle(v)$ is a full orbit; i.e. if $v$ is a node of $K^{\oplus m}$ such that $\pi_{L^{\oplus m}}(v) \neq \pi_{R^{\oplus m}}(v)$, then every node of $R^{\oplus m}\langle o \rangle(v)$ is the source of exactly one $i$-arc for each $i$ of $\langle o \rangle$.

* Labeling of extended embedding orbits of Theorem 2: if $v$ is a node of $K$ and there exists a node $w$ in $R\langle o \rangle(v)$ such that $w$ is not in $L\langle o \rangle(v)$, then there exist $v'$ in $K$ with $v' \equiv_{L\langle o \rangle} v$ and $v' \equiv_{R\langle o \rangle} w$ such that $\pi_L(v') \neq \bot$. ◀

**Proof.** Let us show that the three conditions of the Lemma 3 hold.

**Embedding consistency** Let $v$ and $w$ be two nodes of $L^{\oplus m}$ such that $v \equiv_{L^{\oplus m}\langle o \rangle} w$, $\pi_{L^{\oplus m}}(v) \neq \bot$ and $\pi_{L^{\oplus m}}(w) \neq \bot$. Because of the condition of non-overlap, $v$ and $w$ are two nodes of $L$ such that $v \equiv_{L\langle o \rangle} w$. As $L$ satisfies the embedding consistency constraint, $\pi_L(v) = \pi_L(w)$ and therefore $\pi_{L^{\oplus m}}(v) = \pi_{L^{\oplus m}}(w)$. The proof is the same for $K$ and $R$. $r^{\oplus m}$ satisfies the embedding consistency condition.

### Weak full match of transformed embedding.

Let $v$ be a node of $R^{\oplus m}$. If $v$ is a preserved node of $K^{\oplus m}$ or an added node of $R^{\oplus m}$, thanks to topological extension step, $R^{\oplus m}\langle o \rangle(v)$ is a complete orbit. Thus $v$ is the source of exactly one $i$-arc for each $i$ of $\langle o \rangle$. Then $r^{\oplus m}$ satisfies the weak full match of transformed embedding.
**Labeling of extended embedding orbits.** Let $v$ be a node of $K^{\oplus m}$ and $w$ a node $R^{\oplus m}\langle o \rangle(v)$ such that $w$ is not in $L^{\oplus m}\langle o \rangle(v)$. Because the topological extension definition, $w$ is a node of $r$. As $r$ satisfies the labeling of extended embedding orbits, there exist $v'$ in $K$ with $v' \equiv_{L\langle o \rangle} v$ and $v' \equiv_{R\langle o \rangle} v$ such that $\pi_L(v') \neq \perp$. Moreover, because of the topological extension definition, $v' \equiv_{L^{\oplus m}\langle o \rangle} v$, $v' \equiv_{R^{\oplus m}\langle o \rangle} v$, and $\pi_{L^{\oplus m}}(v') \neq \perp$. Therefore, $r^{\oplus m}$ satisfies the labeling of extended embedding orbits. ◀

Let us now show that the embedding propagation step restores the original strong embedding consistency conditions.

**Lemma 4 (Embedding consistency preservation of the embedding propagation).** Let $r: L \hookleftarrow K \hookrightarrow R$ be a rule embedded on $\pi: \langle o \rangle \to \tau$ and $m: L_\alpha \to G$ a kernel match morphism on a $\pi$-embedded $G$-map $G$.

If $r$ satisfies the conditions of topological consistency preservation of Theorem 1 and the conditions of Lemma 3, then the embedding propagated rule $r^{\circ\pi}$ satisfies the conditions of topological consistency preservation of Theorem 1 and the conditions of embedding consistency preservation of Theorem 2.

**Proof.** As previously said, the embedding propagation step does not modify the topological structure, thus this last step preserves the topological consistency conditions of Theorem 1.

In the same way, the conditions of embedding consistency preservation and of labeling of extended embedding orbits are preserved.

Moreover, the $\pi$-embedding propagation step propagates each embedding label along the full $\langle o \rangle$-orbit, the weak condition of full match of transformed embed becomes total as all nodes are become labeled. ◀

Finally, we can extend this result to the whole rule instantiation and show that it always exists if the following conditions of embedding consistency preservation are satisfied.

**Theorem 4 (Embedding consistency preservation of instantiation).** Let $r: L \hookleftarrow K \hookrightarrow R$ be a rule scheme on a user signature $\Omega_\pi$ and $m: L_\alpha \to G$ be a kernel match morphism on a $\pi$-embedded $G$-map $G$.

The instantiated rule $((r^{mv})^{\oplus m})^{\circ\pi}$ exists and satisfies the conditions of embedding consistency preservation of Theorem 2 if the following conditions are satisfied:

* $r$ satisfies the condition of embedding consistency of Theorem 2;

* $r$ satisfies the condition of labeling of extended embedding orbits of Theorem 2;

* $m$ satisfies the condition of non-overlap of Lemma 2.

**Proof.** As equal terms are evaluated by equal values, if $r$ satisfies the previous conditions, so does the evaluated rule $r^{mv}$. Then, the extended rule $(r^{mv})^{\oplus m}$ satisfies the condition of Lemma 3, including embedding consistency. Therefore, the propagation $((r^{mv})^{\oplus m})^{\circ\pi}$ exists. Finally, according to Lemma 4, the instantiated rule $((r^{mv})^{\oplus m})^{\circ\pi}$ satisfies the conditions of embedding consistency preservation. ◀

Let us note that the properties of Theorem 4 are sufficient but not necessary to ensure the embedding consistency preservation. In practice, it may be useful to relax the embedding consistency condition if several terms can have the same evaluation. For example, algebraic properties of user-defined functions on embeddings could be taken into account.

## 9. Applications

As presented in the introduction, the manipulation of geometric information is at the heart of geometric modelers. Rule schemes with embedding terms allow a major part of geometric operations to be defined, as this section will illustrate. After some basic rule scheme examples, a physical simulation application will be presented with its implementation in a dedicated software tool set.
<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>

<figure><img src="image_59.png" /><figcaption>Figure 41: To modify one embedding</figcaption></figure>

## 9.1. Basic examples

Many usual geometric operations can be specified by rule schemes, using embedding expressions and node variables. The most basic ones are simple modifications of one embedding (see Figure 41). Thanks to the topological extension (see section 7.2), matching one node is enough as the instantiation ensures that all nodes of the embedded orbit are relabeled. For example, Figure 41(a) defines the translation of a vertex position by a given vector; Figure 41(b) defines the coloring of a face in red; Figure 41(c) defines the coloring of a face by the color of its neighboring face due to the $\alpha_2$ operator (see section 6.1).

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /><figcaption>Figure 42: Edge sewing</figcaption></figure>

But these embedding modifications can also be combined with topological transformations of a fixed pattern. For example, the rule scheme of Figure 42 allows one to sew two faces along free edges and to position the merged edge in the middle of the two previous edge positions. More generally, the introduced rule schemes can therefore address any modeling operation as long as this operation concerns the transformations of a fixed topological pattern.

<figure><img src="image_62.png" /></figure>

<figure><img src="image_63.png" /><figcaption>Figure 43: Triangle enlargement</figcaption></figure>

For example, we can easily define usual operations on regular mesh processing. The enlargement of a triangle in mesh can be defined by the rule scheme of Figure 43. This enlargement is carried out by translating every vertex position of the triangle by the vector computed with the `vec` user-operator between the two following positions: the triangle barycenter ($bary(pos_{<01>}(a))$, see Subsection 6.2) and the vertex position itself (e.g. $a.pos$). Therefore, all vertex positions are translated in a way that put them farther from the triangle center.

We shall now take another example of triangular mesh processing, with the triangular flip-flap operation [48] in Figure 44. This operation is useful to transform two flat triangles into more equilateral
<figure><img src="image_64.png" /><figcaption>Figure 44: Triangular flip-flap</figcaption></figure>

ones, in order to increase the mesh shape regularity and therefore the quality of simulations. It should be noted that the rule scheme does not modify the vertex positions. However, as the vertex orbits incident to nodes *a* and *k* are extended with nodes *m*, *n*, *o* and *p*, the corresponding positions must be redefined at least once per extended vertex orbit (see the condition of labeling of extended embedding orbits of Theorem 4).

<figure><img src="image_65.png" /><figcaption>Figure 45: Loop subdivision</figcaption></figure>

A more elaborate example of mesh processing is the loop subdivision of Figure 45 [49]. As this subdivision consists in splitting the three edges of the triangle, the rule scheme has to match both the triangle and its three adjacent edges in order to preserve the topological coherence. On the embedding aspect, the positions of the new vertices are defined as the center of the split edges, while none of the three positions of the original face are modified. While this rule scheme allows the first triangle to be subdivided, it cannot be used to subdivide the neighbor face, as this face would then have four vertices as a result of the first subdivision. Consequently, a new rule scheme is necessary to subdivide this second face. However, to be correctly applied, this second rule scheme would require additional information (i.e. an additional embedding) to distinguish the three original vertices from the added one.

## 9.2. An application to physical simulation

In [50], we proposed a physical simulator based on the mass/spring systems of [51] in which all operations are defined with the introduced rule language. Figure 46(a) presents a first intuitive representation of this model: vertices represent particles and stretching springs are associated to edges.

<figure><img src="image_66.png" /><figcaption>Figure 46: Stretch springs</figcaption></figure>
As any realistic modeling application, this simulator requires multiples embeddings. Each node must therefore carry the particle properties (its position pos, its mass m, and its cumulated force F) and the stretching spring properties (its stiffness k and its rest-length $l_0$). In [13], we addressed the case of multiple embeddings by introducing a category of partially I-labeled graphs that handle multiple node labels as an extension of the category defined in [14]. In this category, each type of embedding (node label) is defined by its own node labeling function, which is defined on its own orbit type. We extended graph transformations in this category so rules could simultaneously transform multiple embeddings. For example, the rule scheme of Figure 46(b) computes the forces corresponding to a given stretching spring (edge), by using a user-defined operator *sprF* on the two corresponding particle data (pos and m) and the spring properties (k and $l_0$). The final cumulated forces of particles are obtained when this rule scheme has been applied to all springs (all edges).

<figure><img src="image_67.png" /><figcaption>Figure 47: Shear springs</figcaption></figure>

To preserve the shape of faces, shear springs, as represented in Figure 47, are generally added. In the case of initially rectangular faces (when diagonals have equal length) with an isotropic material, the two shear springs are equal and we can save only one set of parameters for the two springs associated to the face. Therefore, in the rule scheme of Figure 47(b), the computation of the forces corresponding to a pair of shear springs directly matches a whole face. In the other case (when the initial face is not regular), or when the material is anisotropic, two set of parameters are required and are associated with the two face corners (orbit $\langle 1 \rangle$). Consequently, in the rule scheme of Figure 47(c), the computing of a shear spring only matches half a face (i.e. two opposite corners at a time).

<figure><img src="image_68.png" /><figcaption>Figure 48: Bending springs</figcaption></figure>

Finally, linear bending springs can also be added to control bending. As represented in Figure 48(a), they connect second-neighbor vertices in order to control the angle between two edges, and therefore the corresponding rule scheme of Figure 48(b) matches three vertices. In this case, the chosen orbit to carry the string data are the orbits $\langle 2 \rangle$ as their number matches with the number of linear bending springs.
### 9.3. Jerboa and related applications

The presented language and the associated syntactic conditions are at the heart of Jerboa [33, 34, 52], a tool set for designing and generating a safe geometric modeler kernel. As Jerboa aims at allowing the generation of any modeler, it addresses a large class of modeling operations.

Creating a modeler with Jerboa can basically be achieved in two steps:

* The first one consists in specifying the manipulated object by providing its topological dimension and embedding (which data type will be attached to which orbits). Note that the modeler designer has to provide any external library required to handle the embedding data types (e.g. 3D coordinate, RGB color) and their associated computational functions (e.g. barycenter of a set of points, mix of two colors).

* The second step is the design of rule schemes defining the modeling operations. The syntactic analyzer included in the graphic rule editor automatically checks the conditions given in this article and guides the user through modeling operations design by indicating which parts of the rule are inconsistent.

Once designed, a modeler can be generated and used right away thanks to a default generic viewer provided by Jerboa. But this modeler kernel can also be integrated into larger tools. Most importantly, end-users are not required to understand the rule language: indeed, they will only use modeling operations by interactively applying them on the object under construction.

<figure><img src="image_69.png" /><figcaption>Figure 49: Mass/spring simulation in 2D.</figcaption></figure>

Jerboa has been used to develop several geometric modelers, such as one geology modeling tool [53], and the simulation using mass/spring model presented in section 9.2. The previously described rule schemes have been implemented in 2D (see Figure 49) and adapted in 3D (see Figure 50). They have been applied on several objects: with rectangular cells in Figure 49(a), with triangular cells in Figure 49(b), with mixed ones in Figure 49(c), on cuboids with 64 elements in Figure 50(a), and on a liver model with 597 elements in Figure 50(b). Simulation of more complex objects is possible and the degree of accuracy of the results is equivalent to other approaches.

<figure><img src="image_70.png" /><figcaption>Figure 50: Mass/spring simulation in 3D.</figcaption></figure>
## 10. Conclusion

In this article, we introduced a new kind of graph transformation variables, called node variables and inspired from the attribute variables of [15], and dedicated to embedding computations in the context of topology-based geometric modeling. Benefiting from the regularity of G-map topological structures, these node variables are provided with operators that allow both to access the existing embedding (node labels in the transformed object), therefore avoiding any additional identifier naming for variable. Operators are also allowed to traverse the topological structure (neighboring nodes in the transformed object) without having to match the precise configuration below the matched pattern (e.g. in the face triangulation case, a mix with the neighboring face colors can be defined whether these faces exist or not). A rule instantiation mechanism is also provided to propagate the embedding modifications to the concern orbits of the object. This mechanism allows to modify the labels of nodes located beyond the rule pattern without having to explicitly match all of them (e.g. in the edge removal case, the merged face color can be defined without having to match the whole structure, therefore allowing a generic definition of the operation limited to the edge). The resulting language is generic enough to define any usual embedding transformation, and it is fitted with syntactic conditions that allow an operation implemented as a rule to be statically checked. A single rule application engine may thus be programmed to handle any operation.

Our further work will consist in enhancing the language with new possibilities, while still providing a safe theoretical ground. In particular, we still have to show under which syntactic conditions node variables can be simultaneously used with the orbit variables dedicated to topological transformations in order to define operations independently from both embedding value and topological shape (e.g. the triangulation of any sized face of any color). Furthermore, we wish to provide rule scripts in order to compute complex modeling operations, as the boolean operators allowing to combine objects together by intersection, difference or union. Such operations require to search the object and selectively apply rules, following a given strategy. A script language would allow to define these strategies by providing operators such as iterators, loops or conditionals.

## References

[1] L. Baresi, R. Heckel, Tutorial introduction to graph transformation: A software engineering perspective, in: H. Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg (Eds.), Graph Transformations: Second International Conference, ICGT 2004, Rome, Italy, September 28–October 1, 2004. Proceedings, Vol. 3256 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 431–433.

[2] H. Ehrig, H.-J. Kreowski, U. Montanari, G. Rozenberg (Eds.), Handbook of Graph Grammars and Computing by Graph Transformation: Concurrency, Parallelism, and Distribution, Vol. 3 of Concurrency, Parallelism, and Distribution, World Scientific, 1999.

[3] G. Taentzer, AGG: A graph transformation environment for modeling and validation of software, in: J. L. Pfaltz, M. B. B. Nagl (Eds.), Applications of Graph Transformations with Industrial Relevance: Second International Workshop, AGTIVE 2003, Charlottesville, VA, USA, September 27 - October 1, 2003, Revised Selected and Invited Papers, Vol. 3062 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 446–453.

[4] J. Paredaens, D. V. Gucht, J. Van den Bussche, M. Gyssens, A graph-oriented object database model, IEEE Transactions on Knowledge and Data Engineering 6 (1994) 572–586.

[5] G. Damiand, P. Lienhardt, Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing, A K Peters/CRC Press, 2014.

[6] M. Poudret, A. Arnould, J.-P. Comet, P. Le Gall, Graph Transformation for Topology Modelling., in: 4th International Conference on Graph Transformation (ICGT’08), Vol. 5214 of Lecture Notes in Computer Science, Springer, Leicester, United Kingdom, 2008, pp. 147–161.
[7] A. Spicher, O. J. Michel, J.-L. Giavitto, Declarative mesh subdivision using topological rewriting in MGS, in: 5th International Conference on Graph Transformations (ICGT 2010), Vol. 6372 of Lecture Notes in Computer Science, Enschede, Netherlands, 2010, pp. 298–313.

[8] C. Smith, P. Prusinkiewicz, F. Samavati, Local specification of surface subdivision algorithms, in: J. L. Pfaltz, M. Nagl, B. Böhlen (Eds.), Applications of Graph Transformations with Industrial Relevance: Second International Workshop, AGTIVE 2003, Vol. 3062 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Charlottesville, VA, USA, 2004, pp. 313–327, revised Selected and Invited Papers.

[9] P. Lienhardt, Topological models for boundary representation: a comparison with n-dimensional generalized maps, Computer-Aided Design 23 (1) (1991) 59 – 82.

[10] P. Lienhardt, N-dimensional generalised combinatorial maps and cellular quasimanifolds, International Journal of Computational Geometry and Applications 04 (03) (1994) 275–324.

[11] M. Poudret, J.-P. Comet, P. Le Gall, A. Arnould, P. Meseure, Topology-based Geometric Modelling for Biological Cellular Processes, in: International Conference on Language and Automata Theory and Applications, Tarragone, Spain, 2007, pp. 497–508.

[12] M. Poudret, Transformations de graphes pour les opérations topologiques en modélisation géométrique - Application à l'étude de la dynamique de l'appareil de Golgi, Theses, Université d'Evry-Val d'Essonne (Oct. 2009).

[13] T. Bellet, A. Arnould, P. Le Gall, Rule-based transformations for geometric modeling, in: 6th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2011), Part of ETAPS 2011, Saarbrücken, Germany, 2011, p. 20p.

[14] A. Habel, D. Plump, Relabelling in graph transformation, in: Proceedings of the First International Conference on Graph Transformation, ICGT '02, Springer-Verlag, London, UK, UK, 2002, pp. 135–147.

[15] B. Hoffmann, Graph transformation with variables, in: H.-J. Kreowski, U. Montanari, F. Orejas, G. Rozenberg, G. Taentzer (Eds.), Formal Methods in Software and Systems Modeling: Essays Dedicated to Hartmut Ehrig on the Occasion of His 60th Birthday, Vol. 3393 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2005, pp. 101–115.

[16] B. B. Mandelbrot, Fractals: Form, chance, and dimension, W. H. Freeman, 1977.

[17] P. Prusinkiewicz, A. Lindenmayer, The algorithmic beauty of plants (The Virtual Laboratory), Springer-Verlag, 1990.

[18] P. Prusinkiewicz, M. S. Hammel, E. Mjolsness, Animation of plant development, in: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '93, ACM, New York, NY, USA, 1993, pp. 351–360.

[19] R. Měch, P. Prusinkiewicz, Visual models of plants interacting with their environment, in: Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '96, ACM, New York, NY, USA, 1996, pp. 397–410.

[20] A. Peyrat, O. Terraz, S. Mérillou, E. Galin, Generating vast varieties of realistic leaves with parametric 2Gmap L-systems, in: Computer Graphics International 2008, Vol. 24 of The Visual Computer, Springer Berlin / Heidelberg, Istanbul, Turkey, 2008, pp. 807–816.

[21] O. Petrenko, R. J. G. Hernández, M. Sbert, O. Terraz, D. Ghazanfarpour, Flower modelling using natural interface and 3gmap l-systems, in: Proceedings of the 12th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry, VRCAI '13, ACM, New York, NY, USA, 2013, pp. 101–108.
[22] E. Bohl, O. Terraz, D. Ghazanfarpour, Modeling Fruits and Their Internal Structure Using Parametric 3Gmap L-systems, Vis. Comput. 31 (6-8) (2015) 819-829.

[23] P. Wonka, M. Wimmer, F. Sillion, W. Ribarsky, Instant architecture, ACM Trans. Graph. 22 (3) (2003) 669-677.

[24] P. Müller, P. Wonka, S. Haegler, A. Ulmer, L. Van Gool, Procedural modeling of buildings, in: ACM SIGGRAPH 2006 Papers, SIGGRAPH '06, ACM, New York, NY, USA, 2006, pp. 614–623.

[25] C. A. Vanegas, D. G. Aliaga, B. Benes, Building reconstruction using Manhattan-world grammars, in: Computer Vision and Pattern Recognition (CVPR), IEEE, 2010, pp. 358–365.

[26] Y. I. H. Parish, P. Müller, Procedural modeling of cities, in: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '01, ACM, New York, NY, USA, 2001, pp. 301–308.

[27] H. Ehrig, K. Ehrig, U. Prange, G. Taentzer, Fundamentals of Algebraic Graph Transformation, Monographs in Theoretical Computer Science. An EATCS Series, Springer, 2006.

[28] K. C. You, K.-S. Fu, A syntactic approach to shape recognition using attributed grammars, IEEE transactions on systems, man, and cybernetics 9 (6) (1979) 334–345.

[29] W.-H. Tsai, K.-S. Fu, Attributed grammar-a tool for combining syntactic and statistical approaches to pattern recognition, IEEE Transactions on Systems, Man, and Cybernetics 10 (12) (1980) 873–885.

[30] F. Rosselló, G. Valiente, Graph transformation in molecular biology, in: Formal Methods in Software and Systems Modeling, Springer, 2005, pp. 116–133.

[31] M. L. Blinov, J. Yang, J. R. Faeder, W. S. Hlavacek, Graph theory for rule-based modeling of biochemical networks, in: Transactions on Computational Systems Biology VII, Springer, 2006, pp. 89–106.

[32] V. Danos, J. Feret, W. Fontana, R. Harmer, J. Hayman, J. Krivine, C. Thompson-Walsh, G. Winskel, Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models, in: D. D'Souza, T. Kavitha, J. Radhakrishnan (Eds.), IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), Vol. 18 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2012, pp. 276–288.

[33] T. Bellet, M. Poudret, A. Arnould, L. Fuchs, P. Le Gall, Designing a topological modeler kernel: a rule-based approach, in: Shape Modeling International Conference (SMI), IEEE, 2010, pp. 100–112.

[34] H. Belhaouari, A. Arnould, P. Le Gall, T. Bellet, JERBOA: A graph transformation library for topology-based geometric modeling, in: 7th International Conference on Graph Transformation (ICGT 2014), Vol. 8571 of Lecture Notes in Computer Science, Springer, York, UK, 2014, pp. 269–284.

[35] H. Ehrig, Introduction to the algebraic theory of graph grammars (a survey), in: International Workshop on Graph Grammars and Their Application to Computer Science, Vol. 73 of Lecture Notes in Computer Science, Springer, 1978, pp. 1–69.

[36] A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, M. Löwe, Handbook of Graph Grammars and Computing by Graph Transformation, World Scientific, 1997, Ch. Algebraic Approaches to Graph Transformation. Part I: Basic Concepts and Double Pushout Approach, pp. 163–245.

[37] B. Hoffmann, E. Jakumeit, R. Geiß, Graph rewrite rules with structural recursion, in: M. Mosbah, A. Habel (Eds.), 2nd Intl. Workshop on Graph Computational Models (GCM 2008), 2008, pp. 5–16.
[38] F. Orejas, L. Lambers, Symbolic attributed graphs for attributed graph transformation, Electronic Communications of the EASST 30, Graph Computation Models 2010.

[39] F. Orejas, L. Lambers, Lazy graph transformation, Fundamenta Informaticae 118 (1-2) (2012) 65–96.

[40] F. Drewes, B. Hoffmann, D. Plump, Hierarchical graph transformation, Journal of Computer and System Sciences 64 (2) (2002) 249–283.

[41] B. Hoffmann, More on graph rewriting with contextual refinement, in: R. Echahed, A. Habel, M. Mosbah (Eds.), Graph Computation Models Selected Revised Papers from GCM 2014, Vol. 71 of Electronic Communications of the EASST, 2015.

[42] A. Habel, Hyperedge replacement: grammars and languages, Vol. 643 of Lecture Notes in Computer Science, Springer, 1992.

[43] A. Habel, H. Radke, Expressiveness of graph conditions with variables, Electronic Communications of the EASST 30, Graph and Model Transformation 2010.

[44] V. Lang, P. Lienhardt, Simplicial Sets and Triangular Patches, in: Proceedings of the 1996 Conference on Computer Graphics International, CGI '96, IEEE, 1996, p. 154.

[45] M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, USA, 1988.

[46] K. Weiler, The radial edge structure: A topological representation for non-manifold geometric boundary modeling, in: Geometric Modeling for CAD Applications: Selected Papers from IFIP WG 5.2, Elsevier Science, 1988, pp. 3–36.

[47] F. Ledoux, A. Arnould, P. L. Gall, Y. Bertrand, Geometric Modelling with CASL, in: Selected Papers from the 15th International Workshop on Recent Trends in Algebraic Development Techniques, Vol. 2267 of Lecture Notes in Computer Science, Springer-Verlag, London, UK, UK, 2001, pp. 176–200.

[48] C. Paulus, L. Untereiner, H. Courtecuisse, S. Cotin, D. Cazier, Virtual Cutting of Deformable Objects based on Efficient Topological Operations, Visual Computer 31 (6-8) (2015) 831–841.

[49] C. T. Loop, Smooth subdivision surfaces based on triangles, Master's thesis, Department of Mathematics, The University of Utah, master of Science (aug 1987).

[50] F. Ben Salah, H. Belhaouari, A. Arnould, P. Meseure, A general physical-topological framework using rule-based language for physical simulation, in: 12th International Conference on Computer Graphics Theory and Applications, Porto, Portugal, 2017, to appear.

[51] X. Provot, Deformation constraints in a mass-spring model to describe rigid cloth behaviour, in: Proceedings of Graphics Interface '95, Canadian Human-Computer Communications Society, Toronto, Ontario, Canada, 1995, pp. 147–154.

[52] Jerboa, a rule-based topological modeler generator, http://xlim-sic.labo.univ-poitiers.fr/jerboa/, XLim (CNRS, Université de Poitiers) and MICS (CentrapeSupélec).

[53] V. Gauthier, A. Arnould, H. Belhaouari, S. Horna, M. Perrin, M. Poudret, J.-F. Rainaud, A topological approach for automated unstructured meshing of complex reservoir, in: ECMOR XV - 15th European Conference on the Mathematics of Oil Recovery, EAGE, Amsterdam, Netherlands, 2016.