
i
i

“A10-1659” — 2023/4/25 — 13:12 — page 337 — #1 i
i

i
i

i
i

in Computational and 
Applied Mathematics

Trends Trends in Computational and Applied Mathematics, 24, N. 2 (2023), 337-356
Sociedade Brasileira de Matemática Aplicada e Computacional
Online version ISSN 2676-0029
www.scielo.br/tcam
doi: 10.5540/tcam.2023.024.02.00337

Stable Bi-Maps on Surfaces and Their Graphs

C. MENDES DE JESUS1, E. BOIZAN BATISTA2 and J. C. F. COSTA3*

Received on December 20, 2021 / Accepted on October 4, 2022

ABSTRACT. In this paper we study stable bi-maps F = ( f1, f2) : M → R×R2 from a global viewpoint,
where M is a smooth closed orientable surface and f1 : M →R, f2 : M →R2 are stable maps. We associate a
graph to F , so-called RM -graph and study its properties. The RM -graph captures more information about
the topological structure of M than other graphs that appear in literature. Moreover, some graph realization
theorems are obtained.

Keywords: Stable maps, RM -graphs, closed surfaces.

1 INTRODUCTION

The graph theory has been increasingly used to solve various real-world problems, beyond, of
course, the Mathematics problems. The graph theory has applications in Optimization (logistic
and transportation problems), Organic Chemistry, Physics (statistical mechanics and solid state
Physics), Electrical Engineering (communication network and Coding theory), among others. We
can find a wide scope of these applications in the references [5, 14]. Some recent applications of
graph theory include genome sequencing, starlight interferometer program and DNA sequence.
The special class of bipartite graphs that will appear in this paper has many interesting and even
surprising applications (see for instance [16]).

In Singularity theory, many works resort to graph theory to describe local/global invariants and
combinatorial models to investigate the recognition and classification problem involving maps
or map germs. The authors themselves of this paper have some works in this direction (see,
for instance, [3, 8]). It is important to highlight that the Singularity theory has many practical
applications in Physics, Engineering, Thermodynamic, among others.

*Corresponding author: João Carlos Ferreira Costa – E-mail: joao.costa@unesp.br
1Departamento de Matemática, Universidade Federal de Juiz de Fora, Via Local, 880, São Pedro, 36036-900, Juiz de
Fora, MG, Brazil – E-mail: cmendesjesus@ufjf.br http://orcid.org/0000-0002-1050-2712
2Centro de Ciências e Tecnologia, Universidade Federal do Cariri, 63048-080, Juazeiro do Norte, CE, Brazil – E-mail:
erica.batista@ufca.edu.br https://orcid.org/0000-0003-0125-9949
3Departamento de Matemática, Universidade Estadual Paulista (UNESP), 15054-000, São José do Rio Preto, SP, Brazil
– E-mail: joao.costa@unesp.br https://orcid.org/0000-0002-0428-4640


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 338 — #2 i
i

i
i

i
i

338 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

In this work, we resort graphs to study stable bi-maps F = ( f1, f2) defined on a smooth closed
orientable surface M ⊂ R3. Stable bi-maps means a pair of stable maps, i.e., f1 : M → R and
f2 : M → R2 are stable maps. Stable maps have been investigated by several authors and have
many interesting applications (see, for instance, [3, 4, 8, 11, 13, 18]).

Let us describe the stable bi-maps as above and to show how to associate the graph theory to
investigate it.

Denote by C∞(M,Rp) the set of all C∞ maps from M to Rp, p = 1,2.

Firstly, consider a stable map f1 : M → R. For this type of map, it is known that the Reeb graph
is a global topological invariant associated to f1 (cf. [5,15]). The Reeb graph describes the topol-
ogy of the surface M. Reeb graphs appear with many applications in Computational Geometry,
Computer Graphics, Engineering, Applied Mathematics, etc. We will denote the Reeb graph as-
sociated to a stable map f1 : M →R by R-graph of f1. The Figure 1 shows a practical application
of R-graphs on the study of human body shape and posture using 3D images (cf. [17]).

Notice that in Figure 1 (4), we have two distinct body shapes represented by the same R-graph,
(c) and (f). Since R-graphs do not distinguish these two body shapes, this kind of problem
motivates us to introduce a new graph which encodes information that just the R-graph does not
encode.

This new invariant is constructed as follows. We consider a stable map of type f2 : M →R2. From
Whitney theorem (cf. [18]), the singular set of f2 (denoted by Σ f2 ⊂ M) consists of curves of
double points, possibly containing isolated cusp points. The apparent contour of f2 (i.e., f2(Σ f2)

the image of the singular set) consists of a number of immersed curves in R2 (possibly with cusps)
whose self-intersections are all transverse and disjoint from the cusps (if any). The singular and
regular components in M codify relevant information about the stable map f2. In fact, in [8]
graphs with weights on the vertices were introduced as a global topological invariant for stable
maps of type f2 : M → R2. These weighted graphs describe the position of the singular and the
regular sets of f2 in M. Its edges, vertices and weights corresponding to the singular components,
regular components and the genus of the regular components of M, respectively. We will denote
the weighted graph associated to f2 : M → R2 by M -graph of f2.

In Figure 1, if we consider f2 as the projection map of the human body shapes (4-a) and (4-d) on
the (floor) plane, then the M -graphs associated to f2 can be used to distinguish them while the
R-graphs cannot. To illustrate how the M -graphs associated to f2 can distinguish different body
shapes, see Figure 2.

By the other hand, there are situations in the converse sense: we can have the same M -graphs
but the R-graphs are different. See, for instance, the Figure 3, (a) and (b).

Then, it seems natural to consider the pair R-graph and M -graph, instead of considering just
one of them. The pair captures more information about the topological structure of M than only
one of them.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 339 — #3 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 339

Figure 1: R-graphs associated to human body shapes (for details, see [17]). This figure was
extracted from the reference [17], Fig. 2, page 157.

(a)                          (b)                          (c)

Figure 2: M -graphs related to three distinct human body shapes.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 340 — #4 i
i

i
i

i
i

340 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

In this way, the motivation of this work is to consider stable bi-maps of type F = ( f1, f2) :
M → R×R2 and its associated RM -graphs. The RM -graph is exactly the pair formed by
the R-graph associated to f1 and by the M -graph associated to f2. Moreover, we can use the
RM -graphs to investigate the topological structure of the surface M and of the singular set Σ f2.
Previously, we showed a possible application of RM -graphs to study patterns of the human
body. This kind of application is very interesting to Computer Vision. There will certainly be
many other practical applications of such RM -graphs.

The last part of this paper is dedicated to investigate the graph realization problem. This is a very
interesting and difficult problem. Given a graph Γ, in which conditions Γ can be realized as an
RM -graph associated to some bi-stable map F = ( f1, f2) : M →R×R2 ? We answer this ques-
tion in Section 5 for some cases (see Theorems 5.3, 5.4 and 5.5). Recently, many authors have
dedicated themselves to the realization problem of R-graphs associated with Morse functions
or Morse-Bott functions (see, for instance, the works of L.P. Michalak [12], I. Gelbukh [6], N.
Kitazawa [9], among others). The second and third named authors of this paper, have also a re-
cent work about the realization problem of the calls MB-Reeb graphs [2]. The MB-Reeb graphs
are a kind of generalization of the R-graphs and they were introduced in [2] to investigate the
topological classification of circle-valued Morse-Bott functions defined on surfaces.

Some techniques applied here for a M -graph such as surgeries, codimension one transitions,
etc., are based on the references [8, 13].

2 STABLE BI-MAPS

Let M be a closed orientable surface and N = Rp (p = 1,2). Two smooth maps f ,g : M → N are
said to be A -equivalent (or just equivalent) if there are orientation-preserving diffeomorphisms,
k : M → M and l : N → N such that g ◦ k = l ◦ f . A smooth map f : M → N is said to be stable
if all maps sufficiently closed to f (with respect to Whitney C∞-topology) are equivalent to f
(see [7] for more details).

A smooth map F = ( f1, f2) : M → R×R2 is said to be a stable bi-map if each fi, i = 1,2, is a
stable map.

Considering F = ( f1, f2) : M → R×R2 be a stable bi-map notice that we have the following
properties:

a) Since f1 : M → R is stable then f1 is Morse with distinct critical values. That is, every
critical point of f1 is non-degenerate and each critical level curve of f1 has a finite number
of critical points, all distincts.

b) Since f2 : M →R2 is stable then its singular points are only folds and isolated cups. Remind
that a point p ∈ M is a regular point of f2 if the map f2 is a local diffeomorphism around
p. Otherwise, the point p is said to be a singular point. According to Whitney theorem
(cf. [18]), the singularities of any stable map f2 : M −→ R2 are (locally) of fold type
(x,y) 7→ (x,y2) or of cusp type (x,y) 7→ (x3 + yx,y).

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 341 — #5 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 341

c) The set of all singular points of f2, denoted by Σ f2, is called singular set of f2. The singular
set of f2 consists of (finitely many) disjoint embedded closed curves in M. The image of
singular set of f2, i.e., f2(Σ f2), is called the apparent contour of f2. The apparent contour
of f2 is a finite number of immersed closed plane curves with finite number of cups and
finite number of transverse intersections and self-intersections (disjoint from the set of
cups). The regular set of f2, given by M \Σ f2, consists of all regular points of f2. Since
M is a smooth closed orientable surface, the singular set Σ f2 is a finite collection of closed
regular simple curves on M formed by fold points with possible isolated cusp points that
divide M in a set of regular regions.

Let j : M → R3 be an immersion of M in R3 and v⃗ ̸= 0 be any vector in R3. We can decompose
R3 in a direct sum Rv ⊕Pv, where Rv is a parallel line to v⃗ and Pv is a orthogonal plane to v⃗.
Then we can consider two stable projections as following:

1. π1
v : j(M)→ Rv given by the restriction to j(M) of the canonical projection of R3 in Rv.

2. π2
v : j(M)→ Pv given by the restriction to j(M) of the canonical projection of R3 in Pv.

Let h : Rv →R and g : Pv →R2 be diffeomorphisms and consider f1 : M →R and f2 : M →R2

two stable maps. Then we can define the following stable maps using π1
v and π2

v :

f1 = h◦π
1
v ◦ j and f2 = g◦π

2
v ◦ j.

These stable maps f1 and f2 as above defined are called projection to a parallel line to v⃗ and
projection to an orthogonal plane to v⃗, respectively, associated to the immersion j (see Figure
3).

Observe that when f1 is a projection to a parallel line to v⃗ and f2 is a projection to a orthogonal
plane to v⃗, then the pair F = ( f1, f2) is clearly a stable bi-map.

From now one, we will always consider in this paper stable bi-maps F = ( f1, f2) where f1 is a
projection to a parallel line v⃗, f2 is a projection to an orthogonal plane to v⃗ and v⃗ ̸= 0 is a fixed
vector in R3.

Figure 3: Example of stable bi-maps from sphere.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 342 — #6 i
i

i
i

i
i

342 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

The Figure 3 illustrates three different stable bi-maps from sphere S2. Notice that in (a) and (b),
the projections to the orthogonal plane Pv have the same number of connected components of
the singular set, while the projections to Rv have distinct number of singular points. Already in
(b) and (c), the projections to Rv have the same number of singular points while the projections to
Pv have distint numbers of singular curves. In this way, the classsical invariant related to stable
projections to the orthogonal plane Pv do not distinguish (a) and (b) but they distinguish (b) and
(c). By other hand, the classical invariant associated to the projections to the parallel line Rv can
distinguish (a) and (b) but not (b) and (c).

In fact, the classical invariant associated to the projection to Rv (i.e., the stable map f1) was
codified in the literature by the Reeb graph associated to f1. The Reeb graphs were introduced
by Reeb in [15]. Here the Reeb graphs will be denoted by R-graphs. The next Subsection 3.1
will be dedicated to explain the R-graphs.

By other hand, the classical invariant associated to the projection to Pv (i.e., the stable map f2)
was codified in the literature by Hacon-Mendes-Romero in [8], by a graph with weights in the
vertices. Here these graphs will be denoted by M -graphs or Mendes-graphs. The next Subsection
3.2 will be dedicated to explain the M -graphs.

Figure 4: R-graphs and M -graphs corresponding to the Figure 3.

The Figure 4 illustrates the respectives R-graphs and M -graphs in the three previous examples
given in Figure 3. Notice that in (a) and (b) the respective R-graphs are not isomorphic while in
(b) and (c) only the M -graphs are not isomorphic. The Figure 5 shows one more example of two
stable maps from sphere S2 and their respective R-graphs and M -graphs.

Figure 5: Examples of R-graphs and M -graphs associated to stable maps on sphere.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 343 — #7 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 343

This suggests that these two graphs togheter may give more information to differ two immersions
of M in R3 that just one of them. This is our motivation to introduce, in the next Section, the called
RM -graph which is a pair of graphs.

3 RM -GRAPHS ASSOCIATED TO BI-STABLE MAPS

Given a smooth closed orientable surface M, let j : M →R3 be an embedding and as said before,
let us consider bi-stable maps of type F = ( f1, f2) : M → R×R2, where f1 is a projection in a
line and f2 is a projection on a plane. By simplicity, if we consider Rv =R and Pv =R2, we can
take

f1 = π1 ◦ j and f2 = π2 ◦ j,

where πi denotes the canonical projection in Ri, i = 1,2.

Definition 3.1. If G 1 is the R-graph associated to f1 : M →R and G 2 is the M -graph associated
to f2 : M → R2, then we say that the pair of graphs (G 1,G 2) is the RM -graph associated to the
stable bi-map F = ( f1, f2) : M → R×R2.

In the next pictures, the RM -graphs will be illustrated always in this order (G 1,G 2). Moreover,
the notation G i(V i,E i) will indicate that the graph G i is a graph with V i vertices and E i edges,
i = 1,2.

In an RM -graph, the R-graph contributes to determine the position of the maximum and mini-
mum points (local and global) of f1 while the M -graph contributes to determine the position of
the regular regions and singular curves of f2 in M.

3.1 R-graphs

Given a stable map f1 : M → R we consider the following equivalence relation on M:

x ∼ y ⇔ f1(x) = f1(y) and x and y are in the same connected component of f−1
1 ( f1(x)).

Then the quotient space M/ ∼ admits the structure of a connected graph where the vertices are
the connected components of critical level curves f−1

1 (v) which contains critical points of f1 and
each edge is formed by points that correspond to connected components of level curves f−1

1 (w),
where w ∈ R is a regular value and v ∈ R is a critical value of f1.

Each vertex of the graph can be of three types, depending on the critical points in the connected
component as shown in Figure 6.

Figure 6: Incidence rules for the vertices in a Reeb graph.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 344 — #8 i
i

i
i

i
i

344 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

Let v1, . . . ,vr ∈ R be the critical values of f1. We choose a base point v0 ∈ R and an orientation.
We can reorder the critical values such that v0 ≤ v1 < · · ·< vr and we label each vertex with the
index i ∈ {1, . . . ,r}, if it corresponds to the critical value vi.

Definition 3.2. The graph given by M/ ∼ together with the labels of the vertices, as previously
defined, is said to be the Reeb graph (or R-graph) associated to f1 : M → R.

Figure 7: Examples of R-graphs from sphere.

It is known that the Reeb graph is a complete topological invariant for stable functions (cf. [1]).
The example in Figure 7 shows that the R-graph is an invariant that distinguishes what the image
set of the critical points cannot tell us.

Follows from the possible incidence rules of edges and vertices in an R-graph that all its vertices
have degree 1 or 3. Graphs with this property will be called here 1-trivalent graphs.

Hence, the R-graph associated to a stable map f1 is 1-trivalent. Moreover, the Euler character-
istic of M is given by χ(M) = 2(V 1 −E1). In other words, the topology of surface M can be
determined by the R-graph associated to f1.

Follows from the Poincaré-Hopf theorem that every R-graph associated to a stable map f1 : S2 →
R is a 1-trivalent tree.

Theorem 3.1. Any 1-trivalent graph G 1(V 1,E1) is a R-graph associated to a stable map f1 :
M → R where the Euler characteristic of M is χ(M) = 2(V 1 −E1).

Proof. Given a 1-trivalent graph G 1(V 1,E1), we can construct a surface M such that G 1(V 1,E1)

is the R-graph associated to the height function f : M →R. In fact, consider an embedding of the
graph G 1(V 1,E1) in R3. Let M be the boundary of a thin tubular neighborhood of G 1(V 1,E1).
Then M is diffeomorphic to a surface with χ(M) = 2(V 1 −E1). Moreover, the restriction of the
height function on M, f : M →R, is a stable map whose R-graph is equivalent to G 1(V 1,E1). □

3.2 M -graphs

Given a stable map f2 : M → R2, its topological information may be conveniently encoded in
a determined weighted graph. In fact, given the pair (M,Σ f2), we may reconstruct (up to dif-
feomorphism) a weighted graph associated to f2 (cf. [8]), in the following sense: the edges and
vertices of this weighted graph correspond to the singular curves and the connected components

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 345 — #9 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 345

of the regular set, respectively. An edge is incident to a vertex if and only if the corresponding
singular curve to the edge lies in the boundary of the regular region corresponding to the vertex.
The weight of a vertex is defined as the genus of the corresponding region. This graph is called
M -graph (or Mendes-graph) associated to f2.

It is known that the M -graph is a complete topological invariant for stable maps from M to the
plane (cf. [8]).

Let G 2(V 2,E2,W 2) be the M -graph associated to f2, where V 2, E2 and W 2 correspond to the
number of vertices, edges and the total weight of the graph, respectively. Then E2 represents the
number of connected components of Σ f2; V 2 the number of connected components of M \Σ f2

and W the total sum of genus of the components of M \Σ f2.

If W 2 = 0, that is, if G 2 is a graph without weight, we will denote by simplicity G 2(V 2,E2)

omitting W 2 in the graph notation.

Figure 8: Examples of M -graphs associated to stable maps from sphere.

The Figure 8 illustrates two stable maps f2,g2 : S2 → R2 whose M -graphs are non equivalent,
where ji indicates the respective embedding from S2 in R3 and πi the canonical projection,
i= 1,2. This example shows that the M -graph is an invariant that distinguishes what the apparent
contour sets of f2 and g2 can not distinguish.

Given a stable map f2 : M →R2 always it is possible to obtain its M -graph associated. Moreover,
the Euler characteristic of M is given by χ(M) = 2(V 2 −E2 −W 2). In other words, the topology
of surface M can be determined by M -graph G 2(V 2,E2,W 2) associated to f2.

Given the orientations of M and R2, a region of M is said to be positive (resp. negative) if the
map f2 preserves (resp. reverses) orientation. Since each component of Σ f2 is the boundary of
a positive and a negative region, the signs of the vertices are assigned alternately, that is, the
M -graph associated to stable map f2 : M → R2 is bipartite.

To be a bipartite graph is a necessary condition for a graph to be a M -graph for some stable map
f2 : M → R2.

Theorem 3.2. ( [8]) Any bipartite connected graph (with arbitrarily weighted vertices) is the
M -graph of a stable map f2 : M → R2.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 346 — #10 i
i

i
i

i
i

346 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

The proof of Theorem 3.2 is based in a convenient manipulation of codimension one transitions
(lips and beaks) in the space C∞(M,R2) and convenient surgeries of stable maps (see [8] for more
details). Transitions and surgeries involving stable maps will be treated with more details in the
next Section.

As a consequence of Theorem 3.2, any tree with W 2 = 0 may be realized as the M -graph of
some stable map f2 : S2 → R2.

From now on, we focus on M -graphs without weighted vertices (that is, W 2 = 0). The case
W 2 > 0 will be studied in a future work in progress.

4 TOOLS USED TO CONSTRUCT STABLE BI-MAPS

Let E ∞(M,Rp) be the set of all stable maps in C∞(M,Rp), p = 1,2.

In this work we are considering stable bi-maps of type F = ( f1, f2) : M → R×R2 which can be
decomposed (locally) as fi = πi ◦ j, i = 1,2, where j is an embedding from M in R3 and πi are
the canonical projections from j(M) to R and R2, respectively, i = 1,2. Replacing the embedding
j by another embedding from M in R3, we can obtain new stable bi-maps. This procedure can be
done by taking small perturbations of the embedding j, so that they may alter or not the images
of the projections π1 and π2. The new stable bi-maps obtained in this procedure have associated
new RM -graphs. Then, it is natural to ask whether these changes modify the new RM -graphs
or not.

The alterations used here to obtain new stable bi-maps correspond to transitions and surgeries
and they are described with more details in the next Subsections.

4.1 Elementary Morse transitions

In this Subsection let us consider stable maps in E ∞(M,R).

A Morse transition corresponds to an isotopy from a given stable map to another in a different
path component of E ∞(M,R). Thus, a Morse transition allows to transform a stable map f1 :
M → R in another f̃1 : M → R in such a way that their respective R-graphs have a different
number of vertices or the same number of vertices with noncompatible labels.

A Morse transition T is called elementary if the isotopy T transforms f1 in f̃1 through one of the
following ways:

[C ] The isotopy T creates a new edge in R-graph of f1. That is, if T (0) = f1 and its R-graph
has s saddles and m max/min points then T (1) = f̃1 and the R-graph of f̃1 has s+1 saddles
and m+1 max/min points, with the new saddle and max/min point being connected by a
new edge.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 347 — #11 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 347

[−C ] It is the inverse transition of C. That is, when the isotopy collapses an edge of R-graph
of f1, with the vertices that were removed being previously connected by an edge. In this
case, the R-graph of f̃1 has s−1 saddles and m−1 max/min points.

The Figure 9 indicates examples of elementary Morse transitions.

Figure 9: The effect of the elementary Morse transitions in the R-graphs.

For more details about the consequences of Morse transitions in a Reeb graph see [10].

Since elementary Morse transitions do not generate any new critical curve related to projection π2

(in the plane), the M -graph has no change after C or −C transitions. In other words, elementary
Morse transitions alter the RM -graph associated to original stable bi-map F = ( f1, f2) = (π1 ◦
j,π2 ◦ j), changing only its R-graph.

Definition 4.3. Given a R-graph G 1, we say that a C transition is a 1-extension over the graph
G 1.

A sequence of n 1-extensions over a R-graph increases n vertices of degree 1 (max/min points)
and n vertices of degree 3 (saddles) over the original R-graph.

Any 1-trivalent tree G 1(V 1,V 1 −1) can be obtained as a R-graph of a stable map from M to
R by applying a sequence with (V 1 −2)/2 1-extensions over the R-graph of canonical height
function from S2 to R.

Proposition 4.1. All pair of trees (G 1(V 1,V 1 −1),G 2(2,1)) is a RM -graph of some stable
bi-map F = ( f1, f2) : S2 → R×R2, where G 1(V 1,V 1 −1) is a 1-trivalent tree.

Proof. Since G 1(V 1,V 1 −1) is an 1-trivalent tree, then V 1 is even and (V 1 −2)/2 is a integer
number. Consider the standard stable bi-map G = (g1,g2) : S2 → R×R2 where gi = πi ◦ j and
j : S2 → R3 is the inclusion.

Let (G 1(2,1),G 2(2,1)) be the RM -graph associated to G. After a sequence with (V 1 −2)/2
1-extensions over the RM -graph of G without altering the singular set of g2, we obtain a new

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 348 — #12 i
i

i
i

i
i

348 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

stable bi-map F = ( f1, f2) : S2 →R×R2 which realizes the graph (G 1(V 1,V 1 −1),G 2(2,1)). In
fact, each 1-extension increases two edges and two vertices in the R-graph and do not alter the
M -graph. □

4.2 Lips, beaks and swallowtail transitions

In this Subsection we will consider transitions that alter only the M -graph in a RM -graph
associated to a stable bi-map F = ( f1, f2) : M → R×R2. They are the same transitions that
change the regular and singular sets of f2, namely the lips transitions, denoted by L and beaks
transitions, denoted by B (see Figure 10). We denote by −B and −L, respectively, the inverse
transitions of B and L. These transitions also change the number of cusps by ±2 and they are
sufficient to show that any tree with weight equal zero can be realized as a graph of a stable map
from S2 to R2 (see [8]).

Figure 10: Lips and beaks transitions.

Let G2(V 2,E2) be the M -graph (without weight) associated to a stable map f2 : M →R2. Then,
the lips transition increases by 1 the number of regions in M (i.e., vertices in V 2) and the number
of singular curves in M (i.e., edges in E2). The beaks transition can be classified in four different
cases (see Figure 12):

Figure 11: Beaks transition and C-transition on the torus.

B+
v : beaks transition increases by 1 the number of regular regions, i.e., it adds 1 vertex and 1

edge on the M -graph;

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 349 — #13 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 349

B−
v : beaks transition decreases by 1 the number of regular regions, therefore it removes 1

vertex and 1 edge on the M -graph (see Figure 13);

B+
w : beaks transition increases by 1 the weight, maintains the number of regular regions

(vertices) but decreases by 1 the number of edges (see Figure 11);

B−
w : beaks transition decreases by 1 the weight, maintains the number of regular regions

(vertices) but increases by 1 the number of edges.

Figure 12: Decomposition of beaks transition.

The four types of beaks transition are illustrated (locally) in Figure 12, where in the picture
X , X1, Y, Z, Z1 and Z2 denote (locally) the regular regions where the transitions hold and the
numbers 1 and 2 represent the number of singular curves.

Definition 4.4. Given a M -graph G2(V 2,E2) (without weight), we say that a composition of a
lips transition with a beaks transition (in this order) is a 2-extension over a M -graph when:

1. a lips transition L creates a singular curve α with 2 cusps and 1 new regular region D;

2. a beaks transition −B−
v eliminates the 2 cusps, dividing α into two new singular curves

and border of the new region D′, as illustrate Figure 13.

Figure 13: Lips and beaks transitions and 2-extensions.

The lips transition creates a new region D inside of region A, decomponding A into B and D,
where B is homeomorphic to a cilinder and D is homeomorphic to a disk. The beaks transition

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 350 — #14 i
i

i
i

i
i

350 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

transformes the regions B and D into C and D′, where D′ is homeomorphic to a cilinder and C is
homeomorphic to a disk.

Lips and beaks transitions can modify the singular set of a stable map from M to the plane, and
do not alter the singular set of the height function. That is, the R-graphs are preserved by 2-
extensions while the M -graphs always add two vertices (linked by one edge) with degree two
on the graph. The Figure 13 illustrates a sequence of transitions that alter the M -graph but they
do not the R-graph.

Definition 4.5. We call line graph, and denoted it by L 2(k), a graph with k vertices with degree
2 and k−1 edges.

In the Figure 13 we have three examples of M -graphs which are line graphs: (a) L 2(2); (b)
L 2(3) and (c) L 2(4). Moreover, the lips transition L holds in a positive region of S2 creating a
new singular curve with 2 cusps (see (b)). The beaks transition −B−

v in the negative new region
eliminates 2 cusps and adding a new singular curve (see (c)).

Applying 2-extensions we can show that all line graph L 2(k) is a M -graph of some stable map
f2 : S2 → R2. This is a consequence of Theorem 3.2.

4.3 Surgeries of stable bi-maps

Are considered two types of surgeries of stable bi-maps: horizontal and vertical surgeries. We
are interested to know the effects of these surgeries over the RM -graphs. This study is based in
the concepts introduced in [8].

Let F = ( f1, f2) : M → R×R2 be a bi-stable map, P and Q be two any regions of surface M,
where M may or may not be connected.

Horizontal surgery S h: Let p ∈ P,q ∈ Q be two singular points of f2. A bridge is an embedded
arc β in R2, which connects the set of singular values of f2 (or apparent contour) in its two end
points (and nowhere else). A new stable map f2h can be constructed as follows: the bridge links
the apparent contour of f2 in its points, f2(p) and f2(q). Choose small disks Dp,Dq in M centered
at p,q ∈ Σ f2, respectively. We can choose small enough disks such that they do not contain any
critical point of f1. Replace the interiors of Dp and Dq by a tube (i.e., an annulus) connecting
these two small disks obtaining a new connected surface N. Then f1 and f2 may be extended
over the tube to give new stable maps f1h and f2h, in such way that f1 has only 2 saddle points in
this tube, as shown (locally) in Figure 14.

The horizontal surgery S h connects the two regular regions of f1 and adds 2 saddle points, while
in f2 the horizontal surgery S h effects are:

i) it links the 2 singular curves if p and q are in two disjoint singular curves (see the graphs
in Figure 16 (a)-(b));

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 351 — #15 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 351

Figure 14: Horizontal surgery example.

ii) it separates a singular curve into two curves, if p and q are in the same singular curve (see
the graphs in Figure 16 (c)).

Vertical surgery S v: Let p ∈ P,q ∈ Q be two singular points of f2. We take a surgery between
P e Q by identifying two small topological disks Dp and Dq, one positive and one negative, such
that each one of them contains only 1 critical point of f1 in their interior being 1 maximum and
1 minimum, and its boundary is a connected component of a regular level curve of f1. The disks
are replaced by a tube which is mapped into R, with no singular points in the interior of the tube.
The stable map f1 may be extended over the tube to a new stable map f1v from a new connected
surface N to R. Also, the stable map f2 can be extended to a new stable map f2v : N → R2 with
one fold curve in the tube (see Figure 15).

The vertical surgery S v identifies a neighborhood of a maximum point of f1 as a neighborhood
of a minimum point of f1, eliminating two singular points. In f2, the surgery S v always creates
a new singular curve. In other words, the vertical surgery S v takes away two critical points of
the singular set Σ f1 while it adds one critical curve to Σ f2 (see Figure 15 and 16-(b)).

Notice that the regions P and Q can be in a same connected component of M or in two differ-
ent connected components. If P and Q are regions of the same connected component of M the
singular points p,q ∈ Σ f2 may or may not be in the same singular curve.

We denote by S h( f1, f2) = ( f1h, f2h) : N → R×R2 the new stable bi-map resulting after the
horizontal surgery S h, and by S h(G ) the effect in the graph G after applying a horizontal
surgery S h. Analogously we denote by S v( f1, f2) = ( f1v, f2v) : N → R×R2 the new stable

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 352 — #16 i
i

i
i

i
i

352 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

Figure 15: Vertical surgery of bistable maps.

bi-map resulting after the vertical surgery S v and by S v(G ) the effect in the graph G after
applying a vertical surgery S v.

Let P and Q be two regions of M that are in two connected component of M, then the surgeries
S h and S v over P and Q are called connected horizontal sum (see Figure 15-(a)) and connected
vertical sum (see Figure 15-(a)).

Definition 4.6. We denote by S h1 (resp. S v1) the horizontal surgery (resp. vertical surgery) of
stable maps from M to the plane that connects two regions of a connected surface M. We denote
by S h0 (resp. S v0) the horizontal surgery (resp. vertical surgery) that connects two regular
regions of two different connected components of M.

This local process of f2, for S ηα (η = h,v and α = 0,1) is illustrated in Figures 14 and 15,
which shows the effect of these surgeries on the graphs. It induces the following surgeries on the
R-graphs and M -graphs (see Figure 15):

A horizontal surgery on graphs which identifies two edges ur and vs, identifying the vertices u
with v and r with s, will be denoted by:

(a) S h0: when ru and sv are in different connected graphs, joining these two graphs (Figure
14-(a)).

(b) S h1: when ru and sv are in the same connected component of a graph, creating a new
cycle in the graph (see Figure 14-(b) and (c)).

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 353 — #17 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 353

A vertical surgery on graphs which connects two vertices, r positive and v negative, by an edge
rv, will be denoted by:

(c) S v0: when r and v are in different connected graphs, joining these two graphs (see Figure
15-(a)).

(d) S v1: when r and v are in the same connected graph, creates a new cycle in the graph (see
Figure 15-(b) and (c)).

The next result is a consequence from horizontal surgery and vertical surgeries.

Proposition 4.2. Let (G 1
1 ,G

2
1 ) and (G 1

2 ,G
2
2 ) be the RM -graphs associated to two stable

bi-maps F = ( f1, f2) : P −→ R×R2 and G = (g1,g2) : Q −→ R×R2, respectively. Then
(S αη(G 1

1 ,G
1
2 ),S

αη(G 2
1 ,G

2
2 )) is the RM -graph associated to the stable bi-map

(S αη( f1,g1),S
αη( f2,g2)) : S αη(P,Q)→ R×R2, α = h,v and η = 0,1.

The Figure 16 illustrates examples of surgeries of stable maps from sphere: (a) horizontal surgery
S h1 and (b) vertical surgery S v1.

Figure 16: Examples of surgeries: (a) vertical and (b) horizontal.

5 REALIZATION OF GRAPHS (G 1,G 2)

Lemma 5.1. All pair of trees (G 1(2,1),G 2(V 2,V 2 −1)) is a RM -graph of some stable bi-map
F = ( f1, f2) : S2 → R×R2.

Proof. Consider the pair of canonical maps (given by height function) G = (g1,g2) : S2 → R×
R2, such that the RM -graph associated to G is (G 1(2,1),G 2(2,1)). Since G 2(V 2,V 2 − 1) is a
tree, let L 2(k+1) be the biggest line subgraph of G 2(V 2,V 2−1) which connects two peripheral
vertices of G 2(V 2,V 2−1), where k+1≤V 2. Then, the pair (G 1(2,1),L 2(k+1)) can be realized
as the following:

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 354 — #18 i
i

i
i

i
i

354 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

i) If k is odd, k−1 is even. Passing through a sequence with (k−1)/2 of 2-extensions (without al-
tering the singular set of g1), we obtain a stable bi-map H = (h1,h2) : S2 →R×R2 which realizes
the graph (G 1(2,1),L 2(k+1)), because each 2-extension increases two edges and two vertices
in the M -graph and does not change the R-graph. After this, we can obtain a stable bi-map
F = ( f1, f2) : S2 → R×R2, as required, realizing the RM -graph (G 1(2,1),G 2(V 2,V 2 −1)),
taking V 2 − k lips transitions over H = (h1,h2), in convenient regions.

ii) If k is even, we can first obtain a stable bi-map H = (h1,h2) which realizes the graph
(G 1(2,1),L 2(k + 1)) as done in item i). Then, we can obtain a stable bi-map F = ( f1, f2) :
S2 →R×R2, as required, realizing the RM -graph (G 1(2,1),G 2(V 2,V 2 −1), taking V 2 −k+1
lips transitions over H = (h1,h2), in convenient regions. □

Proposition 5.3. If G 1 is a 1-trivalent tree and G 2 is a tree whithout weights then the graph
(G 1,G 2) is a RM -graph of some stable bi-map F = ( f1, f2) : S2 → R×R2.

Proof. Let G 1(V 1,V 1 −1) be a 1-trivalent tree and G 2(V 2,V 2 −1) be a tree with W 2 = 0. Con-
sider L 2(k + 1) the biggest line subgraph of G 2(V 2,V 2 − 1). Then by Lemma 5.1, the graph
(G 1(2,1),L 2(k+1)) can be realized by some stable bi-map G = (g1,g2) : S2 → R×R2. Since
V 1 is even and each 1-extension increases 2 vertices and 1 edge to the R-graph, then pass-
ing through a sequence with (V 1 −2)/2 1-extensions over G = (g1,g2) we obtain a stable
bi-map F = ( f1, f2) : S2 → R×R2 which realizes the graph (G 1(V 1,V 1 − 1),G 2(V 2,V 2 − 1)),
as required. □

From Poincaré-Hopf theorem, Theorem 3.2 and Proposition 5.3, we obtain the following result:

Theorem 5.3. A graph (G 1,G 2) is a RM -graph for a stable bi-map F = ( f1, f2) : S2 →R×R2

if and only if G 1 is a tree 1-trivalent and G 2 is a tree without weights (i.e., with W 2 = 0).

Theorem 5.4. Let G 1 be a 1-trivalent graph and G 2 be a bipartite graph (with W 2 = 0). Suppose
χ(G 1) = χ(G 2). Then the graph (G 1,G 2) is a RM -graph associated to a stable bi-map F =

( f1, f2) : M → R×R2, where χ(M) = 2χ(G 1) = 2χ(G 2).

Proof. Since χ(G 1) = χ(G 2), both graphs have the same number m of cycles. Consider a pair
of support trees (T 1,T 2) defined in the following way:

i) T 1 is obtained by choosing one edge in each one of the m cycles of G 1 and subdividing each
chosen edge obtaining m new vertices of degree 2. Then we cleave each new vertex vi

(i = 1, · · · ,m) in to two new vertices vi1 and vi2, obtaining 2m new vertices of degree 1.

ii) T 2 is a spanning tree of G 2, that is, a tree that contains all the vertices of G 2, obtained by
removing one edge of each cycle of G 2.

By Theorem 5.3, (T 1,T 2) is a RM -graph of a stable bi-map G = (g1,g2) : S2 −→ R×R2.
Consider the regions Ui1 and Ui2 of S2 corresponding to the neighborhoods of the points asso-
ciated with a pair of vertices vi1 and vi2 obtained in (i), respectively. For each pair of vertices

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 355 — #19 i
i

i
i

i
i

C. MENDES DE JESUS, E. BOIZAN BATISTA and J. C. F. COSTA 355

vi1 and vi2, we may realize a vertical surgery over Ui1 and Ui2 obtaining a new stable bi-map
F = ( f1, f2) : M −→R×R2 (where M is a surface with genus m) which realizes the RM -graph
(G 1,G 2). □

The next result is a consequence of the previous results and remarks.

Theorem 5.5. Consider a pair of graphs (G 1,G 2), with χ(G 1) = χ(G 2). Then (G 1,G 2) is a
RM -graph for some stable bi-map F = ( f1, f2) : M −→ R×R2, where M is a closed oriented
surface with χ(M) = 2χ(G 1) = 2χ(G 2), if and only if G 1 is a 1-trivalent graph and G 2 is a
bipartite graph without weights (i.e. W 2 = 0).

Acknowledgments
The third named author has been partially supported by grants 2018/25157-3 and 2019/21181-0
São Paulo Research Foundation (FAPESP).

REFERENCES

[1] V.I. Arnold. Topological classification of Morse functions and generalisations of Hilbert’s 16-th
problem. Mathematical Physics, Analysis and Geometry, 10 (2007), 227–236.

[2] E.B. Batista, J.C.F. Costa & I.S. Meza-Sarmiento. Topological classification of circle-valued simple
Morse–Bott functions. J. Singul, 17 (2018), 388–402.

[3] E.B. Batista, J.C.F. Costa & J.J. Nuño-Ballesteros. The Reeb graph of a map germ from R3 to R2 with
isolated zeros. Proc. Edinb. Math. Soc., 60(2) (2017), 388–402.

[4] E.B. Batista, J.C.F. Costa & J.J. Nuño-Ballesteros. The Reeb graph of a map germ from R3 to R2

without isolated zeros. Bull. Braz. Math. Soc. (N.S.), 49 (2018), 369–394.

[5] S. Biasotti, D. Giorgi, M. Spagnuolo & B. Falcidieno. Reeb graphs for shape analysis and applications.
Theoretical computer science, 392(1-3) (2008), 5–22.

[6] I. Gelbukh. Realization of a Graph as the Reeb Graph of a Morse–Bott or a Round Function. Studia
Scientiarum Mathematicarum Hungarica, 59(1) (2022), 1–16.

[7] M. Golubitsky & V. Guillemin. Stable mappings and their singularities. In “Graduate Texts in
Mathematics 14”, volume 14. Springer Science & Business Media (2012).

[8] D. Hacon, C.M. de Jesus & M.R. Fuster. Stable maps from surfaces to the plane with prescribed
branching data. Topology and its Applications, 154(1) (2007), 166–175.

[9] N. Kitazawa. Realization problems of graphs as Reeb graphs of Morse functions with prescribed
preimages. arXiv preprint arXiv:2108.06913, (2021).

[10] E.A. Kudryavtseva. Realization of smooth functions on surfaces as height functions. Sbornik:
Mathematics, 190(3) (1999), 349.

Trends Comput. Appl. Math., 24, N. 2 (2023)


i
i

“A10-1659” — 2023/4/25 — 13:12 — page 356 — #20 i
i

i
i

i
i

356 STABLE BI-MAPS ON SURFACES AND THEIR GRAPHS

[11] Y. Masumoto & O. Saeki. A smooth function on a manifold with given Reeb graph. Kyushu Journal
of Mathematics, 65(1) (2011), 75–84.

[12] Ł.P. Michalak. Realization of a graph as the Reeb graph of a Morse function on a manifold. Topol.
Methods Nonlinear Anal., 52(2) (2018), 749–762.

[13] T. Ohmoto & F. Aicardi. First order local invariants of apparent contours. Topology, 45(1) (2006),
27–45.

[14] S. Pirzada. Applications of graph theory. In “PAMM: Proceedings in applied mathematics and
mechanics”. Wiley Online Library (2007), p. 2070013–2070013.

[15] G. Reeb. Sur les points singuliers d’une forme de Pfaff completement intégrable ou d’une fonction
numérique. C. R. Acad. Sci. Paris, 222 (1946), 847–849.

[16] R. Thomas. A Combinatorial Construction of a Nonmeasurable Set. The American Mathematical
Monthly, 92(6) (1985), 421–422.

[17] N. Werghi, Y. Xiao & J.P. Siebert. A functional-based segmentation of human body scans in arbitrary
postures. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 36(1) (2006),
153–165.

[18] H. Whitney. On singularities of mappings of Euclidean spaces. I. Mappings of the Plane into the Plane.
Ann. of Math., 62 (1995), 374–410.

Trends Comput. Appl. Math., 24, N. 2 (2023)