# Cographic Splitting of Graphic Matroids with Respect to a Set with Three
Elements

###### Abstract.

In general, the splitting operation on binary matroids does not preserve the
graphicness and cographicness properties of binary matroids. In this paper, we
obtain a characterization of the class of graphic matroids whose splitting
with respect to a set of three elements gives cographic matroids. We also
provide an alternate proof to such characterization when the set contains two
elements which was provided by Borse et al. [2].

Shital Dilip Solanki1, Ganesh Mundhe2 and S. B. Dhotre3
_1\. Ajeenkya DY Patil University, Pune-411047, Maharashtra, India
2\. Army Institute of Technology, Pune-411015, Maharashtra, India
3\. Department of Mathematics, Savitribai Phule Pune University,
Pune - 411007, Maharashtra, India_
E-mail: 1\<EMAIL_ADDRESS>2<EMAIL_ADDRESS>3.
<EMAIL_ADDRESS>

Mathematics Subject Classification (2010): 05B35, 05C50, 05C83
Keywords: Binary Matroid, Splitting, Graphic, Cographic, Minor, Quotient.

##  1\. Introduction

We refer to Oxley [10] for undefined terminology and notations. There are many
operations in graph theory that are of great importance. The Splitting
operation is one of them, which is introduced by Fleischner [3]. He has
characterized Eulerian graphs using this operation. The Splitting operation is
given as follows. Let $v$ be a vertex of a connected graph G such that
$d(v)\geq 3$ . If $x,y$ are two edges incident at $v$ such that $x=vv_{1}$ and
$y=vv_{2}$. Let $G_{x,y}$ be obtained from $G$ by removing edges $x,y$ and by
adding a vertex $v_{x,y}$ adjacent to $v_{1}$ and $v_{2}$. The splitting
operation on the graph $G$ with respect to $x$ and $y$ is defined as the
transition from $G$ to $G_{x,y}$.

The Splitting operation is further extended to binary matroids by Raghunathan
et al. [6] and defined the splitting operation with respect to a pair of
elements of a binary matroid. Later, it is generalized by Shikare at al. [8]
by defining the splitting of a binary matroid with respect to any set $T$ as
follows.

######  Definition 1.1.

[8] Let $M$ be a binary matroid and let $A$ be the standard matrix
representation of $M$ over the field $GF(2)$ and let $T\subseteq E(M)$. Obtain
a matrix $A_{T}$ by adjoining one row at the bottom of the matrix $A$ with
entries 1 in the columns corresponding to the elements of the set $T$ and zero
otherwise. Then the vector matroid, denoted by $M_{T}$, is called the
splitting matroid of $M$ with respect to $T$, and the splitting operation with
respect to $T$ is the transition from $M$ to $M_{T}$.

Some properties of a binary matroid are not preserved under the splitting
operation. Connectedness, graphicness and cographicness are a few properties
among the properties of binary matroids which are not preserves under the
splitting operation. Shikare and Waphare [7] obtained characterization for a
graphic matroid $M$ whose splitting matroid $M_{T}$ is also graphic for any
$T$ with two elements. Mundhe [4] obtained a similar characterization for a
set $T$ with three elements. Borse et al. [2] characterized the class of
graphic matroids, which yields a cographic matroid under the splitting
operation with respect to a pair of elements. In this paper, we characterize a
graphic matroid that gives a cographic matroid under the splitting operation
with respect to any set $T$ with $|T|=3$.

Let $\mathcal{M}_{k}$ be the class of graphic matroid whose splitting with
respect to any set of $k$-elements is cographic. Let $N$ be an extension of
$M(K_{5})$ or $M(K_{3,3})$ by an element $a$. Then the splitting of $N$ with
respect to $a$ is not cographic. Therefore the single element extensions of
$M(K_{5})$ and $M(K_{3,3})$ are the forbidden minors the class
$\mathcal{M}_{1}$ and only these are the forbidden minors as per the
definition of the splitting operation. Let $N$ be an extension of $M(K_{5})$
by a set $T$ with $|T|=2$ such that $T$ be a 2-cocircuit of $N$. Then
$N\backslash T=M(K_{5})$ and, by Definition 1.1, $N_{T}\backslash
T=N\backslash T=M(K_{5}).$ Thus $N$ is a forbidden minor for the class
$\mathcal{M}_{2}.$ Similarly, it is easy to check that $\mathcal{M}_{2}$
contains a forbidden minor $N$ which arise as follows. (i) $N$ is an extension
of $M(K_{5})$ or $M(K_{3,3})$ by two elements $x,y$ such that ${x,y}$ is a
2-cocircuit of $N$ or (ii) $N$ is a coextension of $M(K_{5})$ or $M(K_{3,3})$
by an element $x$ such that ${x,y}$ is a 2-cocircuit of $N$ for some $y\in
E(N)$.

If $N$ is a forbidden minor for the class $\mathcal{M}_{k}$ which is
isomorphic to $M(K_{5})$, $M(K_{3,3})$ or a matroid which arises by extensions
and coextensions of $M(K_{5})$ or $M(K_{3,3}),$ then we call $N$ is a trivial
forbidden minor for the class $\mathcal{M}_{k}$. Let $\mathcal{T}_{k}$ be a
set containing all trivial forbidden minors for the class $\mathcal{M}_{k}$.
We focus on the forbidden minors of the class $\mathcal{M}_{k}$ other than the
members of $\mathcal{T}_{k}$.

In the following result, Borse et al. [2] have given forbidden minors for the
class $\mathcal{M}_{2}.$

######  Theorem 1.1.

[2] Let $M$ be a graphic matroid without containing a minor isomorphic to any
member of $\mathcal{T}_{2}$. Then $M\in\mathcal{M}_{2}$ if and only if $M$
does not contain a minor isomorphic to any one of the circuit matroids
$M(G_{1})$, $M(G_{2})$ and $M(G_{3})$, where $G_{1}$, $G_{2}$ and $G_{3}$ are
the graphs as shown in Figure 1.

$G_{1}$$G_{2}$$G_{3}$ Figure 1. Forbidden Minors for the Class
$\mathcal{M}_{2}$.

Denote, by $\tilde{M}$, the single element extension of $M$. Later on, Mundhe
[4] obtained forbidden minor for a class of graphic matroid which yields
graphic matroid under the splitting operation with respect to a set of three
elements as follows.

######  Theorem 1.2.

[4] Let $M$ be a graphic matroid. Then $M_{T}$ is graphic for any $T\subseteq
E(M)$ with $|T|=3$ if and only if $M$ does not contain a minor isomorphic to
any of the circuit matroids $\tilde{M}(Q_{1})$, $\tilde{M}(Q_{2})$,
$M(Q_{3}),$ $M(Q_{4}),$ $M(Q_{5})$ and $M(Q_{6}),$ where $Q_{i}$ is the graph
as shown in Figure 2, for $i=1,2,\dots,6.$

$Q_{1}$$Q_{2}$$Q_{3}$$Q_{4}$$Q_{5}$$Q_{6}$ Figure 2. Forbidden Minors for the
Class of Graphic Matroid which yields Graphic Matroid.

In this paper, we obtain excluded minors for the class $\mathcal{M}_{3}$. The
following is the main result of the paper.

######  Theorem 1.3.

Let $M$ be a graphic matroid without containing a minor isomorphic to any
member of the set $\mathcal{T}_{3}.$ Then $M\in\mathcal{M}_{3}$ if and only if
$M$ does not contain a minor isomorphic to any of the matroid
$\tilde{M}(G_{1})$, $\tilde{M}(G_{3})$, $M(G_{4})$, $M(G_{5})$, $M(G_{6})$ and
$M(G_{7})$, where $G_{i}$ is the graph shown in Figure 1 or Figure 3, for
$i=1,3,4,5,6,7$.

$G_{4}$$G_{5}$$G_{6}$$G_{7}$ Figure 3. Forbidden Minors for the Class
$\mathcal{M}_{3}$.

We prove the main result in Section 5. We also give an alternate and short
proof to the characterization of the class $\mathcal{M}_{2}$ in the fourth
section. Section 2 and Section 3 contain results that are useful to prove the
paper’s main result.

##  2\. Minimal Matroid

In this section, we prove that if the splitting of a graphic matroid is not
cographic, then it contains a special type of graphic matroid as a minor. Let
$\mathcal{F}=\\{F_{7},F_{7}^{*},M(K_{5}),M(K_{3,3})\\}.$

We use the following result from Oxley’s book [10].

######  Theorem 2.1.

[10] Let $M$ be a binary matroid. Then $M$ is a cographic matroid if and only
if $M$ does not contain a minor isomorphic to any member of the set
$\mathcal{F}$.

The following result is proved in [4].

######  Lemma 2.2.

[4] Let $M$ be a binary matroid and $T\subseteq E(M)$. Then the following
holds.

  1. (i).

If $x\in E(M)-T$, then $(M_{T})\backslash x=(M\backslash x)_{T}$ and
$(M_{T})/x=(M/x)_{T}$.

  2. (ii).

If $y\in T$, then $(M_{T})\backslash y=((M)\backslash y)_{T-{y}}$.

  3. (iii).

$M_{T}\backslash T=M\backslash T$.

  4. (iv).

$M_{T}=M$ , if $T$ is a cocircuit of $M$.

In the following result, we prove that if the splitting matroid of a graphic
matroid is not cographic, then it contains a minimal minor whose splitting is
not cographic.

######  Lemma 2.3.

Let $M$ be a graphic matroid and $k=2,3$. If $M_{T}$ contains a minor
isomorphic to $F$ for some $F\in\mathcal{F}$ and $T\subseteq E(M)$ with
$|T|=k$, then $M$ has a minor $N$ with $T\subseteq N$, such that one of the
following holds.

  1. (i).

$N_{T}\cong F$.

  2. (ii).

$N_{T}/T^{\prime}\cong F$ for some non-empty subset $T^{\prime}$ of $T$.

  3. (iii).

$N$ is isomorphic to one element extension of forbidden minors for the class
$\mathcal{M}_{k-1}$.

  4. (iv).

$N$ is isomorphic to some member of $\mathcal{T}_{k}.$

###### Proof.

Let $M_{T}$ contains a minor isomorphic to $F$ for some $F\in\mathcal{F}$ and
$T\subseteq E(M)$ with $|T|=k$, where $k=2,3$. Then there exist
$T_{1},T_{2}\subseteq E(M)$ such that $M_{T}\backslash T_{1}/T_{2}\cong F$.
Now let $T_{i}^{\prime}=T\cap T_{i}$ and
$T_{i}^{\prime\prime}=T_{i}-T_{i}^{\prime}$ for $i=1,2$. Then
$T_{i}^{\prime}\subseteq T$ and $T_{i}^{\prime\prime}\cap T=\phi$. By Lemma
2.2(1), $M_{T}\backslash
T_{1}^{\prime\prime}/T_{2}^{\prime\prime}=(M\backslash
T_{1}^{\prime\prime}/T_{2}^{\prime\prime})_{T}$. Let $N=M\backslash
T_{1}^{\prime\prime}/T_{2}^{\prime\prime}$. Then $N$ is minor of $M$
containing $T$ and $N_{T}\backslash T_{1}^{\prime}/T_{2}^{\prime}=(M\backslash
T_{1}^{\prime\prime}/T_{2}^{\prime\prime})_{T}\backslash
T_{1}^{\prime}/T_{2}^{\prime}=M_{T}\backslash
T_{1}^{\prime\prime}/T_{2}^{\prime\prime}\backslash
T_{1}^{\prime}/T_{2}^{\prime}=M_{T}\backslash T_{1}/T_{2}\cong F.$

If $T_{1}^{\prime}=\phi$ and $T_{2}^{\prime}=\phi,$ then (i) or (iv) holds. If
$T_{1}^{\prime}=\phi$ and $T_{2}^{\prime}\neq\phi$ then (ii) or (iv) holds. If
$T_{1}^{\prime}\neq\phi$, then $|T_{1}^{\prime}|\leq k=|T|$. Suppose
$|T_{1}^{\prime}|=k.$ Then $T_{1}^{\prime}=T$ and $F\cong N_{T}\backslash
T_{1}^{\prime}=N_{T}\backslash T=N\backslash T$ this shows that $F$ is minor
of graphic matroid $M$ which shows that (iv) holds. Let $|T_{1}^{\prime}|<k$
and $z\in T_{1}^{\prime}.$ Suppose $N\backslash z=P$. Then, by Lemma 2.3 (ii),
$N_{T}\backslash T_{1}^{\prime}/T_{2}^{\prime}=N_{T}\backslash z\backslash
T_{1}^{\prime}-\\{z\\}\backslash T_{2}^{\prime}=P_{T-\\{z\\}}\backslash
T_{1}^{\prime}-\\{z\\}/T_{2}^{\prime}\cong F.$ Therefore $N$ is extension of
$P,$ which is a forbidden minor for the class $\mathcal{M}_{k-1}.$ Which means
(iii) hold. ∎

We focus on finding forbidden minors for the class $\mathcal{M}_{k}$ other
than the members of $\mathcal{T}_{k}$ for $k=2,3.$ Henceforth, we consider the
graphic matroids, which do not contain a minor isomorphic to any member of
$\mathcal{T}_{k}$ for $k=2,3.$

######  Lemma 2.4.

Let $N$ be the minor of the matroid $M$ stated in Lemma 2.3 and without
containing a minor isomorphic to any member of $\mathcal{T}_{k}$. Then $N$
does not contain 2-cocircuit.

###### Proof.

The proof is similar to the proof of Lemma 3.3.2, in [4]. ∎

######  Lemma 2.5.

Let $N$ be the minor of the matroid $M$ stated in Lemma 2.3, such that $N$
does not satisfy conditions (iii) and (iv). Then $N$ does not contain a
coloop.

###### Proof.

The proof is similar to the proof of Lemma 3.3.3, in [4]. ∎

We call the matroid $N$ of Lemmas 2.3, 2.4 and 2.5 as a $k$-minimal matroid
with repsect to $F$ where $F\in\mathcal{F}.$ We define a $k$-minimal matroid
with respect $F\in\mathcal{F}$ as follows.

######  Definition 2.1.

Let $k=2,3$ and $N$ be a graphic matroid without containing any member of
$\mathcal{T}_{k}.$ Then $N$ is called $k$-minimal matroid with respect to some
$F$ of $\mathcal{F}$ if the following conditions hold.

  1. (i).

$N$ contains no coloop and no 2-cocircuit.

  2. (ii).

$N$ is not a single element extension of any member of forbidden minors of
$\mathcal{M}_{k-1}$.

  3. (iii).

There is a set $T\subseteq E(N)$ with $|T|=k$ such that $N_{T}\cong F$ or
$N_{T}/T^{\prime}\cong F$ for some non-empty subset $T^{\prime}$ of $T$.

In light of Lemma 2.3 and Definition 2.1, we focus on to find the $k$-minimal
matroids with respect to every member of $\mathcal{F}$, for $k=2,3$. Let $M$
be a matroid. Then matroid $Q$ is called a quotient of $M$ if there exist a
matroid $N$ such that $Q=N/a$ and $N\backslash a=M$ for some $a\in N$. Here
$M$ is called a lift of $Q$. We prove that a $k$-minimal matroid with respect
to $F$ contains a minor isomorphic to a quotient of $F$ in the following
lemma.

######  Lemma 2.6.

Let $k=2,3$ and let $M$ be a $k$-minimal matroid with respect to
$F\in\mathcal{F}$. Then there is a binary matroid $N$ containing an element
$a$ such that $N\backslash a\cong F$. Further, $N/a$ is a minor of $M$ such
that either $M=N/a$ or $M$ is a coextension of $N/a$ by at most $k$ elements.

###### Proof.

Since $M$ is a $k$-minimal matroid, $M$ is graphic and $M_{T}\cong F$ or
$M_{T}/T^{\prime}\cong F$ for some $T\subseteq E(M)$ and $T^{\prime}\subseteq
T$ with $|T|=k$. Let $A$ be the standard matrix representation of $M$ over the
field $GF(2)$. Let $A_{T}^{\prime}$ be the matrix obtained from $A$ by adding
one extra row to the matrix $A$ at the bottom whose entries are $1$ in the
columns corresponding to the elements of $T$ and zero otherwise and then
adding one extra column labeled $a$ with entry $1$ in the last row and $0$
elsewhere. Let $M_{T}^{\prime}$ be the vector matroid of $A_{T}^{\prime}$.
Here $E(M_{T}^{\prime})=E(M)\cup\\{a\\}$. Therefore (i).
$M_{T}=M_{T}^{\prime}\backslash a$ and (ii). $M_{T}^{\prime}/a\cong M.$

$N=M_{T}^{\prime}$$M$$M_{T}$$N\backslash a$$N/a$

Suppose $M_{T}\cong F.$ Let $N=M_{T}^{\prime}.$ Then $N$ is a binary matroid
containing $a$, such that $M_{T}^{\prime}/a\cong N/a\cong M$ and
$M_{T}^{\prime}\backslash a\cong M_{T}\cong F\cong N\backslash a$.

Suppose $M_{T}/T^{\prime}\cong F$ for some $T^{\prime}\subset T.$ Let
$N=M_{T}^{\prime}/T^{\prime}$. Then $N\backslash a\cong
M_{T}^{\prime}/T^{\prime}\backslash a\cong M_{T}^{\prime}\backslash
a/T^{\prime}\cong M_{T}/T^{\prime}\cong F$ and $N/a\cong
M_{T}^{\prime}/T^{\prime}/a\cong M_{T}^{\prime}/a/T^{\prime}\cong
M/T^{\prime}.$ Here $M$ is a coextension of $N/a$ by at most $k$ elements as
$|T^{\prime}|\leq|T|=k$. ∎

In the above result, $N/a$ is a quotient of $F$, and $M$ is isomorphic to a
quotient of $F$ or a coextension of a quotient of $F$. Note that $N$ is
binary, and we obtain quotients through binary matroid coextension/extension.
Since $M$ is graphic, in the next section, we determine graphic quotients of
$F\in\mathcal{F}$.

##  3\. Graphic Quotients of Non-Cographic Matroids

In this section, we obtain graphic quotients of every member of the set
$\mathcal{F}.$ First, we prove the following lemma.

######  Lemma 3.1.

Let $N$ be a binary matroid containing an element $a$ such that $N\backslash
a\cong F$ for some $F\in\mathcal{F}$ and $N/a\cong M(G)$ for some connected
graph $G$. Then the following holds.

  1. (i).

The graph $G$ is a block, or it has at most two blocks, one of which is a
loop.

  2. (ii).

The graph $G$ contains at most one loop.

  3. (iii).

The graph $G$ does not contain more than two parallel edges with the same end
vertices.

  4. (iv).

The graph $G$ does not contain a 2-edge cut.

  5. (v).

If $F$ is Eulerian, then G is also Eulerian.

###### Proof.

The proof is similar to the proof of Lemma 3.4.1, in [4]. ∎

Mundhe [4], determined graphic quotients for $F_{7}^{*}$ and $F_{7}$ as
follows.

######  Lemma 3.2.

[4] Every graphic quotient of $F_{7}$ is isomorphic to the circuit matroid
$M(H_{3})$ and every graphic quotient of $F_{7}^{*}$ is isomorphic to the
circuit matroid $M(H_{1})$ or $M(H_{2}),$ where $H_{1}$, $H_{2}$, $H_{3}$ are
shown in Figure 4.

$H_{1}$$H_{2}$$H_{3}$ Figure 4. Quotients of $F_{7}^{*}$ and $F_{7}$.

We find all graphic quotients of $M(K_{5})$ and $M(K_{3,3}).$

######  Lemma 3.3.

Every graphic quotient of $M(K_{5})$ obtained via binary extension is
isomorphic to the circuit matroid $M(H_{4})$, $M(H_{5})$ or $M(H_{6})$, where
$H_{4}$, $H_{5}$ and $H_{6}$ are the graphs as shown in Figure 5.

$H_{4}$$H_{5}$$H_{6}$ Figure 5. Quotients of $M(K_{5})$

###### Proof.

Let $N$ be binary matroid containing $a$ such that $N\backslash a\cong
M(K_{5})$ and $N/a$ is graphic. Assume that $N/a=M(G)$ for a connected graph
$G$. Suppose $a$ is a loop or a coloop of $N$. Then $N/a=N\backslash a\cong
M(K_{5})$. Thus $G\cong H_{4}$.

Suppose $a$ is not a loop or a coloop of $N$. Since the graph $K_{5}$ has 5
vertices and 10 edges, $r(N)=4$ and $|E(N)|=11$. Hence $r(N/a)=3$ and
$|E(N/a)|=10.$ Thus graph $G$ corresponding to $N/a$ has 4 vertices and 10
edges. By Lemma 3.1(v), $G$ is Eulerian as $K_{5}$ is Eulerian and by Lemma
3.1, $G$ contains at most one loop.

If $G$ does not contain a loop, then, by Harary ([5], pg 230), there is only
one Eulerian graph on $4$ vertices and $10$ edges as shown in Figure 6. It
contains five distinct 2-cycles. That is, $N/a$ contains five 2-circuits. One
can easily check that $N\backslash a$ contains an odd cocircuit or a
2-circuit. Since $N\backslash a\cong M(K_{5}),$ $M(K_{5})$ contains an odd
cocircuit or a 2-circuit, a contradiction to $M(K_{5})$ is a Eulerian graph.
Hence we discard this graph.

Figure 6. Eulerian Graph on 4 Vertices and 10 Edges

If $G$ contains a loop, then $G$ minus that loop is an Eulerian graph of $4$
vertices and $9$ edges. By Harary ([5], pg 230), there is only one Eulerian
graph of $4$ vertices and $9$ edges. That graph is $H_{5}$ minus the loop as
shown in Figure 5. Thus $G$ can be obtained by adding a loop to that graph.
Hence $G$ is isomorphic to either the graph $H_{5}$ or $H_{6}$ as shown in
Figure 5. ∎

We need the following result to find graphic quotients of $M(K_{3,3})$.

######  Lemma 3.4.

Let $N$ be a binary matroid and $a\in E(N)$. If $N\backslash a\cong
M(K_{3,3})$, then no element of $N/a$ belongs to 2-circuit and odd circuit.

###### Proof.

Since $M(K_{3,3})$ is a bipartite graph, it contain only circuits with even
length. On contrary, let $x_{1}$ be an element of $N/a$ belongs to both
2-circuit and odd circuit. Suppose $\\{x_{1},x\\}$ is a 2-circuit and
$C_{1}=\\{x_{1},y_{1},y_{2},\cdots y_{k}\\}$ is an odd circuit, where $k$ is
an even integer. Then $C_{2}=\\{x,y_{1},y_{2},\cdots y_{k}\\}$ is also a
circuit of $N/a$. Then $D_{1}=\\{x_{1},y_{1},y_{2},\cdots y_{k},a\\}$ and
$D_{2}=\\{x,y_{1},y_{2},\cdots y_{k},a\\}$ are circuits of $N$ otherwise
$N\backslash a$ contains odd circuit, a contradiction to $N\backslash a$ is
bipartite. Suppose $D_{1}$ and $D_{2}$ are circuits of $N$. Then
$D_{1}\triangle D_{2}=\\{x_{1},x\\}$ is a circuit in $N$ and also in
$N\backslash a\cong M(K_{3,3})$, a contradiction. Thus no element of $N/a$
lies in a 2-circuit as well as in an odd circuit. ∎

In this paper, we aim to find the forbidden minors for the class
$\mathcal{M}_{3}$ and, we also intend to give an alternative proof for the
forbidden minor characterization of the class $\mathcal{M}_{2}$. By Theorem
1.1, $M(G_{2})$ is a forbidden minor for the class $\mathcal{M}_{2}.$
Therefore, by Lemma 2.3, $\tilde{M}({G_{2}})$ is a forbidden minor for the
class $\mathcal{M}_{3}$, where $\tilde{M}({G_{2}})$ is an extension of $G_{2}$
by single element. Thus it is sufficient, if we consider the graphic quotients
$M(K_{3,3})$ which avoids ${\tilde{M}({G_{2}})}$ as a minor.

We now find quotient for $M(K_{3,3})$.

######  Lemma 3.5.

Every graphic quotient of $M(K_{3,3})$ obtained via binary extension and
without containing a minor isomorphic to $\tilde{M}({G_{2}})$ is isomorphic to
the circuit matroid of $H_{i}$ for some $i\in\\{7,8,9,10,11\\}$, where $H_{i}$
is the graph as shown in Figure 7, for $i=7,8,9,10,11$.

$H_{7}$$H_{8}$$H_{9}$$H_{10}$$H_{11}$ Figure 7. Quotients of $M(K_{3,3})$

###### Proof.

Let $N$ be a binary matroid and $a\in E(N)$ such that $N\backslash a\cong
M(K_{3,3})$ and $N/a$ is graphic. Suppose $N/a=M(G)$ for some connected graph
$G$. Assume that $M(G)$ does not contain a $\tilde{M}(G_{2})$ as a minor. If
$a$ is a loop or coloop of $N,$ then $N\backslash a=N/a=K_{3,3}$. Thus $G\cong
H_{7}$.

Suppose $a$ is not a loop or a coloop. Since the graph $K_{3,3}$ has 6
vertices and 9 edges, $r(N)=5$ and $|E(N)|=10$. Thus $r(N/a)=4$ and
$|E(N/a)|=9$. Hence $N/a$ corresponds to a graph $G$ on 5 vertices and 9
edges. By Lemma 3.1(1) and (4), $G$ contains at most two block one of which is
a loop and $G$ does not contain 2-edge cut. Suppose $G$ is a simple graph. As
$G$ is 2-connected, by Harary ([5], Pg. 217), $H_{8}$ is only 2-connected
simple graph as shown in Figure 7. Thus $G\cong H_{8}$.

Suppose $G$ is not a simple graph. Then $G$ contains a loop or 2-cycle. By
Lemma 3.1[1], $G$ is 2-connected, or $G$ can be obtained by adding one loop or
parallel edges to 2-connected or both. Thus there are the following cases.
(i). $G$ contains either a loop or a 2-cycle. (ii). $G$ contains either a loop
and a 2-cycle or two 2-cycles. (iii). $G$ contains a loop and two 2-cycles or
three 2-cycle. (iv) $G$ contains a loop and three 2-cycles or four 2-cycles.
(v) $G$ contains a loop and four 2-cycles or at least five 2-cycles. We
consider all these cases one by one.

Case (i). Suppose $G$ contains either one loop or one 2-cycle.

Then $G$ can be obtained by adding a loop or a parallel edge to a 2-connected
simple graph on $5$ vertices and $8$ edges. By Harary ([5],Pg 217), there are
two non-isomorphic simple graphs $A_{i}$ and $A_{ii}$ on $5$ vertices and $8$
as shown in Figure 8.

$A_{i}$$A_{ii}$ Figure 8. Non-Isomorphic Simple Graphs on $5$ vertices and $8$
edges

Suppose $G$ is obtained from $A_{i}$ by adding a loop. Then $G$ contains a
2-edge cut, by Lemma 3.1 (4), which is a contradiction. Hence $G$ is obtained
from $A_{i}$ by adding a 2-cycle such that $G$ does not contain a 2-edge cut.
Then $M(G)\cong{M(\tilde{G_{2}})},$ a contradiction. Hence we discard $A_{i}$.

If $G$ is obtained from $A_{ii}$ by adding a loop, then $G\cong H_{9}$ or
$G\cong H_{10}$ shown in Figure 7. Suppose $G$ is obtained from $A_{ii}$ by
adding a edge parallel to some edge of $A_{ii}.$ Then either
$M(G)\cong\tilde{M}({G_{2}})$ or by Lemma 3.4, $N\backslash a$ contains a
$3$-circuit or 2-circuit, which is a contradiction. Hence we discard it.

Case (ii). Suppose $G$ contains either a loop and a 2-cycle or two 2-cycles.

$G$ can be obtained from a 2-connected simple graph on $5$ vertices and $7$
edges by adding a loop and a parallel edge or $2$ parallel edges. By Harary
([5], Pg 217), there are three non-isomorphic 2-connected simple graphs
$A_{iii}$, $A_{iv}$, and $A_{v}$ on 5 vertices and 7 edges as shown in Figure
9.

$A_{iii}$$A_{iv}$$A_{v}$ Figure 9. Non-Isomorphic Simple Graphs on $5$
vertices and $7$ edges

The graph $A_{v}$ contains three 2-edge cuts. Therefore, adding a loop and a
parallel edge or two parallel edges to $A_{v}$ still contains a 2-edge cut.
Hence we discard $A_{v}$. If $G$ is obtained from $A_{iii}$ by adding a loop
and a parallel edge, then $G$ contains a 2-edge cut. Suppose $G$ is obtained
from $A_{iii}$ by adding two parallel edges such that no 2-edge cut is there
in $G$. Then we get a contradiction by Lemma 3.4. Thus $G$ can not be obtained
from $A_{iii}$. If $G$ is obtained from $A_{iv}$ by adding a loop and a
parallel edge or two parallel edges such that $G$ does not contain 2-edge,
then $M(G)\cong{\tilde{M}({G_{2}})}$. Thus $G$ can not be obtained from
$A_{iv}$.

Case-(iii) If $G$ contains either a loop and two 2-cycles or three 2-cycles.

Then $G$ is obtained from a 2-connected simple graph on $5$ vertex and $6$
edges. By Harary ([5], Pg 217), there are two non-isomorphic 2-connected
simple graphs on $5$ vertices and $6$ edges as shown in Figure 10.

$A_{vi}$$A_{vii}$ Figure 10. Non-Isomorphic 2-Connected Graphs on 5 Vertices
and 6 Edges

If $G$ is obtained from $A_{vi}$ or $A_{vii}$ by adding a loop and two
parallel edges, then $G$ contains a 2-edge cut, which is a contradiction by
Lemma 3.1. Suppose $G$ obtained from $A_{vi}$ by adding three parallel edges
such that $G$ does not contain a 2-edge cut. Then $G\cong a_{i}$ or $G\cong
a_{ii}$ where $a_{i}$, $a_{ii}$ are shown in Figure 11. By Lemma 3.4, we
discard both the graphs $a_{i}$ and $a_{ii}$.

$a_{i}$$a_{ii}$$a_{iii}$$a_{iv}$ Figure 11. Graphs Obtained from $A_{vi}$,
$A_{vii}$ and From a cycle on 5 Vertices

Suppose $G$ is obtained from $A_{vii}$ by adding three parallel edges such
that $G$ does not contain 2-edge cut then $G\cong H_{11}$ or $G\cong a_{iv}$,
where $a_{iv}$ is shown in Figure 11. Suppose $G\cong a_{iv}$, since due to
cycles of $G$, $N\backslash a$ does not contain circuit with 6 elements, thus
$N\backslash a\ncong K_{3,3}$. Hence $G\ncong a_{iv}$.

Case-(iv) If $G$ contains either a loop and three pairs of parallel edges or
four pairs of parallel edges.

Then $G$ is obtained from a 2-connected simple graph on $5$ vertices and $5$
edges by adding a loop and three parallel edges or four parallel edges. By
Harary ([5], Pg 216), a cycle on $5$ vertices is the only a 2-connected graph
on $5$ vertices and $5$ edges. Thus $G$ is obtained by adding a loop and three
parallel edges such that $G$ does not contain a 2-edge cut, but there is no
graph without a 2-edge cut. Suppose $G$ is obtained from a cycle on $5$
vertices by adding four parallel edges such that it does not contain a 2-edge
cut. Then $a_{iii}$ is the only graph with this condition, where $a_{iii}$ is
a graph shown in Figure 11. By Lemma 3.4, $G\ncong a_{iii}$.

Case (v) If $G$ contains a loop and four pairs of parallel edges or five pairs
of parallel edges.

Then $G$ is obtained from a 2-connected simple graph on $5$ vertices and four
edges. By Harary ([5], Pg 216), there is no 2-connected simple graph on $5$
vertices and $4$ edges.

Therefore $G$ is isomorphic to $H_{i}$, for some $i\in\\{7,8,9,10,11\\}$. ∎

##  4\. Forbidden Minors for the class $\mathcal{M}_{2}$

This section gives alternative proof for the forbidden minor characterization
of the class $\mathcal{M}_{2}$ using the results obtained from the last two
sections. Recall that $\mathcal{M}_{k}$ is the class of graphic matroid whose
splitting with respect to any set of $k$-elements is cographic and
$\mathcal{F}=\\{F_{7},F^{*}_{7},M(K_{5}),M(K_{3,3})\\}.$

We need the following lemmas, which follow easily from the definition of the
splitting operation.

######  Lemma 4.1.

Let $M$ be a binary matroid such that it contains more than two 2-circuits.
Then $M_{T}$ will contain at least one 2-circuit for any $T\subseteq E(M)$
with $|T|=2$.

######  Lemma 4.2.

If $M(G)$ is a graphic matroid and contains a loop, then $M(G)_{T}$ is graphic
with $|T|=2$ or includes a loop.

######  Lemma 4.3.

Let M(G) be a graphic matroid such that it contains two adjacent 2-circuits.
Then $M(G)_{T}$ is graphic for some $T\subseteq E(M)$ with $|T|=2$ or $M_{T}$
contains a 2-circuit.

Now, we give an alternate prove to Theorem 1.1. Here we restate the result
along with the graphs.

######  Theorem 4.4.

Let $M$ be a graphic matroid without containing a minor isomorphic to any
member of $\mathcal{T}_{2}$. Then $M\in\mathcal{M}_{2}$ if and only if $M$
does not contain a minor isomorphic to any one of the circuit matroids
$M(G_{1})$, $M(G_{2})$ and $M(G_{3})$, where $G_{1}$, $G_{2}$ and $G_{3}$ are
the graphs as shown in Figure 12.

$G_{1}$$G_{2}$$G_{3}$ Figure 12. Forbidden Minors for the Class
$\mathcal{M}_{2}$

###### Proof.

Let $M$ be a graphic matroid such that it contains a minor isomorphic to
$M(G_{i})$ for some $i\in\\{1,2,3\\}$. Then we can easily prove that $M_{T}$
is not cographic for some $T\subseteq E(M)$ and $|T|=2$.

Conversely, assume that $M$ avoids a minor isomorphic to $M(G_{i})$ for every
$i\in\\{1,2,3\\}$. Then we prove that $M\in\mathcal{M}_{2}.$ On contrary,
assume that $M\notin\mathcal{M}_{2}$. Then, by Lemma 2.1, $M$ contains a minor
isomorphic to $F\in\mathcal{F}$. Note that $\mathcal{M}_{1}$ is empty and $M$
does not contain a minor isomorphic to any element of $\mathcal{T}_{2}$.
Hence, by Lemma 2.3, $M$ has a minor $Q$ such that (i) $Q_{T}\cong F$, (ii)
$Q_{T}/T^{\prime}\cong F$ for $T^{\prime}\subseteq T$. By Lemma 2.4 and Lemma
2.5, $Q$ is without 2-cocircuit and a coloop. Therefore $Q$ is 2-minimal
matroid with respect to $F\in\mathcal{F}$. Thus, by Lemma 2.6, there exist a
binary matroid $N$ containing $a$ such that $N\backslash a\cong F$ and $Q=N/a$
or $Q$ is coextension of $N/a$ by one or two elements. Since $M$ is graphic,
$Q$ is also graphic. Let $Q=M(G)$ for some connected graph $G$. Since, by
Definition 1.1, $Q_{T}$ contains a 2-cocircuit as $|T|=2$, $Q_{T}\ncong F$.
Therefore $Q_{T}/T^{\prime}\cong F.$ Hence $Q$ is a coextension of $N/a$ by
one or two elements.

Case (i). Suppose $F=F_{7}^{*}$. Then $N\backslash a\cong F_{7}^{*}$ and , by
Lemma 3.2, $N/a\cong M(H_{1})$ or $N/a\cong M(H_{2}),$ where $H_{1}$ and
$H_{2}$ are the graphs shown in Figure 4. Therefore $G$ is a coextension of
$H_{1}$ or $H_{2}$ by one or two elements. Suppose $G$ is a coextension of
$H_{1}$ by an element. By Lemma 3.1 (4), $G$ can not contain a 2-edge cut. We
take coextensions of $H_{1}$ such that it does not contain a 2-edge cut. There
is only one non-isomorphic coextension $C_{1}$ of $H_{1}$ by an element as
shown in Figure 13. Since $C_{1}\cong G_{2}$, $G$ can not arise from $H_{1}$.

$C_{1}$ Figure 13. Coextensions of $H_{1}$ by one element.

Suppose $G$ arise from $H_{2}$. Then $G$ is a coextension of $H_{2}$ by one or
two elements. There are two non-isomorphic coextensions of $H_{2}$ by an
element as shown in Figure 14, such that it does not contain a 2-edge cut.

$C_{2}$$C_{3}$ Figure 14. Coextensions of $H_{2}$ by one element.

Here $C_{3}\cong G_{2}.$ Therefore $G\ncong C_{3}$. By Lemma 4.1, the
splitting of $M(C_{2})$ with respect to any two elements contains a 2-circuit.
Thus $(C_{2})_{T}\ncong F_{7}^{*}$ for any $T\in E(C_{2})$ with $|T|=2$ as
$F_{7}^{*}$ is a 3-connected matroid. Thus $G\ncong C_{2}$. Also there is no
coextension of $C_{2}$ by an element, which does not contain a 2-edge cut.
Hence, we discard $C_{2}$.

Case (ii). Suppose $F=F_{7}$. Then $N\backslash a\cong F_{7}$ and, by Lemma
3.2, $N/a\cong M(H_{3}),$ where $H_{3}$ is the graph as shown in Figure 4.
Therefore $G$ is a coextension of $M(H_{3})$ by one or two elements. Suppose
$G$ is a coextension of $H_{3}$ by an element. There are five
$C_{4},C_{5},C_{6},C_{7},C_{8}$ non-isomorphic coextensions of $M(H_{3})$ by
an element as shown in Figure 15. By Lemma 4.1, the splitting of the matroids
$M(C_{4})$, $M(C_{7})$ and $M(C_{8})$ contains a 2-circuit after splitting
with any two elements set. Also, there is no coextension of $C_{4}$, $C_{7}$
and $C_{8}$ by one element such that it does not contain a loop or 2-edge cut
or a minor isomorphic to $M(G_{1})$, $M(G_{2})$ or $M(G_{3})$. Hence we
discard coextensions of $C_{4}$, $C_{7}$ and $C_{8}$. By Lemma 4.2, splitting
of $M(C_{5})$ with respect to any two elements is either graphic or contains a
loop. Also coextension of $C_{5}$ by one element either contains a loop or a
minor isomorphic to $M(G_{2})$. Hence $G\ncong C_{5}$. Here $M(C_{6})\cong
M(G_{1})$. Hence $G\ncong C_{6}$.

$C_{4}$$C_{5}$$C_{6}$$C_{7}$$C_{8}$ Figure 15. Coextensions of $H_{3}$ by one
Element

Case (iii). Suppose $F=M(K_{5}).$ Then $N\backslash a\cong M(K_{5})$ and, by
Lemma 3.3, $N/a\cong M(H_{4})$, $N/a\cong M(H_{5})$ or $N/a\cong M(H_{6})$,
where $H_{4}$, $H_{5}$ and $H_{6}$ are the graphs shown in Figure 5. Suppose
$N/a\cong M(H_{4})$. Then $M(H_{4})_{T}\ncong M(K_{5})$ for any $T$ with
$|T|=2$. Thus we take coextension of $H_{4}$. Here all coextensions of $H_{4}$
by an element belongs to $\mathcal{T}_{2}$, hence we discard $H_{4}$. Suppose
$N/a\cong M(H_{5})$. Therefore $G$ is a coextension of $H_{5}$ by one or two
elements. There are seven coextensions of $H_{5}$ by an element shown in
Figure 16, without containing a minor isomorphic to $M(G_{1})$, $M(G_{2})$ and
$M(G_{3})$. Since $M(C_{i})$ contains a loop and at least two 2-circuits, the
splitting with respect to any two elements set $T$ will contain a loop or a
2-circuit for $i=9,10,\cdots,15$. Therefore we take coextensions of $C_{i}$
for $i=9,10,\cdots 15$ such that it does not contain a minor isomorphic to
$M(G_{1})$ or $M(G_{2})$ or $M(G_{3})$. Also, it does not contain a loop or
more than two 2-circuits. It is observed that there is no coextension with
these conditions. Hence we discard $H_{5}$. Suppose $N/a\cong M(H_{6})$. Then,
by using similar argument as above, we discard $H_{6}$.

$C_{9}$$C_{10}$$C_{11}$$C_{12}$$C_{13}$$C_{14}$$C_{15}$ Figure 16.
Coextensions of $H_{5}$ by one element

Case (iv). Suppose $F=M(K_{3,3})$. Then, by Lemma 3.5, $N/a\cong M(H_{i})$ for
$i=7,8,9,10,11$, where $H_{i}$ is the graph as shown in Figure 7, for
$i=7,8,9,10,11$.

Suppose $N/a\cong M(H_{7})$, then $M(H_{7})_{T}\ncong M(K_{3,3})$ for any $T$
with $|T|=2$, thus we take coextension of $H_{7}$, but all coextension of
$H_{7}$ belongs to $\mathcal{T}_{2}$. Hence we discard the graph $H_{7}$. Let
$N/a\cong M(H_{8})$. Then $G$ is a coextension of $H_{8}$ by one or two
elements. There are three coextensions of $H_{8}$ by an element as shown in
Figure 17, without containing a 2-edge cut. Here $M(C_{16})$ and $M(C_{17})$
contains a minor isomorphic to $M(G_{1})$ and $M(C_{18})$ contains a minor
isomorphic to $M(G_{3})$. Thus we discard these coextensions.

$C_{16}$$C_{17}$$C_{18}$ Figure 17. Coextensions of $H_{8}$ by one element

Let $N/a\cong M(H_{9})$. Thus we take the coextension of $H_{9}$ by one or two
elements. There is no coextension of $H_{9}$ by one element as well as by two
elements, such that it does not contain a loop, a 2-cocircuit or a minor
isomorphic to $M(G_{1})$, $M(G_{2})$ or $M(G_{3})$. Hence we discard $H_{9}$.

If $N/a\cong M(H_{10})$ then, $G$ is a coextension of $H_{10}$ by one or two
elements such that it does not contain 2-cocircuit or minor $M(G_{1})$,
$M(G_{2})$ or $M(G_{3})$. Such non-isomorphic coextensions of $H_{10}$ by one
element are shown in Figure 18.

$C_{19}$$C_{20}$ Figure 18. Coextensions of $H_{10}$ by one element

Here $C_{19}$ and $C_{20}$ contains a loop. Since
$M(C_{19})\in\mathcal{T}_{2}$, $G\ncong C_{19}$. By Lemma 4.2, the splitting
of $M(C_{20})$ contains a loop or its graphic. Hence we take coextensions by
$H_{10}$ by two elements such that it does not contain a loop, a 2-cocircuit
and a minor isomorphic to $M(G_{1})$, $M(G_{2})$ or $M(G_{3})$. It is observed
that there is no such coextension. Thus we discard $H_{10}$.

If $N/a\cong M(H_{11})$, then, we take coextensions of $H_{11}$ by one element
such that it does not contain 2-cocircuit and minor $M(G_{1})$, $M(G_{2})$ or
$M(G_{3})$. One can easily check that there is no such coextension. Hence we
discard $H_{11}$.

Therefore $M_{T}$ is cographic for any $T$ with $|T|=2$. Hence proved. ∎

##  5\. Forbidden-Minor Characterization of the class $\mathcal{M}_{3}$

In this section, we prove Theorem 1.3. We now first prove ’if part’ of Theorem
1.3 in the following proposition.

######  Proposition 5.1.

Let $M$ be a graphic matroid. If $M$ contains a minor isomorphic to any of the
matroids $M(\tilde{G_{1}})$, $M(\tilde{G_{3}})$ and $M(G_{i})$ for
$i=4,5,6,7$, then $M_{T}$ is not cographic for some $T\subseteq E(M)$ with
$|T|=3$, where $G_{i}$ is the graph as shown in Figure 19, for
$i=1,3,4,5,6,7.$

###### Proof.

Note that, by Theorem 1.1, $M(G_{1})$, $M(G_{2})$ and $M(G_{3})$ are the
forbidden minors for the class $\mathcal{M}_{2}$. For $k=1,3$, let
$\tilde{M}({G_{k}})$ be a matroid obtained by adding an element $z_{k}$ to
$M(G_{k})$. Then $\tilde{M}({G_{k}})\backslash z_{k}=M(G_{k})$. By Theorem
1.1, there is $T_{k}$ with $|T_{k}|=2$ such that $M(G_{k})_{T_{k}}$ is not a
cographic matroid. Let $T=T_{k}\cup z_{k}$. Then, by Lemma 2.2(ii),
$\tilde{M}({G_{k}})_{T}\backslash z_{k}\cong(\tilde{M}({G_{k}})\backslash
z_{k})_{T_{k}}\cong M(G_{k})_{T_{k}}\cong M(G_{k})_{T_{k}}$ is not cographic.
$\tilde{M}({G_{k}})_{T}$ is not cographic. Also $G_{2}$ is minor of $G_{5}$.

Suppose $M=M(G_{4})$ and $T=\\{x,y,z\\}$, where $x,y,z$ are as shown in the
graph $G_{4}$. Let $A_{4}$ be the standard matrix representation of $G_{4}$ as
follows:

$A_{4}=\left[\begin{array}[]{ccccccc}x&y&z&&&&\\\ 1&0&0&0&1&0&1\\\
0&1&0&0&1&1&0\\\ 0&0&0&1&1&1&1\end{array}\right].$ Then
$(A_{4})_{T}=\left[\begin{array}[]{ccccccc}x&y&z&&&&\\\ 1&0&0&0&1&0&1\\\
0&1&0&0&1&1&0\\\ 0&0&0&1&1&1&1\\\ 1&1&1&0&0&0&0\end{array}\right]$
Let $(A_{4})_{T}^{{}^{\prime}}$ be the matrix obtained by applying the row
transformations $R_{4}\implies R_{4}+(R_{1}+R_{2})$ and $R_{34}$. Then we have

$(A_{4})_{T}^{{}^{\prime}}=\left[\begin{array}[]{ccccccc}1&0&0&0&1&0&1\\\
0&1&0&0&1&1&0\\\ 0&0&1&0&0&1&1\\\ 0&0&0&1&1&1&1\end{array}\right]$

Since the vector matroid of $(A_{4})_{T}^{{}^{\prime}}$ is isomorphic to
$F_{7}^{*}$, $M(G_{4})_{T}\cong M[(A_{4})_{T}]\cong
M[(A_{4})_{T}^{{}^{\prime}}]\cong F_{7}^{*}$. By Theorem 2.1, $M(G_{4})_{T}$
is not cographic. Similarly, we can prove that $M(G_{5})_{T_{5}}\cong
F_{7}^{*}$, $M(G_{6})_{T_{6}}\cong M(K_{3,3})$ and $M(G_{7})_{T_{7}}\cong
M(K_{3,3})$ for $T_{i}=\\{x,y,z\\}$ , where $x,y,z$ are as shown in the graph
$G_{i}$ in Figure 19, for $i=5,6,7$.

Suppose $M$ contains a minor $N$ isomorphic to any of circuit matroids
$M(G_{k})$, $k=4,5,6,7$. Then $N_{T}$ is not cographic for some $T\subseteq
E(N)$ with $|T|=3$. Since $N$ is a minor of $M$, there exist subsets $T_{1}$
and $T_{2}$ of $E(M)$ such that $M\backslash T_{1}/T_{2}\cong N$. Then, by
repeated application of Lemma 2.2, we have $M_{T}\backslash
T_{1}/T_{2}\cong(M\backslash T_{1}/T_{2})_{T}\cong N_{T}$. As $N_{T}$ is not
cographic, $M_{T}$ is also not cographic. ∎

Now we prove the main theorem. For convenience, we restate the main theorem
here along with graphs.

######  Theorem 5.2.

Let $M$ be a graphic matroid without containing a minor isomorphic to any
member of the set $\mathcal{T}_{3}.$ Then $M\in\mathcal{M}_{3}$ if and only if
$M$ does not contain a minor isomorphic to any of the matroid
$\tilde{M}(G_{1})$, $\tilde{M}(G_{3})$, $M(G_{4})$, $M(G_{5})$, $M(G_{6})$ and
$M(G_{7})$, where $G_{i}$ is the graph as shown in Figure 19, for
$i=1,3,4,5,6,7$.

$G_{4}$$G_{5}$$G_{6}$$G_{7}$$G_{1}$$G_{3}$$x$$z$$y$$x$$y$$z$$z$$y$$x$$z$$x$$y$
Figure 19. Forbidden Minor for the Class $\mathcal{M}_{3}$

###### Proof.

If $M$ has a minor isomorphic to one of the circuit matroids
$\tilde{M}({G_{1}})$, and $\tilde{M}({G_{3}})$ and $M(G_{k})$ for $k=4,5,6,7$,
then $M_{T}$ is not cographic for some $T\in E(N)$ with $|T|=3$ by Proposition
5.1.

Conversely, assume that $M$ does not contain a minor isomorphic to any of the
circuit matroid $\tilde{M}({G_{1}}),$ $\tilde{M}({G_{3}})$ and $M(G_{k})$ for
$k=4,5,6,7$. Then we will prove that $M_{T}$ is cographic for any $T\subseteq
E(M)$ with $|T|=3$. On contrary, assume that $M_{T}$ is not cographic for some
$T\subseteq E(M)$ with $|T|=3$. Then, by Theorem 2.1 $M_{T}$, has a minor
isomorphic to $F\in\mathcal{F}$. Then, by Lemma 2.3, $M$ has a minor $Q$
containing T such that one of the following holds.

  1. (i).

$Q$ isomorphic to one of the circuit matroids $\tilde{M}({G_{1}}),$
$\tilde{M}({G_{2}})$ and $\tilde{M}({G_{3}}).$

  2. (ii).

$Q_{T}\cong F$ or $Q_{T}/T^{{}^{\prime}}\cong F$ for some
$T^{{}^{\prime}}\subseteq T$.

Note that the graph $G_{2}$ contains a minor isomorphic to the graph $G_{5}$.
If $Q$ is isomorphic to $\tilde{M}({G_{1}}),$ $\tilde{M}({G_{2}})$ and
$\tilde{M}({G_{3}}),$ then it is clear that $M$ contains a minor isomorphic to
$\tilde{M}({G_{1}})$, $\tilde{M}({G_{3}})$ or $M(G_{5})$, a contradiction.
Thus (i) does not hold. Suppose (ii) holds. By Lemma 2.4 and Lemma 2.5, assume
that $Q$ do not contain a 2-cocircuit and a coloop. Thus $Q$ is 3-minimal with
respect to $F$. Then, by Lemma 2.6, there exist a binary matroid $N$ such that
$N\backslash a\cong F$ and $N/a=Q$ or $Q$ is a coextension of $N/a$ by one,
two or three elements. If $M$ is graphic, then $Q$ and $N/a$ are also graphic.
Let $Q\cong M(G)$ for some connected graph $G.$ We assume that $G$ does not
contain a loop or 2-edge cut.

Case (i). Suppose $F=F_{7}^{*}$. Then $N\backslash a=F_{7}^{*}$ and, by Lemma
3.2, $N/a\cong M(H_{1})$ or $M(H_{2}),$ where $H_{1}$ and $H_{2}$ are the
graphs as shown in Figure 4. Here $H_{1}\cong G_{4}$ and $H_{2}\cong G_{5}$.
Thus $Q=N/a\cong M(G_{4})$ or $Q=N/a\cong M(G_{5})$. Hence $M$ contains a
minor isomorphic to $M(G_{4})$ or $M(G_{5})$, a contradiction.

Case (ii). Suppose $F=F_{7}$. Then $N\backslash a=F_{7}$ and, by Lemma 3.2,
$N/a\cong M(H_{3})$, where $H_{3}$ is the graph as shown in Figure 4. The
graph $H_{3}$ contain three pairs parallel edges and a loop. Therefore
$M(H_{3})_{T}$ contains at least one 2-circuit or a loop for any $T$ with
$|T|=3$. Therefore $M(H_{3})_{T}\ncong F_{7}$ and $Q\ncong M(H_{3})$. Hence
$Q$ is a coextension of $M(H_{3})$ by one, two or three elements. There are
five non-isomorphic coextension of $M(H_{3})$ as shown in Figure 15, without
containing 2-edge cut. The graphs $C_{4},$ $C_{7}$ and $C_{8}$ contains a
minor isomorphic to the graph $G_{5}$ and $C_{5}$ contains a minor isomorphic
to graph $G_{4}$. Therefore we discard them.

Let $Q=M(C_{6})$ or $Q$ is a coextension of $M(C_{6})$ by one or two elements.
Coextensions of $M(C_{6})$ by one or two elements contains 2-cocircuit or
$G_{5}$ as a minor, a contradiction. Hence $Q=M(C_{6})$. Since $C_{6}$ has two
2-circuits and eight edges whereas $F_{7}$ has seven edges, there is
$T\subseteq E(C_{6})$ with $|T|=3$ such that $M(C_{6})_{T}/x\cong F_{7}$ for
some $x\in T$. If a 2-circuit does not intersect $T$ or contained in $T$, then
it remains a 2-circuit in $M(C_{6})_{T}$. Thus $M(C_{6})_{T}/x\cong F_{7}$
contains a 2-circuit or a loop, a contradiction. Hence $T$ contains exactly
one edge from each 2-circuits of $C_{6}$. We assume that $x\in T$ does not
belong to any 2-circuit of $C_{6}$. Then there is triangle in $G$ containing
two edges from $T$ one of which is $x$. Then that 3-circuit of $M(C_{6})$ is
get preserved in $M(C_{6})_{T}$. Therefore $Q_{T}/x\cong F_{7}$ contains a
2-circuit, a contradiction.

Case (iii). Suppose $F=M(K_{5})$. Then $N\backslash a\cong M(K_{5})$ and, by
Lemma 3.3, $N/a\cong M(H_{4})$, $N/a\cong M(H_{5})$ or $N/a\cong M(H_{6})$,
where $H_{4}$, $H_{5}$ and $H_{6}$ are the graphs as shown in Figure 5. The
matroid $M(H_{4})$ does not give $M(K_{5})$ after splitting with respect to a
three elements set. Hence we take coextension of $M(H_{4})$, but coextension
of $M(H_{4})$ is a trivial minor for the class $\mathcal{M}_{2}$. Hence we
discard $M(H_{4})$. The matroid $M(H_{5})$ contains a minor isomorphic to
$M(G_{4})$. Hence $M$ can not be arise from $M(H_{5})$. The matroid $M(H_{6})$
contains a minor isomorphic to $M(G_{4})$, and hence $G$ not arise from
$H_{5}$ and $H_{6}$.

Case (iv). Suppose $F=M(K_{3,3})$. Then $N\backslash a\cong M(K_{3,3})$ and,
by Lemma 3.5, $N/a\cong M(H_{i})$, where $H_{i}$ is the graph shown in Figure
7, for $i=7,8,9,10,11$. The matroid $M(H_{7})$ belongs to $\mathcal{T}_{2}$.
Hence we discard the graph $H_{7}$. Note that $H_{8}\cong G_{6}$ and
$H_{11}=G_{7}$. The matroid $M(H_{i})$, for $i=9,10$ contains a minor
isomorphic to $M(G_{4})$. Therefore $M$ can not be arise from these matroid.

Thus from all the above cases, $M_{T}$ does not contain $F$ as a minor for any
$F\in\mathcal{F}$. Therefore $M_{T}$ is cographic and hence proved. ∎

## References

  * [1] Y. M. Borse, M. M. Shikare and K. V. Dalvi, Excluded-minors for the class of cographic splitting matroids, Ars Combin.  115 (2014), 219-237.
  * [2] Y. M. Borse, M. M. Shikare and Pirouz Naiyer, A characterization of graphic matroids which yield cographic splitting matroids,Ars Combin.  118 (2015), 357-366.
  * [3] H. Fleischner, Eulerian Graphs and Related Topics Part 1, Vol. 1, North Holland, Amsterdam , 1990.
  * [4] Ganesh Mundhe, On Connectivity and Graphicness of Binary Matroids Under Splitting Operation, Ph.D. Thesis, University of Pune, (2018).
  * [5] F. Harary, Graph Theory, Narosa Publishing House, New Delhi , 1988.
  * [6] T. T. Raghunathan, M. M. Shikare and B. N. Waphare, Splitting in a binary matroid, Discrete Math.  184 (1998), 267-271.
  * [7] M. M. Shikare and B. N. Waphare, Excluded-Minors for the class of graphic splitting matroids, Ars Combin. 97 (2010), 111-127.
  * [8] M. M. Shikare, Gh. Azadi, B. N. Waphare, Generalized splitting operation and its application, J. Indian Math. Soc. , 78, (2011), 145-154.
  * [9] M. M. Shikare, H. Azanchiler and B. N. Waphare, The cocircuits of splitting matroids, J. Indian Math. Soc. 74 No. 3-4 (2007), 185-202.
  * [10] J. G. Oxley, Matroid Theory, Second Edition, Oxford University Press, Oxford, 2011.


# Knowing Where to Look: A Planning-based Architecture
to Automate the Gaze Behavior of Social Robots*

Chinmaya Mishra1 and Gabriel Skantze2 *This project has received funding from
the European Union’s Framework Programme for Research and Innovation Horizon
2020 (2014-2020) under the Marie Sklodowska-Curie Grant Agreement No.
859588.1Chinmaya Mishra is an Associate Researcher and PhD Fellow at Furhat
Robotics, Stockholm<EMAIL_ADDRESS>Skantze is a
Professor at the Department of Speech Music and Hearing at KTH Royal Institute
of Technology, Stockholm and Co-founder at Furhat Robotics, Stockholm.
<EMAIL_ADDRESS>
###### Abstract

Gaze cues play an important role in human communication and are used to
coordinate turn-taking and joint attention, as well as to regulate intimacy.
In order to have fluent conversations with people, social robots need to
exhibit human-like gaze behavior. Previous Gaze Control Systems (GCS) in HRI
have automated robot gaze using data-driven or heuristic approaches. However,
these systems tend to be mainly reactive in nature. Planning the robot gaze
ahead of time could help in achieving more realistic gaze behavior and better
eye-head coordination. In this paper, we propose and implement a novel
planning-based GCS. We evaluate our system in a comparative within-subjects
user study (N=26) between a reactive system and our proposed system. The
results show that the users preferred the proposed system and that it was
significantly more interpretable and better at regulating intimacy.

©2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

##  I Introduction

Non-verbal cues play a crucial role in realizing effective communication in
Human-Human Interaction (HHI). Humans make use of many non-verbal cues such as
eye gaze, facial expressions, gestures, and prosody to convey meaning during
social interactions. Among these non-verbal cues, eye gaze cues are considered
to be especially important, as they are interpreted using dedicated and unique
hard-wired pathways in the brain [1]. Interpreting and conveying feelings and
intentions through eye gaze during a social interaction is central to HHI and
comes naturally to humans. During social interactions, gaze cues are used to
coordinate turn-taking [2], signal cognitive effort [3], and regulate intimacy
[4], among other things.

As social robots become increasingly available in society, they are expected
to be able to communicate using both verbal and non-verbal cues, similar to
humans. Research has shown that the robot’s gaze behavior plays a similarly
important role in Human-Robot Interaction (HRI) [5, 6]. Consequently,
researchers have designed architectures to control the gaze behaviors of
robots to explore the impact of social gaze in HRI and exploit the many uses
of gaze cues in social interactions [7, 8]. Most of these Gaze Control Systems
(GCS) have generally focused on modelling specific gaze cues such as gaze
aversion [9] or turn-taking [10].

Even though these GCS have achieved good results in emulating human-like gaze
behaviors in robots, a common limitation is that they remain mainly reactive
in nature. Although some of these systems do plan the gaze behavior for the
upcoming utterance at the onset of the utterance (e.g. [9]), the plan does not
get updated incrementally, and the plan does not really affect the gaze
behavior in the current moment. Another limitation of many systems is that
they are static, in the sense that they use fixed durations for gaze shifts.
For example, in [8], the gaze of the robot was fixed on the relevant target
for a duration of 1-5 seconds during the interaction, before moving to the
target with the lowest priority. In contrast, HHI involves a lot of planning.
Research has shown that gaze behavior is coordinated with the underlying
speech plan [11]. Depending on how long we plan to look at something, we
determine whether a quick glance would suffice or whether we need to move the
head and look. In this study, we focus on bringing a planning component into
GCS. More specifically, we address the following research question:

How can planning be used to generate better gaze behavior in HRI?

Our model plans the priority for each potential gaze target (e.g., users or
objects) in the environment incrementally (frame-by-frame) for a future
rolling time window. At each time step, various events in the conversation
might update these priorities, resulting in an evolving gaze plan which
produces gaze behavior that is dynamic and differs in frequency and duration
based on the state of the conversation. This planning allows the robot to
better coordinate eye and head movements, since it is possible to compute for
how long the robot will be attending a specific target in advance. In
addition, the robot can better plan when to avert the gaze to regulate
intimacy. The model is comprehensive in that it encompasses turn-taking, gaze
aversion (GA), referential gaze (RG) and responsive joint attention (RJA). We
evaluate the proposed model and compare it with a purely reactive heuristic
model, using a multi-party interaction scenario where the robot head Furhat
collaborates with two human players to sort a deck of cards in the right
order.

The main contributions of this paper are:

  * •

A comprehensive gaze control architecture that accounts for turn-taking, joint
attention and intimacy regulation in HRI, using a planning-based approach.

  * •

A novel approach to make use of the planned gaze behaviors to coordinate eye-
head movements of the robot.

  * •

An evaluation done in a complex multi-party HRI setting, which shows that this
system is better than a reactive version of the same system.

##  II Related Work

Modelling approaches in HRI for GCS can be broadly categorized into data-
driven approaches (e.g., [9, 10]), where HHI gaze data are used to build
models that can predict the gaze of the robot, and heuristic approaches, where
the gaze of the robot is controlled using a set of rules, based on findings
from HHI literature (e.g., [8, 12]).

Turn-taking refers to the process in which interlocutors coordinate and take
turns while speaking [13, 14]. [10] implemented data-driven models for role-
signalling, turn-taking and topic signalling gaze mechanisms based on the
formal observations of human communication. It was found that the subjects
were able to correctly interpret the turn-yielding signals by the robot 99% of
the time.

Gaze aversion is the intentional shifting of the gaze away from the
interaction partner during a conversation. Several studies have focused on
modelling this and evaluate human perception of it. [9] lists three primary
functions of gaze aversion: cognitive, intimacy regulation and turn-taking.
They used human gaze aversion data to model gaze aversion on a NAO robot and
found that gaze aversion by the robot was perceived to be intentional. [15]
implemented a GCS with four possible states to model mutual gaze and gaze
aversion using the captured gaze data of the participants. [16] used a
heuristic model to generate appropriate gaze aversion along with verbal
fillers as turn-taking cues.

When the interlocutors attend to a common target during a social interaction
(and are mutually aware of that), it is generally referred to as joint
attention. Joint attention is usually split into two categories: responding to
joint attention (RJA) and initiating joint attention (IJA) [17]. IJA refers to
when the interlocutor initiates a joint attention by directing the gaze at the
referent (also known as referential gaze). RJA refers to the act of following
others’ gaze direction and interpreting the need to share focus on a common
point. [12] proposed and implemented a GCS (Sceneflow) that made use of the
bi-directional and multimodal aspects of speech. The model implemented
referential gaze, RJA and mutual gaze as a hierarchical and concurrent state-
chart-based architecture. [8] focused on the effects that RJA has on people’s
perception of social robots. The GCS was divided into two layers: Proactive
Gaze Layer and Responsive Gaze Layer which modelled RJA and IJA respectively
with each module having a predefined priority used to suppress gaze shifts
issued by other modules with lower priorities.

Several studies have also developed models of human gaze behavior which could
then be transferred to robots. [18] used a supervised learning approach to
predict eye gaze direction or head orientation of the participant in multi-
party open world dialogues. A recent study modelled the robot’s gaze behavior
using concepts from animation instead of grounding it in human psychomotor
behavior [19].

Even though data-driven approaches are potentially able to provide a more
accurate representation of human gaze behavior as compared to heuristic
models, they are restricted by their dependence on collecting appropriate gaze
data. It is also unclear how well they generalize to settings different from
that in which the data was recorded. Another problem is that the speakers’
intentions are not available in the data, which makes it difficult for data-
driven models to account for planning.

Another aspect of gaze modelling is the coordination between eye and head
movements during gaze shifts. Previous studies have found that human eye and
head movements are coordinated based on the target angles to realize gaze
shifts [20, 21]. [22] defined eye-head angle relationships to control the eye-
head movements of a virtual avatar during gaze shifts. [23] and [24] tried to
model realistic eye-head coordination on humanoid robots. To the best of our
knowledge, ours is the first work that incorporates a planning component into
a GCS to coordinate the eye-head movement during gaze shifts and regulate
intimacy during a conversation.

TABLE I: Review of Gaze Models in HRI.  Paper | Multi-party | Modelling | Planning | Gaze Aversion | RJA111 | Referential Gaze | Turn-Taking
---|---|---|---|---|---|---|---
Mutlu et al. 2012[10] | Yes | Data-driven | No | No | No | No | Yes
Andrist et al. 2014[9] | No | Data-driven | No | Yes | No | No | Yes
Mehlmann et al. 2014[12] | No | Heuristic | No | Yes | Yes | Yes | Yes
Zaraki et al. 2014[25] | Yes | Heuristic | No | No | No | No | Yes
Andrist et al. 2015[26] | No | Data-driven | No | No | Yes | No | Yes
Nakano et al. 2015[27] | Yes | Data-driven | No | No | No | No | Yes
Lehmann et al. 2017[28] | No | Data-driven | No | No | No | No | Yes
Zhang et al. 2017[29] | No | Heuristic | No | Yes | No | No | Yes
Zhong et al. 2019[15] | No | Heuristic | No | Yes | No | No | Yes
Pereira et al. 2019[8] | No | Heuristic | No | Yes | Yes | Yes | Yes
Lala et al. 2019[16] | No | Heuristic | No | Yes | No | No | Yes
Stefanov et al. 2019[18] | Yes | Data-driven | No | No | Yes | Yes | Yes
Pan et al. 2020[19] | Yes | Heuristic | No | No | No | No | Yes
Proposed Gaze model | Yes | Heuristic | Yes | Yes | Yes | Yes | Yes
1 Responsive Joint Attention. This is set to “Yes” if the GCS was capable of
responding to user’s referential gaze, verbal references to objects/
interlocutors/ locations, movement of task object etc.

We summarize these previous works on modelling GCS in Table I. Planning here
refers to the ability of a GCS to make use of the planned gaze behavior and
the executed gaze behavior to adjust the current gaze behavior. As can be
seen, our proposed model is unique in its comprehensiveness and its use of
planning to control the gaze behavior of the robot.

##  III Test-bed: Card Game

Our GCS was tested with the Card Game scenario, which is a test-bed
specifically designed for studying multi-party interactions involving joint
attention to objects [30]. The Card Game setup consists of a Furhat robot
[31], a touchscreen and up to two players, as seen in Fig. 1. A set of cards
are shown on the touchscreen and the task is to sort the cards based on some
criterion. For example, the task could be to order a set of animals from
slowest to fastest based on their running speeds. Furhat and the players then
collaborate with each other to arrange the cards in the right order by moving
them on the touchscreen.

Figure 1: Third person view of the Card Game setup

During the game, players are encouraged to discuss among each other and with
Furhat to reach a solution. Furhat’s arguments are based on a randomized
belief model, which means that the players have to choose whether they trust
Furhat’s beliefs or not. This results in a fairly free form of multi-party
conversation, and therefore constitutes a good test-bed for studying turn-
taking, joint attention and gaze aversions. When players look at or move a
card, Furhat can display RJA behavior and when Furhat talks about the cards or
the game, it can generate referential gaze.

##  IV A Comprehensive Gaze Control Architecture

Figure 2: Overview of the proposed Gaze Control System

Fig. 2 shows the overall architecture of the GCS and how it is integrated. The
Robot Platform consists of Furhat’s output interfaces (projector, neck servo
motors, etc.), input devices (microphone, camera, touchscreen, etc.), as well
as the software modules for automatic speech recognition (ASR), text-to-speech
synthesis (TTS), face tracking, etc. All the sensory inputs, modules and
actuators in the Robot Platform are mediated by the Event System. The Gaze
Planner subscribes to high-level events, such as the position of the user,
speech input, and location of objects on the touchscreen, to generate a Gaze
Plan. This plan is then used by the Gaze Controller, to generate events that
make the robot move the eyes and turn the head. Interactions are implemented
using the Skill API, with which all the interaction specific details are
defined, such as the utterances of the robot, its facial expressions and head
gestures, among others.

Algorithm 1 Outline of the Gaze Control System

for each time step do:

In Gaze Planner:

updateTargets($GP$) $\triangleright$ Add/Remove $\mathcal{T}_{i}$

for each new event $E$ do

when $E$ is RobotSpeaking

checkPauses($GP$) $\triangleright$ see IV-B

checkTurnYielding($GP$) $\triangleright$ see IV-B

checkReferentialGaze($GP$) $\triangleright$ see IV-C

when $E$ is TargetsMoved

attendTarget($GP$) $\triangleright$ see IV-C

when $E$ is UserSpeaking

checkRJA($GP$) $\triangleright$ see IV-C

attendSpeaker($GP$) $\triangleright$ see IV-B

when $E$ is RobotListening

attendUser($GP$) $\triangleright$ see IV-B

checkIntimacyRegulation($GP$) $\triangleright$ see IV-D

In Gaze Controller: $\triangleright$ see IV-E

$GP_{c}$ = summarize($GP$)

$\mathcal{T}_{c},slack$ = getTarget($GP_{c}$)

headAngle = getHeadAngle($\mathcal{T}_{c},slack$)

setRobotEyes($\mathcal{T}_{c}$)

setRobotNeck(headAngle)

shift($GP$)

Algorithm 1 provides an overview of how the GCS works. During the course of an
interaction, the Gaze Planner identifies and maintains a set of gaze targets
($\mathcal{T}_{i}$, $i\in[1\mathinner{\ldotp\ldotp}n]$) along with their
current locations in real-time. These gaze targets could be of different
types, such as users, task objects or the environment. The GCS continuously
monitors the gaze targets to add new targets or remove targets as necessary.

We introduce a priority score $\mathcal{P}\in[0,1]$, which determines the
priority with which the GCS should be looking at a specific gaze target. The
default priority is always 0. The Gaze Planner maintains a Gaze Plan ($GP$)
which is used by the Gaze Controller to decide which gaze target to look at
over a duration of time into the future. The GP stores the priority
$\mathcal{P}_{i,j}$ for each target $\mathcal{T}_{i}$ at each future time
frame $j$, with $j=0$ being the immediate next time step in the future. We use
a time resolution of 200ms for the plan, i.e., each time frame is 200ms long.

As can be seen in Algorithm 1, at each time step, the Gaze Planner listens to
events and updates the relevant $\mathcal{P}_{i,j}$ values, as will be
described in detail in the following sections. The relative priorities and
specific durations chosen in this paper have either been obtained from
literature or iteratively obtained after running the architecture for
different scenarios. Thus, we acknowledge that these parameters are somewhat
arbitrary, and that more optimal values can very likely be found. It is also
possible to generate different robot gaze behaviors (e.g. introvert vs.
extrovert) by tweaking the parameters. We leave this for future work.

At each time step, the Gaze Controller summarizes the current Gaze Plan,
$GP_{c}$, by calculating the list of final gaze targets for the next 2 seconds
into the future (10 time steps). The final gaze targets ($\mathcal{T}_{f,j}$)
are calculated as the target that has the highest priority value in each frame
$j$ of the $GP$:

$\mathcal{T}_{f,j}=\mathcal{T}_{n},\underset{n}{\arg\max}(\mathcal{P}_{n,j})$
(1)

The current gaze target, $\mathcal{T}_{c}$, is then equal to the immediate
next final target, $\mathcal{T}_{f,0}$. As will be described in Section IV-E,
the rest of the $GP_{c}$ is used to calculate the $slack$ value for the head
movement, to achieve natural eye-head coordination.

After the Gaze Controller has executed the gaze and head movements for that
time step, the $GP$ is shifted one step, so that
$\mathcal{P}_{i,j}\leftarrow\mathcal{P}_{i,j+1}$. Since the updates to the
$GP$ are done at each time step, it is possible for the Gaze Planner to
overwrite $\mathcal{P}$ values in the plan, which makes it possible to
dynamically update the plan depending on the events that occur during an
interaction.

Fig. 3 shows an example of how the GCS works. Let us consider a scenario where
a single user is playing the “Animal speed” Card Game, and a card with Zebra
is being discussed. The $\mathcal{P}$ for each $\mathcal{T}$ in the game is
plotted below the speech boxes. “Final Target” shows the calculated
$\mathcal{T}_{f}$ for the entire example interaction. In the following
subsections, we will use this example to discuss the various components of our
GCS in detail.

Figure 3: An example of gaze planning done by our GCS.(A) shows the plan at
onset of the utterance $t_{0}$ and (B) shows the updated plan at time step
$t_{1}$. The shaded parts show the already executed plan and the non-shaded
part show the plan at the current time step. Grey speech boxes denote that the
event is yet to take place.

###  IV-A Environment

As can be seen in Fig. 3, when the $\mathcal{P}$ value for all gaze targets in
the plan are 0, the final gaze target is defaulted to the environment (Env).
Thus, when the user is given a low priority (e.g., due to gaze aversion) and
no other target is given priority, the robot will gaze away from the user. [9]
found that the distribution of eye gaze at various regions in the environment
depended on the type of gaze aversion being performed. However, to keep the
model simple, we randomly select a location in the area around the currently
addressed user’s face as the location for the environment gaze target.

###  IV-B Turn-taking

At the onset of a robot utterance, the Gaze Planner receives an event from the
TTS system which gives information about the entire utterance text, as well as
the phonetic transcription with precise timing information. This information
can be used to plan the robot’s gaze behavior related to speech production and
turn-taking (as well as referential gaze, as described in the next section).
During the course of the utterance (the $RobotSpeaking$ event), the
$\mathcal{P}$ values of the currently addressed users are set to 0.3 which
results in the robot looking at the user during the utterance, in the absence
of other gaze targets with a higher $\mathcal{P}$ value. This can be seen at
the beginning of the Gaze Plan ($t_{0}$) in Fig. 3A. This emulates mutual
gaze/ individual gaze behavior where the speaker looks at the listener [7].

Speakers tend to avert their gaze to signal that they are thinking or will
hold the conversational floor [9]. The Gaze Planner calculates pause durations
in the utterances it is about to speak (using the phoneme timings). If the
pause duration is greater than 800ms, the $\mathcal{P}$ of the addressed users
are set to 0 for that duration and the environment becomes the
$\mathcal{T}_{f}$ resulting in a turn-holding Gaze Aversion as seen in Fig.
3A.

By default, the robot will always hold the floor unless the $yielding$ flag in
the $RobotSpeaking$ event is set to true. This can be controlled through the
Skill API (per default, $yielding$ is set to true in case of a question). When
$yielding$ is set to true, the $\mathcal{P}$ values of the currently addressed
user targets are set to 0.9, 1000ms before the end of the utterance. This
results in a turn-yielding gaze cue [7] as can be seen in Fig. 3A when the
robot is asking a question. In case $yielding$ is set to false, the
$\mathcal{P}$ of the addressed users are set to 0 about 2000ms before the end
of the utterance where we do not want the user to barge-in, and gaze aversion
is a clear turn-holding cue [14].

When the robot is not speaking and instead listening to the user (the
$RobotListening$ event), the $\mathcal{P}$ of the addressed users are set to
0.4 for the duration of the listening event. This enables the robot to keep
looking at the user unless there is some higher-priority target. When a user
starts to speak (the $UserSpeaking$ event), the $\mathcal{P}$ of that specific
user target is increased to 0.6. In a multi-party setting, the array
microphone of the robot can be used to sense the speech direction, and thereby
attribute the speech onset to the right user. This helps in directing the gaze
of the robot to the active speaker and is in line with the findings in [32],
where it was found that the listeners always tend to spend the most time
looking at the current speaker in multi-party settings.

###  IV-C Joint Attention

In the Card Game skill, the locations of the cards on the touchscreen and
their order are being tracked as task object gaze targets. The $\mathcal{P}$
of the task objects can be raised if Furhat or a user talks about an object,
or engages in joint attention in some other way. We do a keyword matching at
the onset of the robot utterance (the $RobotSpeaking$ event), to identify any
references to a task object. If so, the $\mathcal{P}$ value of that task
object is set to 0.9, 1000ms before the specific word is supposed to be spoken
(timings are obtained from the TTS system) in order to generate referential
gaze. This corresponds to the finding from studies of human communication,
where gaze is directed at the referent about 800-1000ms before the reference
is made [12]. The same can be seen in Fig. 3A, when the robot refers the Zebra
card.

When a task object gaze target (i.e., a card on the touchscreen) is moved, the
Gaze Planner sets gaze target’s $\mathcal{P}$ to 1 for 2000ms which results in
a responsive joint attention (RJA) and Furhat’s gaze follows the card that is
being moved. The current system is not capable of identifying and tracking
objects other than the touchscreen locations. When Furhat is listening to user
speech (the $UserSpeaking$ event), we also do a keyword matching on the
continuous ASR output to check for any references to the task objects. If a
match is found, the corresponding task object’s $\mathcal{P}$ is set to 0.7
(for a period of 800ms) after 200ms of the reference being heard. This is in
line with what was reported in [12] and is also a form of RJA. This can be
seen in Fig. 3B at $t_{1}$, when user refers the Zebra card.

###  IV-D Intimacy Regulation

Studies have shown that the preferred mutual gaze duration in interactions is
between 3-5 seconds before the interlocutor starts to feel uncomfortable [33].
To avoid this, the Gaze Planner also takes care of intimacy regulating gaze
aversion. At every time step (200ms), the Gaze Planner checks the $GP$ and
makes sure that the $\mathcal{T}_{c}$ is not assigned to a specific user for a
duration longer than 3-5 seconds. In example Fig. 3A there is a small period
of GA inserted when the planned final gaze target was User for a long duration
when listening to the user, which results in intimacy regulating gaze
aversions.

###  IV-E Eye-Head Coordination

While most of the previous works (see section II) have made use of the target
angle to coordinate the eye and head movements during gaze shifts, we propose
that the planned duration of gaze also plays a role in determining the head
and eye movements. If an agent knows that the gaze is planned to be directed
at a specific location for a longer period of time, then it can move both the
eyes and the head towards that target immediately. On the other hand, if the
planned gaze duration is very short, the gaze shift should be done using only
the eyes (or with little head rotation). Otherwise, rapidly shifting gaze
targets could result in jerky head movements. We can mitigate this problem
thanks to the planning approach of our GCS. Additionally, this allows the GCS
to take the robot’s intention into account when planning the gaze behavior. To
the best of our knowledge, this has not been addressed in any previous GCS.

In our GCS, we introduce a control variable named $slack$ which is the angle
by which the head direction is allowed to deviate from the eye gaze direction.
As seen in Algorithm 1, at every time step (200ms), the Gaze Controller
calculates the final gaze targets ($\mathcal{T}_{f}$) for 2 seconds into the
future and summarises them in a list $GP_{c}$. The current gaze target
($\mathcal{T}_{c}$) is the first element in the $GP_{c}$. $slack$ calculation
uses the frequency of the same gaze target in the final gaze plan as per
equation:

$slack=max(48-(sameTargetFreq*6),0)$ (2)

$sameTargetFreq$ is the duration of time the gaze is to be directed at a
specific target. It is calculated as the frequency of having the same target
as the $\mathcal{T}_{f}$ within a future window of 2s. This determines whether
the gaze should be directed using just the eyes or using both the eyes and the
head. For example, as in Fig. 3A, it can be seen that at $t_{0}$, the final
target is planned to be User for a long duration. Thus, the $slack$ value is
set to 0, and the head direction is fully aligned with the eyes. In Fig. 3B,
at $t_{1}$, the gaze duration planned at the Zebra card is very short so the
$slack$ value is set to 48. This means that only eye gaze is directed at the
Zebra card for a quick glance. The value 48 has been iteratively obtained.

Figure 4: An example showing the differences in eye and head movements when
looking at a target depending on the $slack$ values.

Fig. 4 shows an example of how $slack$ is used in coordinating the eye and
head movements towards the gaze target. Since the neck movement takes some
time, and the eye movement is instantaneous, the Gaze Controller first moves
the eyes towards the gaze target and then the neck, while centering the eyes.

Sometimes, several gaze targets may have an equally high $\mathcal{P}$ value.
For example, in multi-party interactions, two users might be addressees and
would have an equally high $\mathcal{P}$ while the robot is speaking. In such
cases, it is natural for the speaker’s head to be directed somewhere in the
middle of the gaze targets, while the eye gaze shifts rapidly between each of
them [20, 21]. We model this behavior in our GCS by checking for any rapid
shifts between two or more targets for a future time window. If so, then at
every time step, the mid point between the $\mathcal{T}_{c}$ and the next
$\mathcal{T}_{f}$ is calculated and head is directed at that point.

##  V Experimental Evaluation

In order to evaluate if a GCS that takes the robot’s intention (future gaze
behavior) into account is perceived as better, we performed a user study to
compare our GCS’s performance to a purely reactive GCS.

###  V-A Experimental Setup & Procedure

We used the Card Game scenario described in section III for the experiments. A
camera was placed behind the participants so that it only captured Furhat’s
face and the touch screen.

There were two scenarios under which the participants played the Card Game:

  * •

Planned : Our GCS with planning.

  * •

Reactive : A purely reactive heuristic GCS similar to [8] was implemented and
used as a baseline for the comparative study. The gaze targets were chosen in
response to the events taking place in the Card Game (e.g., when the cards
were moved, when someone was speaking, etc.). The gaze of the robot was fixed
on one target for a duration of 1-5 seconds (same as the original work) before
moving to the next target.

Each session lasted approximately 30 minutes, during which 2 participants
played 2 games (1 from each scenario) together with Furhat. The experiments
followed a within-subjects design and the order of scenarios were alternated
between sessions. The participants were first guided to their seats in front
of the touchscreen and provided with a consent form. Then the researcher
briefed the participants about the goal of the study and the way the
experiment was going to be conducted. They were told that they would play two
games with different versions of the system, but the nature of these two
versions was not explained to them, and they were only referred to as scenario
1 and 2. Participants were encouraged to go through the questionnaire to have
a better grasp of what to look out for before starting the first game. After
each game, the participants filled out one part of the questionnaire. The
questionnaire had two 9-point likert scales placed under each question; one
for each scenario. The participants were asked to score the questions based on
how they perceived the interaction in terms of the question being asked. They
were asked to look for differences in the scenarios and make different
judgements where applicable. The participants were instructed not to discuss
the scenarios with each other before filling out the questionnaire. At the end
of the session, the participants were also asked to choose which of the two
interactions they preferred.

###  V-B Data Collection and Evaluation

We recruited 28 participants to take part in the user study (14 males and 14
females) with ages ranging between 18 and 51 (mean = 32.92, SD = 8.22), and
participants were paired up. The responses from 2 participants were removed
from the analysis, as they violated the instructions and discussed the
scenarios with each other prior to filling out the questionnaire. No prior
interaction with social robots was needed before participating in the
experiment. The experiments were conducted in English.

The questionnaire had 10 9-point Likert scale questions which were grouped
into 5 dimensions, as can be seen in Table II. As the goal of our study was to
to compare two GCSs, we selected the dimensions and questions based on aspects
that should be important for a good GCS. For each dimension, the mean score of
the responses to the individual questions in that dimension was calculated. We
refer to this as the dimension score. For a better GCS, we expected the
dimension scores to be high for all dimensions, except for the Intimacy
dimension, which should be lower, given how the questions were formulated. We
used the statement “Furhat kept staring at me too much” as a sign of bad
Intimacy regulation, since periodic GA while listening leads to making
speakers more comfortable and reduces negative perceptions [4]. While we use
the term Intimacy as a short label for this dimension, this question does not
of course capture all aspects of intimacy, but it was designed to be easy to
interpret for the participants.

At the end of the experiment, the participants were also asked (verbally)
which scenario they preferred, taking all factors into account.

TABLE II: Questionnaire used for evaluation Dimension |  Question
---|---
|  Furhat looked at the cards at the right time.
Awareness |  Furhat was aware of what was happening in the game.
|  I could interpret Furhat’s intention from its gaze.
Interpretation |  Furhat’s gaze helped me understand its instructions better.
|  I was able to understand when Furhat wanted me to speak.
Turn-taking |  I was able to understand when Furhat wanted to keep speaking.
|  I was able to understand when Furhat was talking to me.
|  Furhat’s gaze was human-like.
Human-likeness |  The coordination between eye and head movements seemed natural.
Intimacy |  Furhat kept staring at me too much.

##  VI Results

Fig. 5 shows the dimension scores of each dimension for both GCS versions,
based on the responses from the 26 participants. As our hypothesis was that
they would prefer the Planned version, we performed a one-tailed Wilcoxon
signed-rank test. Since we compared five dimensions, we set $\alpha=0.01$,
after Bonferroni correction. Significant results were obtained for
Interpretation (p = 0.007) and Intimacy (p = 0.0013). While the mean values
for Awareness and Human-Likeness were higher for the Planned version, the
differences were not statistically significant.

For the final preference question, 19 participants preferred the Planned
version, whereas 4 preferred the Reactive version, and 4 could not decide. We
found the results to be significat with p = 0.0002 and $\chi^{2}$ = 16.66.

Figure 5: The comparison between the responses obtained for the reactive
system and the proposed GCS. The grey bar in the box plot indicates the
median, the $\times$ denotes the mean, the boxes show the upper and lower
quartiles of the data. The bars on both ends of the vertical lines denote the
maximum and minimum values in the data. ** ($p<0.01$)

##  VII Discussion

The goal of our evaluation was to do a comparison between a purely reactive
GCS and the planning-based GCS proposed in this paper. We hypothesised that
using a GCS with planning can lead to improved perception of the robot’s gaze
behavior during the interaction. The results from the evaluation indicate that
our GCS was significantly more interpretable, had better intimacy regulation,
and was generally preferred over the reactive version.

When it comes to the dimensions of Awareness, Turn-taking and Human-likeness,
we did not find any significant differences. One possible explanation could be
that it might have been difficult for the participants to observe subtle gaze
behaviors while being engaged in playing a new game. Previous studies on turn-
taking models for conversational systems have shown that it is very hard for
the participants to judge subtle things like turn-taking while interacting
themselves [34]. This is also in line with the Load Theory [35], which says
that when there is a higher cognitive load, the selective attention
performance becomes poor. Another problem that was noticed during the
experiments was that the sound source localization on the robot was not always
working very well. This means that Furhat sometimes turned to the wrong
participant, which clearly could have affected the perception of the Turn-
taking dimension.

Another issue could be the novelty effect; most of the participants were
interacting with a social robot for the first time. Attention might have been
split in familiarizing themselves with the robot and its capabilities during
the first scenario, which could have impacted the ratings. A potential way of
mitigating this problem in future studies could be to let the participants
first do a test round where they familiarize themselves with the robot. A
potential follow-up study could be to show the recordings of the experiments
to third-party observers and let them compare the two versions. In doing so,
the participants would be able to solely focus on rating the robot’s gaze
during the interactions. [34] reported that third-party observers could easily
perceive differences between different turn-taking models, unlike the
participants who were engaged in the interaction.

It should also be noted that many of the parameters chosen for the model could
of course be further tuned. We can also envision a hybrid model, where certain
priority scores are being data-driven, and others are rule-driven.

##  VIII Conclusion

In this paper, we proposed and implemented a novel planning-based
comprehensive GCS to automate the gaze behavior of social robots. The system
is capable of planning the gaze behavior for a future rolling time window of
fixed length, and use this plan to coordinate the eye and head movements of
the robot taking the robot’s intention into account. We conducted a user study
to evaluate our GCS and compared it with a purely reactive GCS. The results
suggest that a GCS with such type of planning is perceived to be significantly
more interpretable and has better intimacy regulation. It was also found that
overall, our GCS was preferred over the reactive system when users were asked
to choose one. This shows that planning is an important aspect of gaze
control, which has not been considered in previous works.

## References

  * [1] N. J. Emery, “The eyes have it: the neuroethology, function and evolution of social gaze,” _Neuroscience & biobehavioral reviews_, vol. 24, no. 6, pp. 581–604, 2000.
  * [2] A. Kendon, “Some functions of gaze-direction in social interaction,” _Acta psychologica_ , vol. 26, pp. 22–63, 1967.
  * [3] M. Argyle and M. Cook, “Gaze and mutual gaze.” _British Journal of Psychiatry_ , vol. 165, p. 848–850, 1976.
  * [4] A. Abele, “Functions of gaze in social interaction: Communication and monitoring,” _Journal of Nonverbal Behavior_ , vol. 10, no. 2, pp. 83–101, 1986.
  * [5] A. Yamazaki, K. Yamazaki, Y. Kuno, M. Burdelski, M. Kawashima, and H. Kuzuoka, “Precision timing in human-robot interaction: coordination of head movement and utterance,” in _Proceedings of the SIGCHI conference on human factors in computing systems_ , 2008, pp. 131–140.
  * [6] M. Imai, T. Kanda, T. Ono, H. Ishiguro, and K. Mase, “Robot mediated round table: Analysis of the effect of robot’s gaze,” in _Proceedings. 11th IEEE International Workshop on Robot and Human Interactive Communication_. IEEE, 2002, pp. 411–416.
  * [7] H. Admoni and B. Scassellati, “Social eye gaze in human-robot interaction: a review,” _Journal of Human-Robot Interaction_ , vol. 6, no. 1, pp. 25–63, 2017.
  * [8] A. Pereira, C. Oertel, L. Fermoselle, J. Mendelson, and J. Gustafson, “Responsive joint attention in human-robot interaction,” in _Proceedings of the 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , IEEE. IEEE, 2019, pp. 1080–1087.
  * [9] S. Andrist, X. Z. Tan, M. Gleicher, and B. Mutlu, “Conversational gaze aversion for humanlike robots,” in _Proceedings of the 9th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_ , IEEE. IEEE, 2014, pp. 25–32.
  * [10] B. Mutlu, T. Kanda, J. Forlizzi, J. Hodgins, and H. Ishiguro, “Conversational gaze mechanisms for humanlike robots,” _ACM Transactions on Interactive Intelligent Systems (TiiS)_ , vol. 1, no. 2, pp. 1–33, 2012.
  * [11] G. W. Beattie, _Sequential Temporal Patterns of Speech and Gaze in Dialogue_. De Gruyter Mouton, 2010, pp. 297–320. [Online]. Available: https://doi.org/10.1515/9783110880021.297
  * [12] G. Mehlmann, M. Häring, K. Janowski, T. Baur, P. Gebhard, and E. André, “Exploring a model of gaze for grounding in multimodal hri,” in _Proceedings of the 16th International Conference on Multimodal Interaction_ , 2014, pp. 247–254.
  * [13] G. Skantze, “Turn-taking in Conversational Systems and Human-Robot Interaction : A Review,” _Computer Speech & Language_, vol. 67, pp. 1–26, 2021.
  * [14] K. Jokinen, H. Furukawa, M. Nishida, and S. Yamamoto, “Gaze and turn-taking behavior in casual conversational interactions,” _ACM Transactions on Interactive Intelligent Systems (TiiS)_ , vol. 3, no. 2, pp. 1–30, 2013.
  * [15] V. J. Zhong, T. Schmiedel, and R. Dornberger, “Investigating the effects of gaze behavior on the perceived delay of a robot’s response,” in _Proceedings of the 11th International Conference on Social Robotics_ , Springer. Springer, 2019, pp. 54–63.
  * [16] D. Lala, K. Inoue, and T. Kawahara, “Smooth turn-taking by a robot using an online continuous model to generate turn-taking cues,” in _Proceedings of the 2019 International Conference on Multimodal Interaction_. ACM, 2019, pp. 226–234.
  * [17] P. Mundy and L. Newell, “Attention, joint attention, and social cognition,” _Current directions in psychological science_ , vol. 16, no. 5, pp. 269–274, 2007.
  * [18] K. Stefanov, G. Salvi, D. Kontogiorgos, H. Kjellström, and J. Beskow, “Modeling of human visual attention in multiparty open-world dialogues,” _ACM Transactions on Human-Robot Interaction (THRI)_ , vol. 8, no. 2, pp. 1–21, 2019.
  * [19] M. K. Pan, S. Choi, J. Kennedy, K. McIntosh, D. C. Zamora, G. Niemeyer, J. Kim, A. Wieland, and D. Christensen, “Realistic and interactive robot gaze,” in _Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 11 072–11 078.
  * [20] T. Uemura, Y. Arai, and C. Shimazaki, “Eye-head coordination during lateral gaze in normal subjects,” _Acta Oto-Laryngologica_ , vol. 90, no. 1-6, pp. 191–198, 1980.
  * [21] J. S. Stahl, “Amplitude of human head movements associated with horizontal saccades,” _Experimental brain research_ , vol. 126, no. 1, pp. 41–54, 1999\.
  * [22] M. M. Hendrikse, G. Llorach, G. Grimm, and V. Hohmann, “Influence of visual cues on head and eye movements during listening tasks in multi-talker audiovisual environments with animated characters,” _Speech Communication_ , vol. 101, pp. 70–84, 2018.
  * [23] L. Gu and J. Su, “Gaze control on humanoid robot head,” in _Proceedings of the 6th World Congress on Intelligent Control and Automation_ , vol. 2. IEEE, 2006, pp. 9144–9148.
  * [24] I. B. Wijayasinghe, S. K. Das, H. L. Miller, N. L. Bugnariu, and D. O. Popa, “Head-eye coordination of humanoid robot with potential controller,” _Journal of Intelligent & Robotic Systems_, vol. 94, no. 1, pp. 15–27, 2019\.
  * [25] A. Zaraki, D. Mazzei, M. Giuliani, and D. De Rossi, “Designing and evaluating a social gaze-control system for a humanoid robot,” _IEEE Transactions on Human-Machine Systems_ , vol. 44, no. 2, pp. 157–168, 2014.
  * [26] S. Andrist, B. Mutlu, and A. Tapus, “Look like me: matching robot personality via gaze to increase motivation,” in _Proceedings of the 33rd annual ACM conference on human factors in computing systems_. ACM, 2015, pp. 3603–3612.
  * [27] Y. I. Nakano, T. Yoshino, M. Yatsushiro, and Y. Takase, “Generating robot gaze on the basis of participation roles and dominance estimation in multiparty interaction,” _ACM Transactions on Interactive Intelligent Systems (TiiS)_ , vol. 5, no. 4, pp. 1–23, 2015.
  * [28] H. Lehmann, I. Keller, R. Ahmadzadeh, and F. Broz, “Naturalistic conversational gaze control for humanoid robots-a first step,” in _Proceedings of the 9th International Conference on Social Robotics_ , Springer. Springer, 2017, pp. 526–535.
  * [29] Y. Zhang, J. Beskow, and H. Kjellström, “Look but don’t stare: Mutual gaze interaction in social robots,” in _Proceedings of the 9th International Conference on Social Robotics_ , Springer. Springer, 2017, pp. 556–566.
  * [30] G. Skantze, M. Johansson, and J. Beskow, “A collaborative human-robot game as a test-bed for modelling multi-party, situated interaction,” in _Proceedings of the 15th International Conference on Intelligent Virtual Agents_. Springer, 2015, pp. 348–351.
  * [31] S. A. Moubayed, G. Skantze, and J. Beskow, “The furhat back-projected humanoid head–lip reading, gaze and multi-party interaction,” _International Journal of Humanoid Robotics_ , vol. 10, no. 01, 2013, id: 1350005.
  * [32] R. Vertegaal, “The gaze groupware system: mediating joint attention in multiparty communication and collaboration,” in _Proceedings of the SIGCHI conference on Human Factors in Computing Systems_ , 1999, pp. 294–301.
  * [33] N. Binetti, C. Harrison, A. Coutrot, A. Johnston, and I. Mareschal, “Pupil dilation as an index of preferred mutual gaze duration,” _Royal Society Open Science_ , vol. 3, no. 7, 2016, id: 160086.
  * [34] R. Meena, G. Skantze, and J. Gustafson, “Data-driven models for timing feedback responses in a Map Task dialogue system,” _Computer Speech and Language_ , vol. 28, no. 4, pp. 903–922, 2014.
  * [35] N. Lavie, A. Hirst, J. W. De Fockert, and E. Viding, “Load theory of selective attention and cognitive control.” _Journal of experimental psychology: General_ , vol. 133, no. 3, p. 339, 2004.