Algorithms for outerplanar graph roots
and graph roots of pathwidth at most 2 ?
Petr A. Golovach1 , Pinar Heggernes1 , Dieter Kratsch2 ,
Paloma T. Lima1 , and Daniël Paulusma3

arXiv:1703.05102v1 [] 15 Mar 2017

1

2

Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway,
{petr.golovach,pinar.heggernes,paloma.lima}@uib.no
Laboratoire d’Informatique Théorique et Appliquée, Université de Lorraine, 57045
Metz Cedex 01, France, dieter.kratsch@univ-lorraine.fr
3
School of Engineering and Computing Sciences, Durham University,
Durham DH1 3LE, UK, daniel.paulusma@durham.ac.uk

Abstract. Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic
and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been dedicated to deciding
whether a given graph has a square root that belongs to a particular
graph class. There are both polynomial-time solvable and NP-complete
cases, depending on the graph class. We contribute with new results in
this direction. Given an arbitrary input graph G, we give polynomialtime algorithms to decide whether G has an outerplanar square root,
and whether G has a square root that is of pathwidth at most 2.

1

Introduction

Squares and square roots of graphs form a classical and well-studied topic in
graph theory, which has also attracted significant attention from the algorithms
community. A graph G is the square of a graph H if G and H have the same
vertex set, and two vertices are adjacent in G if and only if the distance between
them is at most 2 in H. This situation is denoted by G = H 2 , and H is called a
square root of G. A square root of a graph need not be unique; it might even not
exist. There are graphs without square roots, graphs with a unique square root,
and graphs with several different square roots. Characterizing and recognizing
graphs with square roots has therefore been an intriguing and important problem
both in graph theory and in algorithms for decades.
Already in 1967, Mukhopadhyay [25] proved that a graph G on vertex set
{v1 , . . . , vn } has a square root if and only if G contains complete subgraphs
{K 1 , . . . , K n }, such that each K i contains vi , and vertex vj belongs to K i if
and only if vi belongs to K j . Unfortunately, this characterization does not yield
a polynomial-time algorithm for deciding whether G has a square root. Let us
?

Supported by the Research Council of Norway via the project “CLASSIS” and the
Leverhulme Trust (RPG-2016-258).

formally call Square Root the problem of deciding whether an input graph
G has a square root. In 1994 it was shown by Motwani and Sudan [24] that
Square Root is NP-complete. Motivated by its computational hardness, special cases of the problem have been studied, where the input graph G belongs to a
particular graph class. According to these results, Square Root is polynomialtime solvable on planar graphs [21], and more generally, on every non-trivial
minor-closed graph class [26]. Polynomial-time algorithms exist also when the
input graph G belongs to one of the following graph classes: block graphs [19],
line graphs [22], trivially perfect graphs [23], threshold graphs [23], graphs of
maximum degree 6 [4], graphs of maximum average degree smaller than 46
11 [12],
graphs with clique number at most 3 [13], and graphs with bounded clique number and no long induced path [13]. On the negative side, it has been shown that
Square Root is NP-complete on chordal graphs [16]. A number of parameterized complexity results exist for the problem [4, 5, 12].
More interesting from our perspective, the intractability of the problem has
also been attacked by restricting the properties of the square root that we are
looking for. In this case, the input graph G is arbitrary, and the question is
whether G has a square root that belongs to some graph class H specified in
advance. We denote this problem by H-Square Root, and this is exactly the
problem variant that we focus on in this paper.
Significant advances have been made also in this direction. Previous results
show that H-Square Root is polynomial-time solvable for the following graph
classes H: trees [21], proper interval graphs [16], bipartite graphs [15], block
graphs [19], strongly chordal split graphs [20], ptolemaic graphs [17], 3-sun-free
split graphs [17], cactus graphs [11], and graphs with girth at least g for any fixed
g ≥ 6 [10]. The result for 3-sun-free split graphs has been extended to a number
of other subclasses of split graphs in [18]. Observe that if H-Square Root
is polynomial-time solvable for some class H, then this does not automatically
imply that H0 -Square Root is polynomial-time solvable for a subclass H0 of H.
On the negative side, H-Square Root remains NP-complete for each of
the following graph classes H: graphs of girth at least 5 [9], graphs of girth at
least 4 [10], split graphs [16], and chordal graphs [16]. All known NP-hardness
constructions involve dense graphs [9, 10, 16, 24], and the square roots that occur
in these constructions are dense as well. This, in combination with the listed
polynomial-time cases, naturally leads to the question whether H-Square Root
is polynomial-time solvable if the class H is “sparse” in some sense.
Motivated by the above, in this paper we study H-Square Root when H is
the class of outerplanar graphs, and when H is the class of graphs of pathwidth
at most 2. In both cases, we show that H-Square Root can be solved in
polynomial time. In particular, we prove that Outerplanar (Square) Root
can be solved in time O(n4 ) and (Square) Root of Pathwidth ≤ 2 in time
O(n6 ). Our approach for outerplanar graphs can in fact be directly applied to
every subclass of outerplanar graphs that is closed under edge deletion and that
can be expressed in monadic second-order logic, including cactus graphs, for
which a polynomial-time algorithm is already known.
2

2

Preliminaries

We consider only finite undirected graphs without loops and multiple edges. We
refer to the textbook by Diestel [8] for any undefined graph terminology.
Let G be a graph. We denote the vertex set of G by VG and the edge set by
EG . The subgraph of G induced by a subset U ⊆ VG is denoted by G[U ]. The
graph G − U is the graph obtained from G after removing the vertices of U . If
U = {u}, we also write G − u. Similarly, we denote the graph obtained from G
by deleting a set of edges S, or a single edge e, by G − S and G − e, respectively.
The distance distG (u, v) between a pair of vertices u and v of G is the
number of edges of a shortest path between them. The open neighborhood of a
vertex u ∈ VG is defined as NG (u) = {v | uv ∈ EG }, and its closed
S neighborhood
is defined as NG [u] = NG (u) ∪ {u}. For S ⊆ VG , NG (S) = ( v∈S NG (v)) \ S.
Two adjacent vertices u, v are said to be true twins if NG [u] = NG [v]. A vertex
v is simplicial if NG [v] is a clique, that is, if there is an edge between any two
vertices of NG [v]. The degree of a vertex u ∈ VG is defined as dG (u) = |NG (u)|.
The maximum degree of G is ∆(G) = max{dG (v) | v ∈ VG }. A vertex of degree 1
is said to be a pendant vertex.
A connected component of G is a maximal connected subgraph. A vertex u is
a cut vertex of a graph G with at least two vertices if G−u has more components
than G. A connected graph without cut vertices is said to be biconnected. An
inclusion-maximal induced biconnected subgraph of G is called a block.
For a positive integer k, the k-th power of a graph H is the graph G = H k
with vertex set VG = VH such that every pair of distinct vertices u and v of G
are adjacent if and only if distH (u, v) ≤ k. For the particular case k = 2, H 2 is
a square of H, and H is a square root of G if G = H 2 .
The contraction of an edge uv of a graph G is the operation that deletes the
vertices u and v and replaces them by a vertex w adjacent to (NG (u) ∪ NG (v)) \
{u, v}. A graph G0 is a contraction of a graph G if G0 can be obtained from G
by a series of edge contraction. A graph G0 is a minor of G if it can be obtained
from G by vertex deletions, edge deletions and edge contractions.
A graph G is planar if it admits an embedding on the plane such that there
are no edges crossing (except in endpoints). A planar graph G is outerplanar if it
admits a crossing-free embedding on the plane in such a way that all its vertices
are on the boundary of the same (external) face. For a considered outerplanar
graph, we always assume that its embedding on the plane is given. If G is a
planar biconnected graph different from K2 , then for any of its embeddings, the
boundary of each face is a cycle (see, e.g., [8]). If G is a biconnected outerplanar
graph distinct from K2 , then the cycle C forming the boundary of the external
face is unique and we call it the boundary cycle. By definition, all vertices of G
are laying on C, and every edge is either an edge of C or a chord of C, that is,
its endpoints are vertices of C that are non-adjacent in C. Clearly, these chords
are not intersecting in the embedding. For a vertex u, we define the canonical
ordering with respect to u as a clockwise ordering of the vertices on C starting
from u. For a subset of vertices X, the canonical canonical ordering of X with
respect to u is the ordering induced by the canonical ordering of the vertices
3

of C. See Figure 1 a) for some examples. In our paper we use these terms for
blocks of an outerplanar graphs distinct from K2 . Outerplanar graphs can also
be characterized via forbidden minors as shown by Syslo [28].

x2

X
x1

x1

x2
x3

x3
u

xk

v3
v2

vn
u = v1

a)

u

b)

Fig. 1. a) Canonical orderings with respect to u of a biconnected outerplanar graph
with vertex set VG = {v1 , . . . , vn } and a set X = {x1 , . . . , xk }. b) Example of a set
X = {x1 , x2 , x3 } that is consecutive with respect to u; notice that x1 and x3 are not
consecutive.

Lemma 1 ([28]). A graph G is outerplanar if and only if it does not contain
K4 and K2,3 as minors.
A tree decomposition of a graph G is a pair (T, X) where T is a tree and
X = {Xi | i ∈ VT } is a collection of subsets (called bags) of VG such that the
following three conditions hold:
S
i) i∈VT Xi = VG ,
ii) for each edge xy ∈ EG , x, y ∈ Xi for some i ∈ VT , and
iii) for each x ∈ VG the set {i | x ∈ Xi } induces a connected subtree of T .
The width of a tree decomposition ({Xi | i ∈ VT }, T ) is maxi∈VT {|Xi | − 1}. The
treewidth tw(G) of a graph G is the minimum width over all tree decompositions of G. If T is restricted to be a path, then we say that (X, T ) is a path
decomposition of G, The pathwidth pw(G) of G is the minimum width over all
path decompositions of G. Notice that a path decomposition of G can be seen as
a sequence (X1 , . . . , Xr ) of bags. We always assume that the bags (X1 , . . . , Xr )
are distinct and inclusion maximal, that is, there are no bags Xi and Xj such
that Xi ⊂ Xj .
The following fundamental results are due to Bodlaender [1], and Bodlaender
and Kloks [3].
Lemma 2 ([1, 3]). For every fixed constant c, it is possible to decide in linear
time whether the treewidth of a graph is at most c. For every fixed constant c, it
is possible to decide in linear time whether the pathwidth of a graph is at most
c.
4

We need the following three folklore observations about treewidth and pathwidth.
Observation 1 If H is a minor (contraction) of G, then tw(H) ≤ tw(G) and
pw(H) ≤ pw(G).
Observation 2 For an outerplanar graph G, tw(G) ≤ 2.
Observation 3 For a graph G and a positive integer k,
tw(Gk ) ≤ (tw(G) + 1)∆(G)bk/2c+1
and
pw(Gk ) ≤ (pw(G) + 1)∆(G)bk/2c+1 .
For more information on treewidth and pathwidth we refer to [2].
Let H be a square root of a graph G. We say that H is a minimal square
root of G if H 2 = G, and no proper subgraph of H is a square root of G. We
need the following simple observations.
Observation 4 Let H be a graph class closed under edge deletion. If a graph G
has a square root H ∈ H, then G has a minimal square root that belongs to H.
Observation 5 Let H be a minimal square root of a graph G that contains three
pairwise adjacent vertices u, v, w. Then v or w has a neighbor x 6= u in H such
that x is not adjacent to u.
Proof. Since H is a minimal square root of G, H − vw is not a square root of
G. Because uv, uw ∈ EG , we conclude that there is xy ∈ EG \ EH such that H
has a unique (x, y)-path P of length two and wv is an edge of this path. Then
P = xvw or P = xwv for some x 6= u that is not adjacent to u.
t
u
We conclude this section by a lemma that enables us to identify some edges
that are not included in any square root. The lemma is implicit in [11]; for the
sake of completeness we give a full proof here.
Lemma 3. Let x, y be distinct neighbors of a vertex u in a graph G such that x
and y are at distance at least 3 in G − u. Then xu, yu ∈
/ EH for any square root
H of G.
Proof. Suppose that H is a square root of G. To obtain a contradiction, assume
that ux ∈ EH . If uy ∈ EH , then xy ∈ EG contradicting the condition that
distG−u (x, y) ≥ 3. Hence, uy ∈
/ EH . Because uy ∈ EG , there are uz, zy ∈ EH .
If y = x, then xy ∈ EG ; a contradiction. If y 6= x, then xz ∈ EG and xzy is a
path in G − u of length 2 and again we obtain a contradiction with the condition
distG−u (x, y) ≥ 3.
t
u
5

3

Outerplanar Roots

In this section we show that it can be decided in polynomial time whether a
graph has an outerplanar square root. We say that a square root H of G is an
outerplanar root if H is outerplanar. We define the following problem:
Outerplanar Root
Input: a graph G.
Question: is there an outerplanar graph H such that H 2 = G?
The main result of this section is the following.
Theorem 1. Outerplanar Root can be solved in time O(n4 ), where n is the
number of vertices of the input graph.
The remaining part of this section is devoted to the proof of Theorem 1. In
Section 3.1 we obtain several structural results we need to construct an algorithm
for Outerplanar Root. Then in Section 3.2 we construct a polynomial-time
algorithm for Outerplanar Root.
3.1

Structural Lemmas

In this section we give several structural results about outerplanar square roots.
Let H be an outerplanar root of a graph G, u ∈ VG . We say that two distinct
vertices x, y ∈ NH (u) are consecutive with respect to u if x and y are in the
same block F of H and there are no vertices of NH (u) between x and y in the
canonical ordering of the vertices of the boundary cycle of F with respect to u.
For a set of vertices X ⊆ NH (u), we say that the vertices X are consecutive with
respect to u if the vertices of X are in the same block of H and any two vertices
of X consecutive in the canonical ordering of elements of X with respect to u
are consecutive with respect to u; a singleton is assumed to be consecutive (see
Figure 1 b for an example).
As every subgraph of an outerplanar graph is outerplanar, by Observation 4,
we may restrict ourselves to minimal outerplanar roots. Let H be a minimal
outerplanar root of a graph G and let u ∈ VG . Denote by S(G, H, u) a collection
of all subsets X of NH (u) such that X = NG (x) ∩ NH (u) for some x ∈ NG (u) \
NH (u). We intend to use the notion S(G, H, u) to find edges of G which cannot
belong to any square root of G. To this aim we study properties of S(G, H, u).
Lemma 4. Let H be a minimal outerplanar root of a graph G, and let u ∈ VG .
Then for each X ∈ S(G, H, u), X is consecutive with respect to u.
Proof. Let X ∈ S(G, H, u) and consider x ∈ NG (u) \ NH (u) such that X =
NG (x) ∩ NH (u). Notice that X 6= ∅, because x should be adjacent to a vertex
of NH (u) since ux ∈ EG . If |X| = 1, then the claim holds by definition. Assume
that |X| ≥ 2. Notice that the vertices of X are in the same block of H, because
if y, z ∈ NH (u) are not in the same block F of H, then any vertex adjacent
to y and z in G is in NH [u]. Assume that X = {x1 , . . . , xk } and the vertices
6

are numbered in the canonical order with respect to u. Suppose that X is not
consecutive with respect to u. Then there is a vertex y lying on C between
xi−1 and xi for some i ∈ {2, . . . , k} such that uy ∈ EH and yx ∈
/ EG . Since
xi−1 x, xi x ∈ EG , H has (xi−1 , x) and (xi , x)-paths P1 and P2 of length at most
2. Notice that these paths do not contain u, because xu ∈
/ EH , and they do not
contain y, because yx ∈
/ EG . This implies that y is inside of the inner face of C
in the outerplanar embedding of G; a contradiction.
t
u
Lemma 5. Let H be a minimal outerplanar root of a graph G, and let u ∈ VG .
If for two distinct vertices x, y ∈ NH (u) there is no set X ∈ S(G, H, u) such that
x, y ∈ X, then xy ∈
/ EH .
Proof. Suppose that for two distinct x, y ∈ NH (u), xy ∈ EH . By Observation 5,
there is a vertex z such that z is adjacent to x or y in H, but z is not adjacent
to u in H. We obtain that x and y are adjacent to z in G and, therefore,
x, y ∈ NG (z) ∩ NH (u). In other words, x, y ∈ X = NG (z) ∩ NH (u) ∈ S(G, H, u).
t
u
We also need the following two observations.
Lemma 6. Let H be a minimal outerplanar root of a graph G, and let u ∈ VG .
If x ∈ NH (u) is not a pendant vertex of H, then there is y ∈ NG (u) \ NH (u)
that is adjacent to x in G.
Proof. Since x is not a pendant vertex, it has a neighbor in H distinct from
u. If there is a y ∈ NH (x) such that y ∈
/ NH [u], the claim holds. Assume that
for every y ∈ NH (x) distinct from u, it holds that y ∈ NH (u). Consider such a
neighbor y of u. By Observation 5, y has a neighbor z in H such that z ∈
/ NH (u).
Since xy, yz ∈ EH , xz ∈ EG , we have that z ∈ NG (u) \ NH (u).
t
u
Lemma 7. Let H be a minimal outerplanar root of a graph G, and let u ∈ VG .
Then any X ∈ S(G, H, u) has size at most 4.
Proof. Suppose that there is a set X = {x1 , . . . , xk } ∈ S(G, H, u) of size at
least 5. Then X = NG (x) ∩ NH (u) for x ∈ NG (u) \ NH (u). By Lemma 4, X is
consecutive with respect to u, and w.l.o.g. x1 , . . . , xk is the canonical order of
the vertices of X along the boundary cycle C of the block of H with respect
to u. Suppose that x lays on C. If it lays before x3 in the canonical ordering
of the vertices of C with respect to u, then x is not adjacent to xk in G by
outerplanarity; a contradiction. Similarly, if x lays after x3 , x is not adjacent to
x1 in G and we also have a contradiction. Suppose that x does not belong to C.
Then x is at distance at most 2 in H from x1 and xk . It follows that there is a
(x1 , xk )-path P in H of length at most 4 avoiding u and at least one vertex of
X but this contradicts outerplanarity.
t
u
By combining Lemmas 4 and 7 we obtain the following lemma.
Lemma 8. Let H be a minimal outerplanar root of a graph G, and let u ∈ VG .
Then the following holds.
7

(i) If x, y ∈ NH (u) do not belong to
S(G, H, u), x ∈
/ X or y ∈
/ X.
(ii) If F is a block of H containing u
in the canonical order with respect
any X ∈ S(G, H, u), xi ∈
/ X or xj

the same block of H, then for any X ∈
and vertices x1 , . . . , xk ∈ NH (u) ordered
to u in the boundary cycle of F , then for
∈
/ X if i, j ∈ {1, . . . , k} and |i − j| ≥ 4.

We now state some structural results that help to decide whether an edge
incident to a vertex is in an outerplanar root or not. Suppose that u and v are
pendant vertices of a square root H of G and that u and v are adjacent to the
same vertex of H − {u, v}. Then, in G, u and v are simplicial vertices and true
twins. We use this observation in the proof of the following lemma that allows
to find some pendant vertices.
Lemma 9. Let H be a minimal outerplanar root of a graph G. If G contains at
least 7 simplicial vertices that are pairwise true twins, then at least one of these
vertices is a pendant vertex of H.
Proof. Let H be a minimal outerplanar root of a graph G that contains a set X
of 7 simplicial vertices that are pairwise true twins.
Suppose first that X contains two vertices x and y that do not belong to the
same block of H. We claim that x is a pendant vertex of H. Since x and y are
adjacent in G, we obtain that xu, yu ∈ EH for a cut vertex u that belongs to two
blocks Fx and Fy of H containing x and y respectively. To obtain a contradiction,
assume that x has a neighbor z 6= u in H. Clearly, z is not in Fy . It implies that
zu ∈ EH , because x and y are true twins of G and, therefore, z ∈ NG (y).
Since H is a minimal square root, H − xz is not a square root of G. Because
ux, uz ∈ EH , we have that there is a vertex z 0 6= u such that xz 0 , zz 0 ∈ EG but
either i) xz 0 ∈ EH , zz 0 ∈
/ EH and zxz 0 is the unique (z, z 0 )-path of length at
most 2 in H or, symmetrically, ii) xz 0 ∈
/ EH , zz 0 ∈ EH and xzz 0 is the unique
0
(x, z )-path of length at most 2 in H. Because x and y are true twins of G and
z 0 6= u, we obtain that yz 0 ∈ EG and, therefore, uz 0 ∈ EH . Hence, xuz 0 and
zuz 0 are paths of H contradicting i) or ii) respectively. We conclude that x is a
pendant vertex of H.
Suppose now that the vertices of X belong to the same block F of H. Let C
be the boundary cycle of F and denote by x1 , . . . , x7 the vertices of X numbered
according to the canonical order with respect to an arbitrary vertex of C. Because
the vertices of X are pairwise adjacent in G, F has a chord uv such that X has
vertices in the two components of F − {u, v}. Among all such chords we choose
uv and a component F 0 of F −{u, v} in such a way that F 0 contains the minimum
number of vertices of X. Let F 00 be the other compoent of F − {u, v}. Assume
without loss of generality that x1 ∈ VF 0 and let xi , . . . , xj for 1 < i ≤ j ≤ 7
be the vertices of X in F 00 . Notice that F 00 contains at least 3 vertices of X by
the choice of uv. Assume also that v is after x1 in the canonical ordering of the
vertices of C with respect to u. Because the vertices of X are adjacent in G,
they are at distance at most 2 in H. It implies that for any x ∈ X ∩ VF 0 and any
y ∈ X ∩ VF 00 , xu, uy ∈ EH or xv, vy ∈ EH by the outerplanarity of F .
8

Suppose that F 0 contains at least two vertices of X. By symmetry, we can
assume that x1 , x2 ∈ VF 0 . It follows that x1 u ∈ EH , x2 v ∈ EH but x1 v, x2 u ∈
/ EH
by the choice of uv. We obtain that xi u ∈ EH and xj v ∈ EH , but these are
intersecting chords of C; a contradiction. We conclude that x1 is the unique
vertex of X in F 0 . Notice that it implies that i ≤ 3 and j ≥ 6 but it can happen
that u = x7 or v = x2 . We also have that x1 u ∈ EH or x1 v ∈ H. Using symmetry
we assume that x1 u ∈ EH .
If x1 v ∈
/ EH , then xk u ∈ EH for k ∈ {i, . . . , j}. Hence, u is adjacent to
x1 , . . . , x6 in this case.
Suppose that x1 v ∈ EH . We show that either xk u ∈ EH for k ∈ {i, . . . , j}
or xk v ∈ EH for k ∈ {i, . . . , j}. Assume that this is not the case and that there
is an s ∈ {i, . . . , j} such that xs u ∈
/ EH and t ∈ {i, . . . , j} such that xt v ∈
/ EH .
Since xs u ∈
/ EH , xs v ∈ EH . Because we cannot have intersecting chords in C,
xi u ∈
/ EH . Similarly, we obtain that xj v ∈
/ EH . Since, for every k ∈ {i + 1, j − 1},
xk u ∈ EH or xk v ∈ EH and j − i ≥ 3, we have that the distance between xi and
xj in H is at least 3 by the outerplanarity of H, a contradiction. Therefore, the
claim holds. By symmetry, we can assume that xk u ∈ EH for k ∈ {i, . . . , j}. In
particular, u is adjacent to x1 , . . . , x6
We now show that x3 is a pendant vertex of H. To obtain a contradiction,
assume that x3 has a neighbor y in H distinct from u. Because x3 and x6 are
true twins of G, yx6 ∈ EG and, therefore, yu ∈ EH . Because H is a minimal
outerplanar root, H − x3 y is not a square root of G. Because ux3 , uy ∈ EH ,
it follows that there is a vertex z 6= u such that x3 z, yz ∈ EG but either i)
x3 z ∈ EH , yz ∈
/ EH and yx3 z is the unique (y, z)-path in H or, symmetrically,
ii) x3 z ∈
/ EH , yz ∈ EH and x3 yz is the unique (x3 , z)-path in H. If x3 z ∈ EH ,
then by the same arguments as for y, we have that zu ∈ EH and we get another
path yuz. Let yz ∈ EH . If z ∈ {x1 , . . . , x5 }, then zu ∈ EH and we have the path
x3 uz. Hence, z ∈
/ {x1 , . . . , x5 }. Since z is adjacent to x3 in G, z is a neighbor of
x6 in G. The only possibility is that zx4 , zx5 ∈ EH , i.e., z lays in C between x4
and x5 . Since z is adjacent to x1 , we obtain that uz ∈ EH . Again, we have the
path x3 uz; a contradiction. We conclude that x3 is a pendant vertex of H. t
u
We apply Lemma 3 to identify the edges incident to a vertex of sufficiently
high degree in an outerplanar root using the following two lemmas.
Lemma 10. Let G be a graph having a minimal outerplanar root H. Let also
u ∈ VG be such that there are three distinct vertices v1 , v2 , v3 ∈ NG (u) that are
pairwise at distance at least 3 in G − u. Then for x ∈ NG (u), xu ∈
/ EH if and
only if there is an i ∈ {1, 2, 3} such that distG−u (x, vi ) ≥ 3.
Proof. Let H be a minimal outerplanar root of G. If there is an i ∈ {1, 2, 3}
such that distG−u (x, vi ) ≥ 3, then xu ∈
/ EH by Lemma 3. Hence, to complete
the proof, we have to show that if xu ∈
/ EH , then there is i ∈ {1, 2, 3} such that
distG−u (x, vi ) ≥ 3. Observe that this property trivially holds if x = vi for some
i ∈ {1, 2, 3}. Assume that x ∈
/ {v1 , v2 , v3 }. Notice that uvi ∈
/ EH by Lemma 3
for i ∈ {1, 2, 3}.
9

Let x ∈ NG (u) such that xu ∈
/ EH . Suppose that there is an i ∈ {1, 2, 3}
such that x and vi are in distinct components of H − u. Then any (x, vi )-path
in H goes through u and has length at least 4, because ux, uvi ∈
/ EH . It follows
that distG−u (x, vi ) ≥ 3.
v2
v20

v1 = v10
v3 = v30
u
Fig. 2. The case when v1 , v2 , v3 are in the same component of H − u.

Suppose now that v1 , v2 , v3 and x are in the same component of H − u. Since
xu ∈ EG , there is y ∈ NH (u) such that xy ∈ EH . Let F be a block of H
containing u and y and denote by C its boundary cycle. Because v1 , v2 , v3 and
x are in the same component of H − u, each vi is either i) a vertex of F and we
let vi0 = vi in this case or ii) vi ∈
/ VF and there is a unique vi0 ∈ VF such that
0
0
vi vi ∈ EH and vi u ∈ EH (see Figure 2). Assume that v10 , v20 , v30 is the canonical
order with respect to u in C.
Let y 6= v20 . If y lays before v20 on C in the canonical ordering with respect to u,
then distG−u (x, v3 ) ≥ distG−u (v2 , v3 ) ≥ 3. Similarly, if y lays after v20 on C in the
canonical ordering with respect to u, then distG−u (x, v1 ) ≥ distG−u (v1 , v2 ) ≥ 3.
Suppose that y = v20 . Notice that it means that v2 6= v20 . If x ∈
/ VF , then y
is the unique neighbor of x in H that is in F . We have that distG−u (v1 , y) =
distG−u (v1 , v2 ) ≥ 3. If x ∈ VF , then x is either before or after v20 in the canonical
ordering with respect to u. We have that distG−u (x, v3 ) ≥ distG−u (v2 , v3 ) ≥ 3
in the first case and distG−u (x, v1 ) ≥ distG−u (v1 , v2 ) ≥ 3 in the second.
t
u
Lemma 11. Let G be a graph having a minimal outerplanar root H such that
any vertex of H has at most 7 pendant neighbors. Let also u ∈ VG with dH (u) ≥
22. Then there are distinct v1 , v2 , v3 ∈ NG (u) that are pairwise at distance at
least 3 in G − u.
Proof. Let H be a minimal outerplanar root of G such that any vertex of H
has at most 7 pendant neighbors and let u ∈ VG be a vertex with dH (u) ≥ 22.
Denote by A the set of pendant neighbors of u and let X = NH (u) \ A. Notice
that |X| ≥ 15, because |A| ≤ 7.
Suppose that the vertices of X are in at least 3 distinct components of H − u.
Then there are distinct blocks F1 , F2 and F3 of H containing u and at least one
10

vertex of X each. By Lemma 6, there are v1 , v2 , v3 ∈ NG (u) \ NH (u) such that vi
is adjacent to a vertex of Fi in G for i ∈ {1, 2, 3}. Notice that v1 , v2 and v3 are
in distinct components of H − u. We obtain that they are pairwise at distance
at least 3 in G − u.
Suppose now that the vertices of X are in exactly two distinct components of
H − u. Then there are two blocks F1 and F2 of H containing u and the vertices
of X. Since |X| ≥ 15, we can assume that F1 contains at least 8 vertices of X.
Denote them by x1 , . . . , xk in their order in the canonical order in the boundary
cycle of F1 with respect to u. By Lemma 6, there are v1 , v2 ∈ NG (u) \ NH (u)
such that v1 is adjacent to x1 in G and v2 is adjacent to xk . By Lemmas 4 and
7, v1 is not adjacent in G to x5 , . . . , xk and vk is not adjacent to x1 , . . . , xk−4 .
Notice that each of v1 and v2 is either laying on the boundary cycle of F1 or
is in another block of H containing x1 or x2 and xk−1 or xk respectively. Then
distG−u (v1 , v2 ) ≥ 3. By Lemma 6, there is v3 ∈ NG (u) \ NH (u) such that v3
is adjacent to a vertex of F2 in G. Notice that v1 , v2 and v3 are in distinct
components of H − u. We obtain that v3 is at distance at least 3 from v1 and v2
in G − u.
Finally, assume that the vertices of X are in the same block F of H. Denote
them by x1 , . . . , xk in their order in the canonical order in the boundary cycle
of F with respect to u. By Lemma 6, there are v1 , v2 , v3 ∈ NG (u) \ NH (u) such
that v1 is adjacent to x1 in G, v2 is adjacent to x8 and v2 is adjacent to xk .
By Lemmas 4 and 7, v1 is not adjacent in G to x5 , . . . , xk , v2 is not adjacent to
x1 , . . . , x4 and xk−3 , . . . , xk , and vk is not adjacent to x1 , . . . , xk−4 . Notice that
each of v1 , v2 and v2 is either laying on the boundary cycle of F or is in another
block of H containing x1 or x2 , x7 or x8 or x9 and xk−1 or xk respectively. Then
distG−u (vi , vj ) ≥ 3 for i, j ∈ {1, 2, 3}, i 6= j.
t
u
The next lemma is crucial for our algorithm. To state it, we need some
additional notations. Let H be a minimal outerplanar root of a graph G such
that each vertex of H is adjacent to at most 7 pendant vertices. Let U be a
set of vertices of H that contains all vertices of degree at least 22. For every
u ∈ U and every block F of H containing u we do the following. Consider the
set X = NH (u) ∩ VF and denote the vertices of X by x1 , . . . , xk , where these
vertices are numbered in the canonical order with respect to u. Then
– for i, j ∈ {1, . . . , k}, delete the edge xi xj from G if |i − j| ≥ 4.
– for i ∈ {1, . . . , k}, delete the edges xi y from G for y ∈ NH (u) \ VF .
Denote by G0 (H, U ) the graph obtained by this procedure.
Lemma 12. There is a constant c that depends neither on G nor on H such
that
tw(G0 (H, U )) ≤ c.
Proof. Let H be a minimal outerplanar root of a graph G such that each vertex
of H is adjacent to at most 7 pendant vertices. Let U be a set of vertices of H
containing the vertices of degree at least 22. For each vertex u ∈ U we do the
following.
11

– Let F1 , . . . , Fr be the blocks of H containing u.
– For each i ∈ {1, . . . , r}, denote by xi1 , . . . , xiki the neighbors of u in Fi numbered according to the canonical ordering with respect to u for the boundary
cycle of Fi . Assume that x0 , . . . , xk is the ordering of NH (u) obtained by the
consecutive concatenation of the sequences xi1 , . . . , xiki for i = 1, . . . , r.
– Modify H as follows: delete u, replace it by a path u1 . . . uk and make each
ui adjacent to xi−1 and xi for i ∈ {1, . . . , k} (see Figure 3).
Denote by Ĥ the graph obtained by the procedure. Notice that the procedure
modifies degrees of vertices of H but we do not recompute U .

x1

x0
xk

x2

u

x0

x1

x2

x3 x4

xk

x3
x4
u1

uk

Fig. 3. Modification of H.

Notice that H is a contraction of Ĥ as H can be obtained from Ĥ by contracting the paths u1 . . . uk constructed for u ∈ U . It is also straightforward to
see that Ĥ is an outerplanar graph, because each step maintains outerplanarity
(see Figure 3). By Observation 2, tw(Ĥ) ≤ 2.
We claim that ∆(Ĥ) ≤ 42. Let v ∈ VĤ . Suppose first that v ∈ VH \ U . We
have that dH (v) ≤ 21 and, in particular, v has at most 21 neighbors in U in
the graph H. In the construction of Ĥ each neighbor of this type is replaced by
two neighbors and all other neighbors remain the same. Therefore, dĤ (v) ≤ 42.
Suppose now that v is a vertex of one of the paths u1 . . . uk constructed for
u ∈ U . Notice, that when u is replaced by u1 . . . uk , then the degree of each
vertex ui is at most 4, and at most two neighbors of ui could be modified in the
subsequent construction steps. It implies that dĤ (v) ≤ 6.
We claim that G0 (H, U ) is a minor of Ĥ 4 .
Let Ĝ be the graph obtained from Ĥ 4 by the contraction of the paths u1 . . . uk
constructed for u ∈ U . We use the name u for the vertex obtained by contracting
u1 . . . uk constructed for u ∈ U . Thus, we can assume that VĜ = VG . We show
that G0 (H, U ) is a subgraph of Ĝ.
We already observed that H can be obtained from Ĥ by contracting paths
u1 . . . uk constructed for u ∈ U . Hence, each edge of H is an edge of Ĝ. Let xy
be an edge of G0 (H, U ) that is not an edge of H. Then, there is u ∈ VG such
12

that xu, yu ∈ H. Denote by X 0 and Y 0 respectively the sets of vertices of Ĥ that
are contracted to x and y respectively. If u ∈
/ U , then by the construction of Ĥ,
there are x0 ∈ X 0 and y 0 ∈ Y 0 such that x0 u, y 0 u ∈ EĤ . Hence, x0 y 0 ∈ Ĥ 4 and
xy ∈ EĜ . Suppose that u ∈ U . By the definition of G0 (H, U ), the vertices x and
y are in the same block F of H. Denote by z1 , . . . , zk the vertices of NH (u) in F
in the canonical order with respect to u along the boundary cycle of F . We have
that x = zi and y = zj for some i, j ∈ {1, . . . , k}. By the definition of G0 (H, U ),
|i − j| ≤ 4. By the construction of Ĥ, there are x0 ∈ X 0 and y 0 ∈ Y 0 that are
joined by the path x0 zi+1 . . . zj y 0 in Ĥ. Since this path has length at most 4,
x0 y 0 ∈ Ĥ 4 . Therefore, xy ∈ Ĝ.
Since G0 (H, U ) is a subgraph of Ĝ and Ĝ is a contraction of Ĥ 4 , we conclude
that G0 (H, U ) is a minor of Ĥ 4 .
Since, G0 (H, U ) is a minor of Ĥ 4 , tw(G0 (H, U )) ≤ tw(Ĥ 4 ) by Observation 1.
Because Ĥ is outerplanar, tw(Ĥ) ≤ 2 by Observation 2, and because ∆(Ĥ) ≤ 42,
tw(Ĥ 4 ) ≤ (tw(Ĥ) + 1) · 423 by Observation 3. We obtain that tw(G0 (H, U )) ≤
3 · 423 = c.
t
u
3.2

The Algorithm

In this section we construct an algorithm for Outerplanar Root with running
time O(n4 ). Let G be the input graph. Clearly, it is sufficient to solve Outerplanar Root for connected graphs. Hence, we assume that G is connected and
has n ≥ 2 vertices.
First, we preprocess G using Lemma 9 to reduce the number of pendant
vertices adjacent to the same vertex in a (potential) outerplanar root of G. To
do so, we exhaustively apply the following rule.
Pendants reduction. If G has a set X of simplicial true twins of size at least 8,
then delete an arbitrary u ∈ X from G.
The following claim shows that this rule is safe.
Lemma 13. If G0 = G − u is obtained from G by the application of Pendant
reduction, then G has an outerplanar root if and only if G0 has an outerplanar
root.
Proof. Suppose that H is a minimal outerplanar root of G. By Lemma 9, H has a
pendant vertex u ∈ X. It is easy to verify that H 0 = H −u is an outerplanar root
of G0 . Assume now that H 0 is a minimal outerplanar root of G0 . By Lemma 9,
H has a pendant vertex w ∈ X \ {u}, since the vertices of X \ {u} are simplicial
true twins of G0 and |X \ {u}| ≥ 7. Let v be the unique neighbor of w in H 0 . We
construct H from H 0 by adding u and making it adjacent to v. It is readily seen
that H is an outerplanar root of G. This completes the proof.
t
u
For simplicity, we call the graph obtained by exhaustive application of the
pendants rule G again. The following property immediately follows from the
observation that any two pendant vertices of a square root H of G adjacent to
the same vertex in H are true twins of G.
13

Lemma 14. Every outerplanar root of G has at most 7 pendant vertices adjacent to the same vertex.
In the next stage of our algorithm we label some edges of G red or blue in
such a way that the edges labeled red are included in every minimal outerplanar
root and the blue edges are not included in any minimal outerplanar root. We
denote by R the set of red edges and by B the set of blue edges. We also construct
a set of vertices U of G such that for every u ∈ U , the edges incident to u are
labeled red or blue.
Labeling. Set U = ∅, R = ∅ and B = ∅. For each u ∈ VG such that there are
three distinct vertices v1 , v2 , v3 ∈ NG (u) that are at distance at least 3 from each
other in G − u do the following:
(i)
(ii)
(iii)
(iv)
(v)

set U = U ∪ {u},
set B 0 = {ux ∈ EG | there is 1 ≤ i ≤ 3 s.t. distG−u (x, vi ) ≥ 3},
set R0 = {ux | x ∈ NG (u)} \ B 0 ,
set R = R ∪ R0 and B = B ∪ B 0 ,
if R ∩ B 6= ∅, then return a no-answer and stop.
Lemmas 10 and 11 imply the following claim.

Lemma 15. If G has an outerplanar root, then Labeling does not stop in
Step (v), and if H is a minimal outerplanar root of G, then R ⊆ EH and
B ∩ EH = ∅. Moreover, every vertex u ∈ VG with dH (u) ≥ 22 is included in U .
Next, we find the set of edges xy with xu, yu ∈ R for some u in R such that
they cannot be edges in any minimal outerplanar root, and thus are irrelevant
edges.
Finding irrelevant edges. Set S = ∅. For each u ∈ U and each pair of distinct
x, y ∈ NG (u) such that ux, uy ∈ R do the following.
(i) If xy ∈
/ EG , then return a no-answer and stop.
(ii) If for x and y, there is no v ∈ NG (u) such that vu ∈ B and x, y ∈ NG (v),
then include xy in S.
(iii) If R ∩ S 6= ∅, then return a no-answer and stop.
Combining Lemmas 15 and 5, we obtain the following claim.
Lemma 16. If G has an outerplanar root, then Finding irrelevant edges
does not stop in Steps (i) and (iii), and if H is a minimal outerplanar root of
G, then S ∩ EH = ∅.
Assume that we did not stop during the execution of Finding irrelevant
edges. Let G0 = G − S. We show the following.
Lemma 17. The graph G has an outerplanar root if and only if there is a set
L ⊆ EG0 such that
(i) R ⊆ L, B ∩ L = ∅,
14

(ii) for any xy ∈ EG0 , xy ∈ L or there is z ∈ VG0 such that xz, yz ∈ L,
(iii) for any distinct edges xz, yz ∈ L, xy ∈ EG0 or there is u ∈ U such that
xu, yu ∈ R,
(iv) the graph H = (VG , L) is outerplanar.
Proof. Let H be a minimal outerplanar root of G. By Lemma 16, EH ∩ S = ∅,
i.e., EH ⊆ EG0 . Let L = EH . It is straightforward to verify that (i)–(iv) are
fulfilled. Assume now that there is L ⊆ EG0 such that (i)–(iv) hold. Then we
have that H = (VG , L) is an outerplanar root of G.
t
u
To complete the description of the algorithm, it remains to show how to
check the existence of a set of edges L satisfying (i)–(iv) of Lemma 17 for given
G0 , R and B. Notice, that if G has a minimal outerplanar root H, then G0 is
a subgraph of the graph G0 (H, U ) constructed in Section 3.1 by Lemma 8. By
Lemma 12, there is a constant c that depends neither on G nor on H such that
tw(G0 (H, U )) ≤ c. Therefore, tw(G0 ) ≤ c for a yes-instance. We use Lemma 2
to verify whether it holds. If we obtain that tw(G0 ) > c, we conclude that
we have a no-instance and stop. Otherwise, we use the celebrated theorem of
Courcelle [6], which states that any problem that can be expressed in monadic
second-order logic can be solved in linear time on graph of bounded treewidth.
It is straightforward to see that properties (i)–(iv) can be expressed in this logic.
In particular, to express outerplanarity in (iv), we can use Lemma 1 and the
well-known fact that the property that G contains F as minor can be expressed
in monadic second-order logic if F is fixed (see, e.g., the book of Courcelle and
Engelfriet [7]). It immediately implies that we can decide in linear time whether
L exists or not. Notice that we can modify these arguments such that we do not
only check the existence of L but also find it. To do this, we can construct a
dynamic programming algorithm for graphs of bounded treewidth that finds L.
Now we evaluate the running time of our algorithm. We can find simplicial
vertices of the input n-vertex graph G in time O(n3 ). Therefore, Pendant reduction can be done in time O(n3 ). For every vertex u, we can compute the
distances between the vertices of NG (u) in G − u in time O(n3 ). This implies
that Labeling can be done in time O(n4 ). Finding irrelevant edges also can
be done in time O(n4 ) by checking O(n2 ) pairs of vertices x and y. Then G0
can be constructed in linear time. Finally, checking whether tw(G0 ) ≤ c and
deciding whether there is a set of edges L satisfying the required properties can
be done in linear time by Lemma 2 and Courcelle’s theorem [6] respectively.
Notice that we can use the same arguments to decide whether a graph G
has a square root H that belongs to some subclass H of the class of outerplanar
graphs. To be able to apply our structural lemmas, we only need the property
that H should be closed under edge deletions. Observe also that if the properties
defining H could be expressed in monadic second-order logic, then we can apply
Courcelle’s theorem [6]. It gives us the following corollary.
Corollary 1. For every subclass C of the class of outerplanar graphs that is
closed under edge deletions and can be expressed in monadic second-order logic,
15

it can be decided in time O(n4 ) whether an n-vertex graph G has a square root
H ∈ C.

4

Roots of Pathwidth at most two

Our main approach for solving Outerplanar root is general in the sense that
it can be adapted to also find square roots belonging to some other graph classes.
In this section, we show that there is an algorithm to decide in polynomial time
whether a graph has a square root of pathwidth at most 2. Notice that graphs
of pathwidth 1 are caterpillars, and that it can be decided in polynomial time
whether a graph G has a square root that is a caterpillar by an easy adaptation
of the algorithms for finding square roots that are trees [21, 27].
We define the following problem:
Root of Pathwidth ≤ 2
Input: a graph G.
Question: is there a graph H such that pw(H) ≤ 2 and H 2 = G?
The main difference between our algorithm for Root of Pathwidth ≤
2 and our algorithm for Outerplanar Root lies in the way properties of
the involved graph classes are used. To show the structural results needed for
this algorithm, we use the property that a potential square root has a path
decomposition of width at most 2, instead of the existence of an outerplanar
embedding used in the previous section.
Theorem 2. Root of Pathwidth ≤ 2 can be solved in time O(n6 ), where n
is the number of vertices of the input graph.
The remaining part of this section contains the proof of Theorem 2. In Section 4.1, we present the structural results necessary to prove correctness of the
algorithm for Root of Pathwidth ≤ 2. The algorithm itself is presented in
Section 4.2.
4.1

Structural Lemmas

In this section, we present structural properties of graphs with square roots
of pathwidth at most 2. Recall that we assume that for any considered path
decomposition, it holds that A * B for every two distinct bags A and B of the
decomposition. As the pathwidth of any subgraph of a graph of pathwidth at
most 2 is upper bounded by 2, by Observation 4, we can consider only minimal
roots of pathwidth at most 2.
Lemma 18. Let G be a graph and H be a minimal square root of G such
that pw(H) ≤ 2. Suppose there exist distinct u, v, x1 , . . . , xk such that the bags
{x1 , u, v}, {x2 , u, v},. . ., {xk , u, v} appear in this order in the path decomposition
of H. Then for each i, 2 ≤ i ≤ k − 1, NH (xi ) ⊆ {u, v}.
16

Proof. Suppose xi has a neighbor w in H such that w 6= u and w 6= v. Clearly
there exists a bag B in the path decomposition of H that contains xi and w. As
B contains xi , then B is between the bags {x1 , u, v} and {xk , u, v} in the path
decomposition and hence must contain u and v. Then |B| ≥ 4, a contradiction
with pw(H) ≤ 2.
t
u
For two positive integers p and q, we denote by R(p, q) the Ramsey number,
that is, the smallest n such that every graph on n vertices has either a clique of
size p or an independent set of size q. Those numbers are all finite by Ramsey’s
theorem (see, e.g., [8]).
Lemma 19. Let G be a graph and H be a minimal square root of G such that
pw(H) ≤ 2. Then there is a constant c1 such that for every set W of true twins
in G, if |W | ≥ c1 , then one of the following holds:
(i) W has a vertex that is a pendant in H.
(ii) W has distinct pairwise nonadjacent vertices x, y, z of degree 2 in H such
that NH (x) = NH (y) = NH (z).
Proof. Let c1 = R(4, 16).
We start by constructing an auxiliary graph F . Let VF = W and two vertices
of F are adjacent if there exists a bag in the path decomposition of H that
contains both of them. We want to show that F has an independent set of size
16. To do so, we prove that F has no clique of 4 vertices. Suppose for the sake of
contradiction that F has such a clique, say {x1 , x2 , x3 , x4 }. Let Pi be the interval
of those bags of the path decomposition of H that contain the vertex xi . By the
construction of F , these intervals are pairwise intersecting. By the Helly property,
there exists a bag containing all four vertices, a contradiction with pw(H) ≤ 2.
Hence F has an independent set of size 16, since |VF | = |W | ≥ R(4, 16) and F
has no clique of 4 vertices.
Let W 0 = {x1 , x2 , . . . , x16 } be such an independent set of F . By the construction of F , there are no two vertices of W 0 that are contained in the same
bag of the path decomposition of H. Let B1 , B2 , . . . , B16 be bags containing the
vertices of W 0 such that xi ∈ Bi . As the vertices of W 0 are true twins in G and
they are not adjacent in H, there must exist a path of length two between any
two of them. Let x1 ux16 be such path between x1 and x16 . We may consider
that u ∈ B1 , otherwise we can pick bag B1 as the one containing x1 and u.
Analogously, we may assume that u ∈ B16 . Since we have a path decomposition,
we conclude that u ∈ Bi , 2 ≤ i ≤ 15.
Suppose there are three distinct vertices xi , xj and xk in W 0 that are not
adjacent to u, with 2 ≤ i < j < k ≤ 15. Let v be a vertex in a path of length two
between xi and xk , i.e. v is a common neighbor of xi and xk . We may assume
that Bi = {xi , u, v} and Bk = {xk , u, v}. Then v ∈ Bj . By Lemma 18 and by
the fact that xj u ∈
/ EH , we conclude that dH (xj ) = 1 and hence (i) holds.
Suppose that at most two vertices of W 0 \ {x1 , x16 } are not adjacent to u in
H. Let W 00 = {x01 , . . . , x0p }, p ≥ 12, be the set containing the vertices that are
adjacent to u in W 0 \ {x1 , x16 }. If some vertex of W 00 has degree one in H, then
17

condition (i) holds. Assume this is not the case. Then all the vertices of W 00 have
degree at least two in H. Let B 0 = {B10 , . . . , Bp0 } be bags such that x0i ∈ Bi0 . Let
v be a neighbor of x01 , v 6= u. We may assume B10 = {x01 , u, v}. If v appears in at
least five bags of B 0 , then it appears in B10 , B20 , B30 , B40 and B50 . As x02 , x03 and
x04 do not have degree one by hypothesis, then by Lemma 18, they have degree
two and hence condition (ii) holds. As x01 and x16 are true twins in G, then v
must also be a neighbor of x16 in G. If v and x16 are not adjacent, let vwx16 be
a path of length two between them. If w 6= u, the bag containing {v, w, u} has to
be between {x01 , u, v} and B16 . Since p ≥ 12, either v or w appear in at least five
bags of B 0 . If w = u, then v, u and x01 form a triangle in H. By Observation 5,
there exists a vertex z that is adjacent to either v or x01 that is not adjacent
to u. The case when z is a neighbor of x01 has already been covered. Suppose
zv ∈ EH and zu ∈
/ EH . As dH (z, x01 ) ≤ 2, z is adjacent to x01 in G, meaning
that z must also be adjacent to x16 in G. If zx16 ∈ EH , then the bag {v, z, u}
appears between bags B10 and the bag containing x16 and z. Then either v or z
appear in at least five bags of B 0 . If zx16 ∈
/ EH , let zyx16 be a path of length
two in H. Since p ≥ 12 and there must exist a bag containing x16 and y, and
thus one of v, z or y appear in at least five bags of B 0 .
t
u
If G has a set W of true twins with size greater than c1 , then we can delete
an arbitrary vertex of W . The following lemma shows that this procedure is safe.
Lemma 20. Let W be a set of true twins in G such that |W | ≥ c1 + 1 and
let u ∈ W . Then G has a square root H such that pw(H) ≤ 2 if and only if
G0 = G − u has a square root H 0 such that pw(H 0 ) ≤ 2.
Proof. Let G be a graph that has a square root H of pathwidth at most 2. Since
|W | ≥ c1 + 1, either there exists a vertex v ∈ W satisfying the condition (i)
of Lemma 19 or there are three vertices v1 , v2 , v3 ∈ W satisfying (ii). Since the
vertices of W are true twins, we can assume that u = v in the first case and
u = v1 in the second. In both cases we obtain that H − u is a square root of
pathwidth at most 2 for G − u.
To prove the other direction, let H 0 be a square root of pathwidth at most
2 of G0 . Since |W \ {u}| ≥ c1 , H 0 has a vertex v satisfying the condition (i) of
Lemma 19 or there are three vertices v1 , v2 , v3 ∈ W satisfying (ii).
If v is a pendant, let w be the vertex of H 0 that is adjacent to v. In order to
obtain a square root H of G, we attach u to w in H 0 . We now prove that pw(H) ≤
2. We may assume that v appears in only one bag in the path decomposition
of H 0 (which also contains w). If this is not the case, we can delete all other
occurrences of v and still obtain a valid path decomposition of H 0 having width
at most two. Let Ai be the bag containing {w, v} and Ai+1 be the next bag in
the path decomposition. If w ∈ Ai+1 , we create a new bag between Ai and Ai+1
containing (Ai ∩ Ai+1 ) ∪ {u}. If w ∈
/ Ai+1 , then |Ai ∩ Ai+1 | ≤ 1, and the new bag
will contain (Ai ∩ Ai+1 ) ∪ {u, w}. This is a path decomposition for H of width
at most two.
Assume that v1 , v2 , v3 are vertices satisfying condition (ii) of Lemma 19. Let
NH (v1 ) = NH (v2 ) = NH (v3 ) = {w, y}. In order to obtain a square root H for
18

G, we add u to V (H 0 ) and make it adjacent to w and y. We now prove that
pw(H) ≤ 2. Since NH (v1 ) = NH (v2 ) = NH (v3 ) = {w, y}, there is a bag in
the path decomposition of H 0 containing Ai = {w, y, vi } for some i ∈ {1, 2, 3}.
Since vi is only adjacent to w and y, we may assume that this is the only bag
in the decomposition containing vi . Let Ai+1 be the bag that succeeds Ai in the
decomposition. We create a new bag between Ai and Ai+1 containing {u, w, y},
and hence obtain a path decomposition for H of width at most two.
t
u
For simplicity, let us denote the graph obtained by exhaustive application
of the previously described safe procedure by G again. From now on, in all our
lemmas, we assume that every set of true twins of G has size bounded by the
constant c1 .
Lemma 21. Let G be a graph and H be a minimal square root of G such
that pw(H) ≤ 2. Suppose there exist distinct u, v, x1 , . . . , xk such that the bags
{x1 , u, v}, {x2 , u, v},. . ., {xk , u, v} appear in this order in the path decomposition
of H. Then k ≤ 3c1 + 2.
Proof. By Lemma 18, for every 2 ≤ i ≤ k − 1, NH (xi ) ⊆ {u, v}. All vertices that
are adjacent in H only to u are true twins in G. The same applies to vertices
that are adjacent only to v and also to those that are adjacent to both u and
v. Since the size of every set of true twins in G is bounded by c1 , we have
|{x2 , . . . , xk−1 }| ≤ 3c1 and hence k ≤ 3c1 + 2.
t
u
Lemma 22. Let G be a graph and H be a minimal square root of G such that
pw(H) ≤ 2. If u, v ∈ VH , then the number of common neighbors of u and v
in H is bounded by c1 + 2.
Proof. Suppose NH (u) ∩ NH (v) = {x1 , . . . , xt }. In the path decomposition of
H, for each i, we need a bag containing u and xi and a bag containing v
and xi . As pw(H) ≤ 2, this implies the existence of one bag Bi = {u, v, xi }
for each i. Suppose B1 , . . . , Bt appear in the path decomposition in this order.
Lemma 18 and the fact that {x2 , . . . , xt−1 } ⊂ NH (u) ∩ NH (v) imply that the
vertices x2 , x3 , . . . , xt−1 are true twins in G and that the number of such vertices
is bounded by c1 . Hence, the number of common neighbors of two vertices in H
is bounded by c1 + 2.
t
u
Lemma 23. Let G be a graph and H be a minimal square root of G such that
pw(H) ≤ 2. Let u ∈ VG and c2 = 6 · 21(c1 + 2). If dH (u) ≥ c2 , then there
exist five vertices x1 , . . . , x5 in NG (u) such that dG−u (xi , xj ) ≥ 3 for all i, j ∈
{1, 2, 3, 4, 5}.
Proof. Let u ∈ VG be such that dH (u) ≥ c2 . We choose a set of bags B1 , . . . , Bl
in the path decomposition of H such that u ∈ Bi . Then for all i and for all
x ∈ NH (u), there exists an i such that x ∈ Bi . Note that some neighbors of u
might appear in more than one bag. Let k1 be the smallest integer such that
1
∪ki=1
Bi contains at least three distinct vertices of NH (u). Since u belongs to all
1
bags, at least one of these three neighbors in ∪ki=1
Bi does not appear in Bk1 .
19

Let v1 be such a vertex. In general, let kj be the smallest integer greater than
kj
kj−1 such that ∪i=k
Bi contains at least five new vertices of NH (u). Since
j−1
u belongs to all bags, there is at least one vertex among the five that appears
neither in Bkj−1 nor in Bkj . Let vj be such a vertex. Hence we obtain a set
{v1 , . . . , vt } ⊂ NH (u) that is an independent set. Since dH (u) ≥ c2 = 6·21(c1 +2),
we have t ≥ 21(c1 + 2). For each vi , we pick xi ∈ NH (vi ) such that xi 6= xj if
i 6= j. Since t ≥ 21(c1 + 2) and by Lemma 22, we can pick at least 21 such
vertices. For simplicity, we assume that {v1 , . . . , v21 } is a set of such vertices.
For each i, let Ai be a bag containing vi and u. For 2 ≤ i ≤ 20, we can assume
Ai = {vi , xi , u}. Note that xi and xi+1 might be adjacent in H, but xi cannot be
a neighbor of xk , with k ≥ i + 2, because of the existence of bag {vi+1 , xi+1 , u}.
For the same reason, xi cannot be adjacent to vk for some k ≥ i + 2. Also, if
k ≥ i + 2, all paths in H from xi to xk contain either xi+1 or vi+1 . The same
applies to the paths from xi to vk for some k ≥ i + 2. Then {x1 , x6 , x11 , x16 , x21 }
are vertices that are pairwise at distance at least 3 in G − u.
t
u
Lemma 24. Let G be a graph and H be a minimal square root of G such that
pw(H) ≤ 2. If G has five vertices x1 , . . . , x5 ∈ NG (u) such that dG−u (xi , xj ) ≥ 3,
then for any x ∈ NG (u), xu ∈
/ EH if and only if there exists an i ∈ {1, . . . , 5}
such that dG−u (x, xi ) ≥ 3.
Proof. By Lemma 3, if there exists i ∈ {1, . . . , 5} such that dG−u (x, xi ) ≥ 3,
then xu ∈
/ EH .
Let x ∈ NG (u) be such that xu ∈
/ EH . We need to prove that there exists an
i such that dG−u (x, xi ) ≥ 3. This holds if x = xj for some j ∈ {1, . . . , 5}. Note
also that uxi ∈
/ EH because dG−u (xi , xj ) ≥ 3. Then for each i there exists vi
such that xi vi ∈ EH and vi u ∈ EH . If i 6= j, then vi 6= vj , otherwise xi and xj
would be adjacent in G. Moreover, vi vj ∈
/ EH , otherwise dG−u (xi , xj ) = 2.
Without loss of generality assume that v1 , . . . , v5 appear in this order in
the path decomposition of H. This implies the existence of the bags {v2 , x2 , u},
{v3 , x3 , u} and {v4 , x4 , u} in the path decomposition of H. Consider the bags
containing x.
If x appears before v2 , consider the distance between x and x4 . If the shortest path between x and x4 in G − u contains x2 or x3 , then dG−u (x, x4 ) ≥
dG−u (x, x3 ) ≥ 3. If it does not contain x2 and x3 , then it must contain either
v2 , v3 or another neighbor of u that appeared previously in the path decomposition and has no common neighbor with x4 in H. However, dG−u (v2 , x4 ) ≥ 2,
otherwise dG−u (x2 , x4 ) < 3. As dG−u (v2 , x4 ) ≥ 2, we have dG−u (x, x4 ) ≥ 3.
If x appears between {v2 , x2 , u} and {v3 , x3 , u}, consider dG−u (x, x5 ). By the
same argument we obtain that dG−u (x, x5 ) ≥ 3, because of the existence of bags
{v3 , x3 , u} and {v4 , x4 , u}. The other cases follow by symmetry.
t
u
Given a vertex u ∈ VG such that dH (u) ≥ c2 , we define Ru = {w ∈
NG (u) | uw ∈ EH } and Bu = {w ∈ NG (u) | uw ∈
/ EH }. Let u1 , u2 ∈ Ru .
If u1 u2 ∈ EH , by Observation 5, there exists a vertex v that is adjacent to at
least one of u1 and u2 in H, but is not adjacent to u. Assume v is adjacent
to u1 . This implies v ∈ Bu . Moreover, as u1 u2 ∈ EH , we have vu2 ∈ EG . In
20

other words, if there exists an edge in H between two vertices in Ru , then there
exists a vertex in Bu that is adjacent to both of them in G. We can now use this
observation to identify edges that will not be in a square root of G. Let v ∈ Bu
and Xv = {x ∈ Ru | xv ∈ EG }. We formalize this in the following lemma.
Lemma 25. Let u ∈ VG be such that dH (u) ≥ c2 and x, y ∈ NH (u) for a
minimal square root H of G with pw(H) ≤ 2. If there is no v ∈ Bu such that
x, y ∈ Xv , then xy ∈
/ EH .
Lemma 26. Let G be a graph and H a minimal square root of G such that
pw(H) ≤ 2. Let u be a vertex such that dH (u) ≥ c2 and v ∈ Bu . Let A and A0 be,
respectively, the first and the last bag in the path decomposition of H containing
u and a vertex of Xv . There exists a constant c3 such that the number of bags
between A and A0 is bounded by c3 = 15c1 + 4.
Proof. Let A and A0 be the first and the last bag in the path decomposition of
H containing u and a vertex of Xv . If v belongs to both A and A0 , then all the
bags between A and A0 (and including them) contain both u and v. Since for
any two bags X, Y in the path decomposition we have X * Y , for every vertex
appearing between A and A0 we have exactly one new bag. The number of such
vertices is bounded by 3c1 , by Lemma 21.
If v appears before A and is not contained in A, let x ∈ Xv be such that
x ∈ A0 . Since the bags containing v appear before A, x cannot be adjacent to
v in H. By the definition of Xv , they are at distance two. Let y ∈ VH be such
that xy, yv ∈ EH . There exists a bag containing {v, y}, which is before A in the
path decomposition and a bag containing {x, y, u}, which is between A and A0
since x ∈ Xv . The number of bags between A and {x, y, u} is bounded by 3c1 ,
by Lemma 21, as both contain y and u. The same holds for the number of bags
between {x, y, u} and A0 , as they both contain x and u.
If v appears in A but not in B 0 , let x ∈ Xv be such that x ∈ A0 . Since
xv ∈
/ EH , let xyv be a path between x and v in H. There exists a bag containing {v, y, u} and a bag containing {y, x, u} that appears after {v, y, u}. The
same constant 3c1 bounds the number of bags between A and {v, y, u}, between
{v, y, u} and {y, x, u} and between {y, x, u} and A0 .
If v appears between A and A0 but it is not contained in them, we proceed
in the same way as we did in the previous cases and the worst scenario is the
one where the vertices of Xv contained in A and A0 are not adjacent to v. Let
x ∈ Xv ∩ A and y ∈ VH be such that xyv is a path between x and v. We
take x0 and y 0 analogously with respect to A0 . By Lemma 21, the constant 3c1
bounds the number of bags between the following pairs of bags: A and {x, y, u},
{x, y, u} and {v, y, u}, {v, y, u} and {v, y 0 , u}, {v, y 0 , u} and {x0 , y 0 , u} and finally,
{x0 , y 0 , u} and A0 .
The total number of bags between A and A0 is therefore bounded by c3 =
15c1 + 4.
t
u
Let H be a minimal square root of G with pw(H) ≤ 2. Let G0H be the
subgraph of G obtained by deleting the edges between x, y ∈ NH (u), where
dH (u) ≥ c2 , such that there is no v ∈ Bu such that x, y ∈ Xv .
21

Lemma 27. There exists a constant c4 that depends neither on G nor on H
such that pw(G0H ) ≤ c4 .
Proof. Let H be a minimal square root of G. Let U be the set of vertices of H
such that dH (u) ≥ c2
For each u ∈ U , we do the following. Consider the bags B1 , . . . , Bt in the path
decomposition of H containing u and its neighbors. Starting from B1 , we pick the
first bag where a new neighbor of u appears. Let Bi be such a bag. As Bi contains
at least one vertex that is not contained in Bi−1 , we have |Bi ∩ Bi−1 | ≤ 2 and we
already know that u ∈ Bi ∩Bi−1 . In the bags B1 , . . . Bi−1 , we replace u by u1 . We
create a new bag between Bi−1 and Bi containing u1 , u2 and (Bi ∩ Bi−1 ) \ {u}.
In the bags Bi , . . . , Bt , we replace u by u2 . In general, for every bag Bk found
containing a new neighbor of u we do the following:
1. Create a new bag between Bk−1 and Bk containing uj+1 and the vertices of
Bk−1 ∩ Bk (note that uj ∈ Bk−1 ∩ Bk ).
2. In the bags Bk , . . . , Bt , replace uj by uj+1 .
3. In H, add the edge between uj and uj+1 and an edge between uj+1 and the
new found neighbor of u.
Let Ĥ be the graph obtained from H by the previous procedure. Note that
H is a contraction of Ĥ, as H can be obtained by contracting the edges of the
paths created for each vertex of U . Since we construct a path decomposition for
Ĥ with the same width as the one we had for H, we have pw(Ĥ) ≤ 2. We claim
that ∆(Ĥ) is bounded. If v ∈ VH \ U , then v has bounded degree in H and, in
each step of the above procedure, the degree of v is maintained. The vertices ui
created for each vertex of U have degree bounded by three. Thus the graph Ĥ
has indeed bounded degree.
We claim that G0H is a minor of Ĥ c3 +1 . Let Ĝ be obtained from Ĥ c3 +1 by
the contraction of the paths created for each vertex of U . We can now assume
that VĜ = VG0H . We now show that G0H is a subgraph of Ĝ.
Every edge of G0H that belongs to EH is also an edge of Ĥ c3 +1 . Let xy ∈ EG0H
be such that xy ∈
/ EH . As H is a square root of G, there exists u ∈ VG0H such that
xu, yu ∈ EH . Denote by X 0 and Y 0 respectively the sets of vertices of Ĥ that
were contracted to x and y. If u ∈
/ U , by the construction of Ĥ, there are x0 ∈ X 0
0
0
0
0
and y ∈ Y such that x u, y u ∈ EĤ and therefore x0 y 0 ∈ Ĥ c3 +1 and xy ∈ EĜ . If
u ∈ U , there exists a path ui . . . uj in Ĥ, x0 ∈ X and y 0 ∈ Y such that ui x0 ∈ EĤ
and uj y 0 ∈ EĤ . Since xy ∈ EG0H and u ∈ U , we know that x, y ∈ Xv for some
v, otherwise we would have deleted this edge in the construction of G0H . As the
number of bags containing u and vertices of Xv is bounded by c3 by Lemma 26,
the length of the path ui . . . uj is at most c3 . This implies that dĤ (x0 , y 0 ) ≤ c3 +1
and hence x0 y 0 ∈ EĤ c3 +1 , which implies xy ∈ EĜ .
Since G0H is a subgraph of Ĝ and Ĝ is a contraction of Ĥ c3 +1 , we conclude that
0
GH is a minor of Ĥ c3 +1 . Since G0H is a minor of Ĥ c3 +1 , pw(G0 ) ≤ pw(Ĥ c3 +1 ).
As Ĥ has pathwidth at most 2, pw(Ĥ) ≤ 2. Since Ĥ has bounded degree, by
Observation 3, we obtain a constant c4 such that pw(G0H ) ≤ c4 .
t
u
22

4.2

The Algorithm

Let G be the input graph. It is sufficient to solve Root of Pathwidth ≤ 2 for
connected graphs. Hence, we assume that G is connected and has n ≥ 2 vertices.
First, we preprocess G using Lemma 19 to reduce the number of true twins
that a given vertex of VG might have. To do so, we exhaustively apply the
following rule, which is safe by Lemma 20.
Twin reduction. If G has a set X of true twins of size at least c1 + 1, then
delete an arbitrary u ∈ X from G.
For simplicity, we call the graph obtained by exhaustive application of the Twin
reduction rule G again.
In the next stage of our algorithm we label some edges of G red or blue in
such a way that the edges labeled red are included in every minimal square root
of pathwidth at most 2 and the blue edges are not included in any minimal
square root of pathwidth at most 2. We denote by R the set of red edges and by
B the set of blue edges. We also construct a set of vertices U of G such that for
every u ∈ U , the edges incident to u are labeled red or blue.
Labeling. Set U = ∅, R = ∅ and B = ∅. For each u ∈ VG such that there are
five distinct vertices in NG (u) that are at distance at least 3 from each other in
G − u do the following:
(i)
(ii)
(iii)
(iv)
(v)

set U = U ∪ {u},
set B 0 = {ux ∈ EG | there is 1 ≤ i ≤ 5 s.t. distG−u (x, vi ) ≥ 3},
set R0 = {ux | x ∈ NG (u)} \ B 0 ,
set R = R ∪ R0 and B = B ∪ B 0 ,
if R ∩ B 6= ∅, then return a no-answer and stop.
Lemmas 23 and 24 imply the following claim.

Lemma 28. If G has a square root of pathwidth at most 2, then Labeling does
not stop in step (v). Moreover, R ⊆ EH , B ∩ EH = ∅ and every vertex u ∈ VG
with dH (u) ≥ c2 is included in U .
Next, we find the set of edges xy with xu, yu ∈ R for some u in U that are
not an edge in any square root of pathwidth at most 2. Finding irrelevant
edges. Set S = ∅. For each u ∈ U and each pair of distinct x, y ∈ NG (u) such
that ux, uy ∈ R and xy ∈ EG do the following.
(i) If there is no v ∈ NG (u) such that vu ∈ B and x, y ∈ NG (v), then include
xy in S.
(ii) If R ∩ S 6= ∅, then return a no-answer and stop.
By Lemma 25, we obtain the following claim.
Lemma 29. If G has a square root of pathwidth at most 2, then Finding irrelevant edges does not stop in step (ii), and if H is such a square root of G,
then S ∩ EH = ∅.
23

Assume that we did not stop during the execution of Finding irrelevant
edges. Let G0 = G − S. We show the following.
Lemma 30. The graph G has a square root of pathwidth at most 2 if and only
if there is a set L ⊆ EG0 such that
(i)
(ii)
(iii)
(iv)

R ⊆ L, B ∩ L = ∅,
for any xy ∈ EG0 , xy ∈ L or there is z ∈ VG0 such that xz, yz ∈ L,
for any distinct edges xz, yz ∈ L, xy ∈ EG0 or xy ∈ S,
the graph H = (VG , L) is such that pw(H) ≤ 2.

Proof. Let H be a square root of pathwidth at most 2 of G. By Lemma 29,
EH ∩ S = ∅, i.e., EH ⊆ EG0 . Let L = EH . It is straightforward to verify that
(i)–(iv) are fulfilled. Assume now that there is L ⊆ EG0 such that (i)–(iv) hold.
Then we have that H = (VG , L) is a square root of pathwidth at most 2 of G. t
u
To complete the description of the algorithm, it remains to show how to
check the existence of a set of edges L satisfying (i)–(iv) of Lemma 30 for given
G0 , R, B and S. If G has a minimal square root H with pw(H) ≤ 2, then G0
is a subgraph of G0H by Lemmas 23 and 25. Then by Lemma 27, pw(G0 ) ≤ c4 .
Therefore, pw(G0 ) ≤ c4 for a yes-instance. By Lemma 2, it is possible to verify
in linear time whether it holds. If pw(G0 ) > c4 , we conclude that we have a noinstance and stop. Otherwise, notice that properties (i) – (iv) can be expressed
in monadic second order logic. In particular, (iv) can be expressed using the
property that the class of graphs of pathwidth at most 2 is defined by the set
of forbidden minors given by Kinnersley and Langston in [14]. Then we use
Courcelle’s theorem [6] to decide in linear time whether L exists or not.
Now we evaluate the running time of our algorithm. We can find classes of
true twin vertices of the input n-vertex graph G in time O(n3 ). Therefore, Twin
reduction can be done in time O(n3 ). For every vertex u, we can compute the
distances between the vertices of NG (u) in G − u in time O(n3 ). It implies that
Labeling can be done in time O(n6 ). Finding irrelevant edges can be done
in time O(n4 ) by checking O(n2 ) pairs of vertices x and y. Then G0 can be
constructed in linear time. Finally, checking whether pw(G0 ) ≤ c4 and deciding
whether there is a set of edges L satisfying the required properties can be done
in linear time by Lemma 2 and Courcelle’s theorem [6] respectively. This implies
that the total running time is also O(n6 ).

5

Conclusions

We proved that H-Square Root is polynomial-time solvable when H is the
class of outerplanar graphs or the class of graphs of pathwidth at most 2. The
same result holds if H is any subclass of the class of outerplanar graphs that is
closed under edge deletion and that can be expressed in monadic second-order
logic (for instance, if H is the class of cactus graphs). We conclude by posing
two questions:
24

– Is H-Square Root polynomial-time solvable for every class H of graphs of
bounded pathwidth?
– Is H-Square Root polynomial-time solvable if H is the class of planar
graphs?

References
1. Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small
treewidth. SIAM Journal on Computing 25, 305–1317 (1996)
2. Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor.
Comput. Sci. 209(1-2): 1-45 (1998)
3. Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358–402 (1996)
4. Cochefert, M., Couturier, J., Golovach, P.A., Kratsch, D., Paulusma, D.: Sparse
square roots. In: Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013. LNCS, vol. 8165, pp. 177–188. Springer (2013)
5. Cochefert, M., Couturier, J., Golovach, P.A., Kratsch, D., Paulusma, D.: Parameterized algorithms for finding square roots. Algorithmica 74, 602–629 (2016)
6. Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions,
minor and complexity issues. Informatique Théorique et Applications 26, 257–286
(1992)
7. Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic - A
Language-Theoretic Approach, Encyclopedia of mathematics and its applications,
vol. 138. Cambridge University Press (2012)
8. Diestel, R.: Graph Theory, 4th Edition, Graduate Texts in Mathematics, vol. 173.
Springer (2012)
9. Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. CoRR abs/1210.7684 (2012)
10. Farzad, B., Lau, L.C., Le, V.B., Tuy, N.N.: Complexity of finding graph roots with
girth conditions. Algorithmica 62, 38–53 (2012)
11. Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: Finding cactus roots in
polynomial time. In: Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016). LNCS, vol. 9843, pp. 253–265 (2016)
12. Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: A linear kernel for finding
square roots of almost planar graphs. In: Proceedings of the 15th Scandinavian
Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics, vol. 53, pp. 4:1–4:14 (2016)
13. Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: Squares of low clique
number. In: 14th Cologne Twente Workshop 2016 (CTW 2016). Electronic Notes
in Discrete Mathematics, vol. 55, pp. 195–198 (2016)
14. Kinnersley, N.G., Langston, M.A.: Obstruction set isolation for the gate matrix
layout problem. Discrete Applied Mathematics 54(2-3), 169–213 (1994)
15. Lau, L.C.: Bipartite roots of graphs. ACM Transactions on Algorithms 2, 178–208
(2006)
16. Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal
graphs. SIAM Journal on Discrete Mathematics 18, 83–102 (2004)
17. Le, V.B., Oversberg, A., Schaudt, O.: Polynomial time recognition of squares of
ptolemaic graphs and 3-sun-free split graphs. Theoretical Computer Science 602,
39–49 (2015)

25

18. Le, V.B., Oversberg, A., Schaudt, O.: A unified approach for recognizing squares
of split graphs. Theoretical Computer Science 648, 26–33 (2016)
19. Le, V.B., Tuy, N.N.: The square of a block graph. Discrete Mathematics 310, 734–
741 (2010)
20. Le, V.B., Tuy, N.N.: A good characterization of squares of strongly chordal split
graphs. Information Processing Letters 111, 120–123 (2011)
21. Lin, Y., Skiena, S.: Algorithms for square roots of graphs. SIAM Journal on Discrete Mathematics 8, 99–118 (1995)
22. Milanic, M., Oversberg, A., Schaudt, O.: A characterization of line graphs that are
squares of graphs. Discrete Applied Mathematics 173, 83–91 (2014)
23. Milanic, M., Schaudt, O.: Computing square roots of trivially perfect and threshold
graphs. Discrete Applied Mathematics 161, 1538–1545 (2013)
24. Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Applied
Mathematics 54, 81–88 (1994)
25. Mukhopadhyay, A.: The square root of a graph. Journal of Combinatorial Theory
2, 290–295 (1967)
26. Nestoridis, N.V., Thilikos, D.M.: Square roots of minor closed graph classes. Discrete Applied Mathematics 168, 34–39 (2014)
27. Ross, I.C., Harary, F.: The square of a tree. Bell System Technical Journal 39,
641–647 (1960)
28. Syslo, M.M.: Characterizations of outerplanar graphs. Discrete Math. 26(1), 47–53
(1979)

26

