Graph Isomorphism for unit square graphs

arXiv:1602.08371v2 [] 22 Jun 2016

Daniel Neuen
RWTH Aachen University
neuen@informatik.rwth-aachen.de

Abstract
In the past decades for more and more graph classes the Graph Isomorphism Problem was
shown to be solvable in polynomial time. An interesting family of graph classes arises from
intersection graphs of geometric objects. In this work we show that the Graph Isomorphism
Problem for unit square graphs, intersection graphs of axis-parallel unit squares in the plane,
can be solved in polynomial time. Since the recognition problem for this class of graphs is
NP-hard we can not rely on standard techniques for geometric graphs based on constructing a
canonical realization. Instead, we develop new techniques which combine structural insights
into the class of unit square graphs with understanding of the automorphism group of such
graphs. For the latter we introduce a generalization of bounded degree graphs which is used
to capture the main structure of unit square graphs. Using group theoretic algorithms we
obtain sufficient information to solve the isomorphism problem for unit square graphs.

1

Introduction

The Graph Isomorphism Problem is one of the most famous open problems in theoretical computer science. In the past three decades the problem was intensively studied but only recently the
upper bound on the complexity could be improved to quasipolynomial time [Bab15]. However,
it is still open whether the Graph Isomorphism Problem can be solved in polynomial time. In
this work we focus on geometric graph classes, that is, graph classes that arise as intersection
graphs of geometric objects. In an intersection graph the vertices are identified with geometric
objects and two vertices are connected if the corresponding objects intersect.
One of the most basic geometric graph classes is the class of interval graphs, intersection
graphs of intervals on the real line. Although this graph class is quite restrictive there are a
number of practical applications and specialized algorithms for interval graphs (see e.g. [Gol04]).
The Graph Isomorphism Problem on interval graphs can be solved in linear time [CB81] as well
as in logarithmic space [KKLV11]. However, for several generalizations of interval graphs the
complexity of the Graph Isomorphism Problem is unknown. This includes for example circular
arc graphs (see [CLM+ 13]) and triangle graphs (see [Ueh14]). On the other hand a graph class
is GI-complete if the Graph Isomorphism Problem for this class is as difficult as the general
problem under polynomial time reductions. An example of a GI-complete geometric class is
the class of grid intersection graphs, bipartite intersection graphs of horizontal and vertical line
segments in the plane [Ueh08]. As an immediate consequence the class of intersection graphs
of axis-parallel rectangles is also GI-complete. Unit square graphs, intersection graphs of axisparallel unit squares, are a natural restriction for the rectangle graphs. This raises the question
for the complexity of the isomorphism problem for unit square graphs. In this work we prove
that the Graph Isomorphism Problem for unit square graphs can be solved in polynomial time.
Besides being a natural restriction to rectangle graphs, another central motivation to study this
1

problem comes from unit disk graphs, intersection graphs of unit circles in the plane. Unit disk
graphs where first studied by Clark, Colbourn and Johnson in [CCJ90] and for several problems
specialized algorithms have been proposed (see e.g. [FLS12]). Practical applications arise for
example from broadcast networks where each broadcast station is represented by a vertex and
two stations communicate with each other if the distance between them does not exceed the
broadcast range. In the work of Clark et al. two problems, namely the recognition problem
and the isomorphism problem, were left open. While recognition of unit disk graphs proved to
be NP-hard [BK98], the isomorphism problem for unit disk graphs is still open. Unit square
graphs present a natural variant to unit disk graphs as we just replace the Euclidean norm by
the Manhattan norm. Also, going from unit disks to unit squares removes geometric intricacies
and tends to simplify the structure of graphs but maintains several key aspects of the problem.
In particular, for unit disk as well as unit square graphs vertices only have a bounded number
of independent neighbors (set of pairwise non-adjacent neighbors) and the structure of graphs
seems to be a mixture of bounded degree and planarity. Hence, solving the isomorphism problem
for unit square graphs might be a step towards solving the same problem for unit disk graphs.
Furthermore, in [Ueh08, Ueh14] Uehara also asked for the complexity of graph isomorphism for
unit grid intersection graphs. Unit grid intersection graphs can be seen as bipartite versions of
unit square graphs in the following sense: A bipartite graph is a unit grid intersection graph
if and only if it is the intersection graph of unit squares where intersections between squares
belonging to vertices on the same side of the bipartition are ignored. Hence, the result presented
in this work shows that in some sense the difficulty for unit grid intersection lies in recreating
the information which lines are close to each other.
Another interesting point arises from the fact that, like for unit disk graphs, recognition
of unit square graphs is NP-hard [Bre96]. Hence, we obtain an example of a natural graph
class with the interesting property that isomorphism tests can be performed in polynomial time
whereas recognition is NP-hard. Also, the hardness result rules out the classical approach to
attack the isomorphism problem. Typically, isomorphism tests for geometric graphs are based
on constructing a canonical geometric representation of the graph (see e.g. [KKLV11, KKV13])
but, as this would also solve the recognition problem, such an approach is not possible here.
Instead, our algorithm combines group theoretic techniques with geometric properties of unit
square graphs. For the group theoretic machinery we extend the results developed by Luks
[Luk82] to decide isomorphism for bounded degree graphs by also allowing for example large
cycles in the neighborhood of a vertex. On a geometric level this coincides in some sense with the
intuition that vertices in the neighborhood of some fixed vertex are cyclically arranged around
the central vertex. Using geometric properties of unit square graphs and known algorithms
for other geometric graph classes such as proper circular arc graphs we can canonically (in an
isomorphism-invariant way) extract such circular orderings, which can then be used by the group
theoretic machinery. For this, we show a series of results giving a deep insight into the structure
of neighborhoods of single vertices and neighborhoods of cliques within unit square graphs. These
results not only help us to understand the structure of unit square graphs, but also we obtain
significant knowledge about the structure of the automorphism group of a unit square graph.
However, an obvious obstacle to this approach comes from large cliques which are connected
in a uniform way to the rest of the graph and do not contain any significant structure. More
precisely, such cliques may be responsible for large symmetric groups which are subgroups of the
automorphism group of the whole graph. Since large symmetric groups form a clear obstacle
to the group theoretic machinery and can not be handled by Luks’ algorithm we have to cope
with these parts of the graph in a different way. Our second main result on the structure of unit
square graphs characterizes connections between cliques which are stable with respect to the
color refinement algorithm (see e.g. [BBG13, McK81]), and also establishes a close connection to
2

interval graphs. Building on this characterization we show that the color refinement algorithm
can be used to cope with the symmetric parts of the graph containing no significant structure.
Finally, combining the color refinement algorithm with the group theoretic machinery, we obtain
an algorithm to solve the isomorphism problem for unit square graphs.
The remainder of this paper is structured as follows. In the next section we give some
preliminaries and in Section 3 we prove some basic properties of unit square graphs. In Section
4 we analyze the local structure. In Sections 5 and 6 we compute the desired partitions together
with the canonical structure. Finally we discuss some related open problems in Section 7.

2
2.1

Preliminaries
Graphs

A graph is a pair G = (V, E) with vertex set V = V (G) and edge set E = E(G). In this paper
all graphs are undirected, so E(G) is always irreflexive and symmetric. The (open) neighborhood
of a vertex v ∈ V (G) is the set NG (v) = N (v) = {w ∈ V (G) | vw ∈ E(G)} and the size of
N (v) is the degree of v. The closed neighborhood is the set N [v] = N (v) ∪ {v}. Two vertices
v, w ∈ V (G) are connected twins if N [v] = N [w]. A path from v to w of length m is a sequence
u0 , . . . , um of distinct vertices with u0 = v and um = w, such that ui−1 ui ∈ E(G) for each
i ∈ [m] := {1, . . . , m}. The distance between v and w, d(v, w), is the length of a shortest path
from v to w. A colored graph is a tuple G = (V, E, c) where c : V (G) → N assigns each vertex a
unique color. For each color i ∈ N let Vi (G) = {v ∈ V (G) | c(v) = i}. Two graphs G and H are
isomorphic (G ∼
= H) if there is a bijection ϕ : V (G) → V (H), such that vw ∈ E(G) if and only if
ϕ(v)ϕ(w) ∈ E(H) for all v, w ∈ V (G). In this case the mapping ϕ is an isomorphism from G to
H. In case the input graphs are colored it is demanded that the isomorphism also preserves the
coloring of the vertices. The Graph Isomorphism Problem asks whether two given graphs G and
H are isomorphic. An isomorphism from a graph to itself is called an automorphism. The set
of automorphisms of a graph G, denoted by Aut(G), forms a subgroup of the symmetric group
over the vertex set.

2.2

Color Refinement

A very basic and fundamental method, which is a basic building block of many isomorphism tests,
is the color refinement algorithm (see e.g. [McK81]). The basic idea is to iteratively distinguish
vertices if they have a different number of neighbors in some color. A partition P of the vertices
is stable if for all X, Y ∈ P and all v, w ∈ X it holds that |N (v) ∩ Y | = |N (w) ∩ Y |. Further
a partition P refines another partition Q if for each X ∈ P there is some Y ∈ Q with X ⊆ Y .
The color refinement algorithm computes the unique coarsest stable partition refining the initial
color partition (i.e. the partition of the vertices according to their color). The coarsest stable
partition can be computed in almost linear time (see [McK81, BBG13]). We say color refinement
distinguishes two graphs if there is some class in the coarsest stable partition on the disjoint
union of the graphs that contains a different number of vertices from the two graphs. In this
case the two input graphs are not isomorphic.
The k-dimensional Weisfeiler-Leman algorithm is a generalization of the color refinement
algorithm (cf. [CFI92]). Instead of coloring only single vertices, the Weisfeiler-Leman algorithm
colors k-tuples of vertices. Initially each tuple is colored with the isomorphism type of the
underlying induced subgraph and then the coloring is refined in a similar way as by the color
refinement algorithm (see [CFI92] for a detailed description). We say k-dimensional WeisfeilerLeman identifies a graph class C if for every pair of non-isomorphic graphs G, H with G ∈ C the
3

k-dimensional Weisfeiler-Leman distinguishes between G and H.

2.3
2.3.1

Group Theory
Basic Facts

In this subsection we introduce some group theoretic notation. For a general introduction
to group theory we refer to [Rot95] whereas several group theoretic algorithms are given in
[HEO05, Ser03]. Since we only deal with automorphism groups of graphs we restrict ourselves
to permutation groups.
Let Ω be a finite set and n = |Ω|. The symmetric group Sym(Ω) over the set Ω is the group
containing all permutations on Ω. A permutation group over the set Ω is a subgroup of the
group Sym(Ω). Let Γ ≤ Sym(Ω) be a permutation group. For γ ∈ Γ and α ∈ Ω we denote
by αγ the image of α under the permutation γ. The set αΓ = {αγ | γ ∈ Γ} is the orbit of α.
The group Γ is transitive if αΓ = Ω for some (and thus for all) α ∈ Ω. The stabilizer of α is
StabΓ (α) = {γ ∈ Γ | αγ = α} which is a subgroup of Γ. For A ⊆ Ω let Aγ = {αγ | α ∈ A}.
The (setwise) stabilizer of A is StabΓ (A) = {γ ∈ Γ | Aγ = A}. The set A is called Γ-invariant if
Γ = StabΓ (A). For a partition P of the set Ω let P γ = {X γ | X ∈ P} which is again a partition
of Ω. The partition P is Γ-invariant if P γ = P for all γ ∈ Γ. The group Γ is abelian if γγ ′ = γ ′ γ
for all γ, γ ′ ∈ Γ. A subgroup N ≤ Γ is normal (N E Γ) if γ −1 N γ = {γ −1 nγ | n ∈ N } = N for
all γ ∈ Γ. A mapping ϕ : Γ → ∆ is a homomorphism if ϕ(γ1 )ϕ(γ2 ) = ϕ(γ1 γ2 ) for all γ1 , γ2 ∈ Γ.
Its kernel is ker(ϕ) = {γ ∈ Γ | ϕ(γ) = 1} E Γ and the image is im(ϕ) = {ϕ(γ) | γ ∈ Γ} ≤ ∆.
A set S ⊆ Γ is a generating set if each γ ∈ Γ can be written as γ = s1 . . . sk for some
s1 , . . . , sk ∈ S. In order to allow efficient computations permutation groups are represented by
small generating sets. For each permutation group on a set of size n there is a generating set of
size n − 1 [MN87]. In practice generating sets of quadratic size are typically used to represent
permutation groups (cf. [FHL80]).
2.3.2

Bounded Composition Series

In this work we shall be interested in a particular subclass of permutation groups, namely groups
with bounded non-abelian composition factors. Let Γ be a group. A normal series is a sequence
of subgroups Γ = Λ0 D Λ1 D · · · D Λk = {1}. The length of the series is k and the groups
Λi−1 /Λi are the factor groups of the series, i ∈ [k]. A composition series is a strictly decreasing
normal series of maximal length. For every finite group Γ all composition series have the same
family of factor groups considered as a multi-set (cf. [Rot95]). A composition factor of a finite
group Γ is a factor group of a composition series of Γ.
Definition 2.1. Let d ∈ N. The family Γd contains all finite groups Γ for which all non-abelian
composition factors are isomorphic to subgroups of Sd = Sym([d]).
The class of Γd -groups is closed under subgroups and homomorphic images. Furthermore, for
groups N E Γ it holds that Γ ∈ Γd if and only if N ∈ Γd and Γ/N ∈ Γd . A group Γ is solvable
if every composition factor is abelian. Two examples of solvable groups, that are particularly
important for this work, are cyclic groups and dihedral groups which are the automorphism
groups of directed cycles and undirected cycles. Note that every solvable group is a Γd -group for
every d ∈ N.
2.3.3

Algorithms

The Setwise Stabilizer Problem asks, given a permutation group Γ ≤ Sym(Ω) and A ⊆ Ω, for a
generating set of the group StabΓ (A). A central motivation to consider Γd -groups is the following
4

result.
Proposition 2.2. Let d ∈ N. The Setwise Stabilizer Problem for groups in Γd can be solved in
polynomial time.
A weaker version of this statement was proved by Luks in [Luk82] considering only groups
where all composition factors are isomorphic to subgroups of Sd . For the more general version
stated above we refer to [Bab14]. This result is for example used by Luks to solve graph isomorphism for graphs of bounded degree [Luk82], but it can also be applied to more general graph
classes. In this work we are interested in graphs which we call t-circle-bounded graphs. For a
graph G and a set X ⊆ V (G) we write G[X] to denote the induced subgraph of G with vertex
set X.
Definition 2.3. A colored
S graph G = (V, E, c) with c : V (G) → [k] is t-circle-bounded if for each
i ∈ [k] and X ⊆ V<i := j<i Vj (G) the graph
Gi,X := G[{v ∈ Vi (G) | N (v) ∩ V<i = X}]

is the disjoint union of at most t connected graphs of maximum degree two.
The t-circle-bounded graphs are closely related to t-bounded graphs which are similarly defined with the size of Gi,X bounded by t (see [BCS+ 13]). From an algorithmic point of view
we can use very similar methods for the isomorphism problem on t-circle-bounded graphs as
for t-bounded graphs. For the sake of completeness we still give a complete description. This
requires the following result due to Miller on hypergraphs which is also used in the algorithm
for t-bounded graphs. A hypergraph is a pair H = (V, E) with finite vertex set V and a set of
hyperedges E ⊆ 2V .
Proposition 2.4 (Miller, [Mil83]). Let t ∈ N. Let H = (V, E) be a hypergraph and Γ ≤ Sym(V ),
such that Γ ∈ Γt . Then a generating set for the group Aut(H)∩Γ can be computed in polynomial
time.
Note, that this result also holds for edge-colored hypergraphs by considering one color after
the other.
Theorem 2.5. Let G be a t-circle-bounded graph. Then Aut(G) ∈ Γt .
Proof. We proof by induction on i ∈ [k] that Aut(G[V≤i ]) ∈ Γt . For i = 1 the graph G[V1 ] is
the disjoint union of at most t connected graphs of maximum degree two. A connected graph
of maximum degree two is either a path or a cycle. In both cases the automorphism group is
solvable and thus it is a Γt -group. Let X1 , . . . , Xs be the connected components of G[V1 ]. Then
s ≤ t and P1 = {X1 , . . . , Xs } is an Aut(G[V1 ])-invariant partition. Consider the natural action
ψ : Aut(G[V1 ]) → Sym(P1 ) of Aut(G[V1 ]) on the connected components. Then ker(ψ) ∈ Γt ,
since it is a direct product of solvable groups, and im(ψ) ≤ St . Hence, Aut(G[V1 ]) ∈ Γt .
For the inductive step suppose Aut(G[V<i ]) ∈ Γt . Consider the restriction ϕi : Aut(G[V≤i ]) →
Aut(G[V<i ]) : γ 7→ γ|V<i . Then im(ϕi ) ≤ Aut(G[V<i ]) and hence, im(ϕi ) ∈ Γt by induction
hypothesis. So it remains to prove that ker(ϕi ) ∈ Γt . For each X ⊆ V<i the set V [Gi,X ] is
ker(ϕi )-invariant. So
Aut(Gi,X ).
ker(ϕi ) ≤

×

X⊆V<i : V [Gi,X ]6=∅

Since a subgroup of a direct product of Γt -groups is still a Γt -group it suffices to prove that
Aut(Gi,X ) ∈ Γt . But this follows by the same argument as in the base step of the induction.
5

Theorem 2.6. The Graph Isomorphism Problem for t-circle-bounded graphs can be solved in
polynomial time.
Proof. By standard reduction techniques it suffices to show that a generating set for the automorphism group of a t-circle-bounded graph can be computed in polynomial time.
Let G be a t-circle-bounded graph. We proof by induction on i ∈ [k] that a generating set for
Aut(G[V≤i ]) can be computed in polynomial time. For i = 1 the graph G[V1 ] has maximum degree
two and thus, a generating set can be computed in polynomial time. So let i > 1 and suppose
we are given a generating set for the group Aut(G[V<i ]). Let Ei = {X ⊆ V<i | V (Gi,X ) 6= ∅} and
define the hypergraph Hi = (V<i , Ei ). Let Gi = (V≤i , E(Gi )) with
E(Gi ) = E(G[V<i ]) ∪ {vw ∈ E(G) | ∃X ∈ Ei : vw ∈ E(Gi,X )}.
Then Aut(G[V≤i ]) ≤ Aut(Gi ) since Gi is defined in an isomorphism-invariant way. Consider
the homomorphism ϕi : Aut(Gi ) → Aut(G[V<i ]) : γ 7→ γ|V<i . Then ker(ϕi ) = X∈Ei Aut(Gi,X )
which can be computed in polynomial time. Further ker(ϕi ) ∈ Γt by Theorem 2.5. Let K be a
generating set for the kernel ker(ϕi ). Now let X ∼ Y if Gi,X ∼
= Gi,Y for all X, Y ∈ Ei and define
a coloring c : Ei → N, so that each color class corresponds to an equivalence class of ∼. Then
im(ϕi ) = Aut(H, c) ∩ Aut(G[V<i ]). Let S be a generating set for im(ϕi ) which can be computed
in polynomial time by Proposition 2.4. For s ∈ S compute some s′ ∈ ϕ−1
i (s) using isomorphisms
between Gi,X and Gi,X s for each X ∈ Ei . Let S ′ be the set of all elements s′ . Then K ∪ S ′ is a
generating set for Aut(Gi ). Furthermore Aut(Gi ) ∈ Γt . So a generating set for Aut(G[V≤i ]) can
be computed in polynomial time using Proposition 2.2.

×

2.4

Proper circular arc graphs

A graph G is a unit interval graph if G is the intersection graph of unit intervals on the real
line. A graph G is a proper circular arc graph if G is the intersection graph of arcs on a circle,
such that for no two arcs, one is properly contained in the other. A characterization of unit
interval graphs and proper circular arc graphs in terms of forbidden induced subgraphs is given
in [Tuc74]. For our purposes the following statements are sufficient. Some relevant forbidden
induced subgraphs are also depicted in Figure 2.1.
Proposition 2.7. A graph G is a unit interval graph if and only if there are no induced subgraphs
isomorphic to Cn+4 for n ≥ 0, S3 , K1,3 and net.
Here, Cn denotes a cycle of length n. Furthermore we denote by G ∪ H the disjoint union of
G and H and the graph G is the complement graph of G.
Proposition 2.8. Let G be a graph, such that NG [v] is a unit interval graph for every v ∈ V (G)
and there are no induced subgraphs isomorphic to K1 ∪ Cn+4 for n ≥ 0, K1 ∪ S3 , T2 , C6 and
net. Then G is a proper circular arc graph.
We also require the following characterization for proper circular arc graphs. A vertex is
universal if it is adjacent to all other vertices. A graph G is twin-free if it does not contain
connected twins and G is co-bipartite if G is bipartite.
Proposition 2.9 ([KKV12], Theorem 3). Let G be a graph without universal vertices. Then G
is a proper circular arc graph if and only if there is a cycle H with V (G) = V (H), such that
1. NG [v] induces a connected subgraph in H for each v ∈ V (G)

6

w7
w3
w6

w6
w6

v

w5

w1

w4

w2

w2

(a) K1 ∪ S3

w1

w2

w1
w4

w4

w3

w5

(b) K1,3 (claw)

(c) T2
w3

w1,2

w2,2
v3
w1,3

w2,3
v1

w1,1

w2,1

v2

w1

(d) C6

w2
(e) net

Figure 2.1: Some forbidden induced subgraphs of proper circular arc graphs
2. For all v, w ∈ V (G) it holds that if NG [v] ⊆ NG [w] then the two paths share an endpoint
in H.
Furthermore, if G is connected, twin-free and not co-bipartite, the cycle H is unique [Hua95].
Additionally, given some proper circular arc graph, a cycle H can be computed in polynomial
time (see [KKV12]). This gives us the following proposition.
Proposition 2.10. Let G be a connected proper circular arc graph, such that G is not bipartite.
Further let ∼G be the connected twins relation and P the corresponding partition into equivalence
classes. Then one can compute in polynomial time a canonical connected graph H, such that
V (H) = P and H has maximum degree two.

3

Basic Properties

For unit square graphs there are several possible definitions. The most obvious one is to describe
vertices by axis-parallel unit squares with edges connecting two vertices if the unit squares
intersect. Alternatively it can also be demanded that vertices represented by unit squares are
connected if the center of the first square is contained in the other square. Another possibility is
to describe vertices by points in the plane. Note that two squares with unit side length intersect
if and only if the distance between their centers using the maximum norm is at most one. Thus,
two vertices are connected if the distance between the points is at most one using the maximum
norm. Furthermore, a unit square contains the center point of another unit square if and only if
the distance between both centers is at most one half using the maximum norm. By applying a
scaling argument this also gives us the equivalence to the second definition. In this paper we work
with the last definition, that is we represent vertices by points in the plane. For a point p ∈ Rk
we denote by pi the i-th component of p, i ∈ [k]. The L∞ -norm is defined as kpk∞ = maxi∈[k] pi .

7

Definition 3.1. A k-dimensional L∞ -realization of a graph G is a mapping f : V (G) → Rk
such that vw ∈ E(G) if and only if kf (v) − f (w)k∞ ≤ 1 for all v, w ∈ V (G). A unit square graph
is a graph having a two-dimensional L∞ -realization.
Observe that graphs with 1-dimensional L∞ -realization are exactly the unit interval graphs.
For the remainder of this paper we focus on unit square graphs and just use the term realization
for a two-dimensional L∞ -realization. Following our previous notation, for a realization f :
V (G) → R2 and a vertex v ∈ V (G), we denote by (f (v))i the i-th component of f (v). This is
also abbreviated by f (v)i , i ∈ [2]. We start by showing a series of basic properties for unit square
graphs.
Lemma 3.2. Let G be a unit square graph. Then G has no induced subgraph isomorphic to
K1,5 .
Proof. Since the class of unit square graphs is hereditary (closed under induced subgraphs) it
suffices to show that K1,5 is not a unit square graph. Suppose towards a contradiction that there
exists a realization f : V (G) → R2 . Without loss of generality let f (v) = (0, 0) where v is the
center vertex connected to the other vertices w1 , . . . , w5 . Then f (wi ) ∈ [−1, 1]2 for all i ∈ [5].
Thus, there is some q1 , q2 ∈ {−1, 1}, such that there are i 6= j with f (wi ), f (wj ) ∈ [q1 , 0] × [q2 , 0]
(for simplicity we may use [1, 0] to denote the interval [0, 1]). But then there is an edge between
wi and wj which is a contradiction.
Remark 3.3. Let G be a unit square graph and f : V (G) → R2 a realization. Further let
X ⊆ V (G), such that there are a1 , b1 , a2 , b2 ∈ R with a1 ≤ b1 ≤ a1 + 1, a2 ≤ b2 and f (v) ∈
[a1 , b1 ] × [a2 , b2 ] for every v ∈ X. Then G[X] is a unit interval graph.
Lemma 3.4. Let G be a unit square graph. Then there is some v ∈ V (G), such that G[N [v]] is
a unit interval graph.
Proof. Let f : V (G) → R2 be a realization and choose v = argminv∈V (G) f (v)1 . Further let
a1 = f (v)1 , b1 = a1 + 1, a2 = f (v)2 − 1 and b2 = f (v)2 + 1. Then f (w) ∈ [a1 , b1 ] × [a2 , b2 ] for
every w ∈ N [v]. So G[N [v]] is a unit interval graph according to Remark 3.3.
Lemma 3.5. Let u, v ∈ V (G) be two non-adjacent vertices. Then N (u) ∩ N (v) defines a unit
interval graph with at most two independent vertices.
Proof. Without loss of generality assume f (u)1 + 1 ≤ f (v)1 . For w ∈ N (u) ∩ N (v) we obtain
f (u)1 ≤ f (w)1 ≤ f (v)1 . Without loss of generality let f (u) = (0, 0). Then f (w) ∈ [0, 1] × [−1, 1]
for every w ∈ N (u) ∩ N (v). So N (u) ∩ N (v) defines a unit interval graph according to Remark
3.3. Furthermore in this area there can be at most two independent vertices.
Corollary 3.6. Let G be a unit square graph. Then G has no induced subgraph isomorphic to
K2,3 , 3K2 (3K2 is the disjoint union of three K2 ) or T2 .
Proof. For K2,3 the two vertices on the left side have three independent common neighbors. The
graph 3K2 contains two non-adjacent vertices whose common neighborhood is a 4-cycle. Finally
T2 extends the graph 3K2 .
We also require some properties of maximal cliques. A clique is a set of vertices C ⊆ V (G),
such that vw ∈ E(G) for every two distinct v, w ∈ C. A maximal clique is a clique so that there
is no larger clique containing it. For a graph G the set of maximal cliques of G is denoted by
M(G).

8

Lemma 3.7. Let G be a unit square
T graph and C be a maximal clique of G. Then there are
v1 , . . . , v4 ∈ V (G), such that C = i∈[4] N [vi ].

Proof. Let f : V (G) → R2 be a realization
argminv∈C f (v)i and v2i =
T of G. Pick v2i−1 = T
argmaxv∈C f (v)i for i ∈ [2]. Clearly C ⊆ i∈[4] N [vi ]. So let w ∈ i∈[4] N [vi ] and v ∈ C. In
order to prove w ∈ C it suffices to show that kf (v)−f (w)k∞ ≤ 1, since v is chosen arbitrarily from
C. For i ∈ [2] it holds that f (v2i−1 )i ≤ f (v2i )i . If f (w)i ≤ f (v2i )i then −1 ≤ f (v2i )i −1−f (v)i ≤
f (w)i − f (v)i ≤ f (v2i )i − f (v)i ≤ 1. Otherwise f (w)i ≥ f (v2i−1 )i and −1 ≤ f (v2i−1 )i − f (v)i ≤
f (w)i − f (v)i ≤ f (v2i−1 )i + 1 − f (v)i ≤ 1.
The proof of the last lemma motivates us to describe maximal cliques by unit squares with
all points being inside the square belonging to the maximal clique.

Definition 3.8. Let G be a unit square graph, C ∈ M(G) and let f : V (G) → R2 be a realization.
The center of C with respect to f is the set zf (C) := {p ∈ R2 | ∀v ∈ C : kf (v) − pk∞ ≤ 21 }.
Choose v1 , . . . , v4 as in the last lemma and let pi = f (v2i−1 )2i +f (v2i )i for i ∈ [2]. Then p ∈
zf (C) and so zf (C) 6= ∅. Further for every p ∈ zf (C) the unit square with center placed at p
contains exactly those points that belong to C. This can easily be seen from the definition of
the center and using the triangle inequation. Thus, for two distinct maximal cliques C, D we get
zf (C) ∩ zf (D) = ∅.
Lemma 3.9. Let G be a unit square graph and C be a maximal clique of G. Further let
v2i−1 = argminv∈C f (v)i and v2i = argmaxv∈C f (v)i for i ∈ [2]. Then zf (C) = [f (v2 )1 −
1
1
1
1
2 , f (v1 )1 + 2 ] × [f (v4 )2 − 2 , f (v3 )2 + 2 ].
Proof. Clearly zf (C) ⊆ [f (v2 )1 − 21 , f (v1 )1 + 21 ] × [f (v4 )2 − 21 , f (v3 )2 + 12 ]. So let p ∈ [f (v2 )1 −
1
1
1
1
2 , f (v1 )1 + 2 ] × [f (v4 )2 − 2 , f (v3 )2 + 2 ] and w ∈ C. If f (w)1 ≥ p1 then 0 ≤ f (w)1 − p1 ≤
1
f (v2 )1 − p1 ≤ 2 . Otherwise f (w)1 ≤ p1 and hence, 0 ≤ p1 − f (w)1 ≤ p1 − f (v1 )1 ≤ 12 . The
argument for the second component is analogous. Thus, kw − pk∞ ≤ 12 .

4

Local Structure

The basic approach for our algorithm is group-theoretic. A main obstacle for group theoretic
approaches comes from large symmetric or alternating groups, that appear in the automorphism
group. For unit square graphs the central observation is that these groups can in a way only
arise from cliques. In this section we show how to cope with possibly very symmetric parts of
the graphs and give a corresponding reduction to get rid of them.

4.1

Connection to Interval graphs

In order to obtain a better understanding of how the symmetric parts may look like we start by
giving a translation from interval graphs to unit square graphs. This is based on the description
of maximal cliques introduced before. Let C1 , . . . , Ck be maximal cliques of a unit square graph,
such that for all i < j and all pi ∈ zf (Ci ), pj ∈ zf (Cj ) it holds that pib < pjb for b ∈ [2]. Then it
is not difficult to show that each vertex can only appear in consecutive maximal cliques. More
precisely, for each interval I ⊆ [k], there is a non-empty set of points P ⊆ R2 , such that for each
v ∈ V (G) with f (v) ∈ P it holds v ∈ Ci if and only if i ∈ I. A visualization is given in Figure
4.1b. This allows us to encode arbitrary interval graphs using unit square graphs.

9

C1 C2 C3 C4 C5 C6 C7
(a) An interval graph

(b) Constructed unit square graph

Figure 4.1: From interval to unit square graphs
Let G be a graph. Define the colored graph GM = (V (G) ∪ M(G), E(GM ), cGM ) with
E(GM ) = {vC | C ∈ M(G), v ∈ C} ∪ {vw | v 6= w ∈ V (G)} ∪ {CD | C 6= D ∈ M(G)}
and cGM (v) = cG (v) + 1 for v ∈ V (G), cGM (C) = 1 for C ∈ M(G). For a group Γ ≤ Sym(Ω)
and a set A ⊆ Ω the pointwise stabilizer is the group Stab•Γ (A) := {γ ∈ Γ | ∀α ∈ A : αγ = α}.
If A is invariant under Γ (i.e. Aγ = A for every γ ∈ Γ) we define the restriction of Γ to A as
Γ|A := {γ|A | γ ∈ Γ} where γ|A : A → A with γ|A (α) = γ(α).
Lemma 4.1. For every two graphs G and H it holds that
1. G ∼
= HM ,
= H if and only if GM ∼
2. Stab•Aut(GM ) (V (G)) = {1} (here 1 denotes the identify mapping),
3. Aut(GM )|V (G) = Aut(G).
Proof. This follows directly from the definition of GM and the fact that vw ∈ E(G) if and only
if there is some maximal clique C ∈ M(G) with v, w ∈ C.
We now use the fact that a graph G is an interval graph if and only if there is a linear order
on the maximal cliques, such that each vertex appears in consecutive maximal cliques [FG65].
For a vertex v ∈ V (G) let MG (v) = M(v) = {C ∈ M(G) | v ∈ C}.
Lemma 4.2. Let G be an interval graph. Then GM is a colored unit square graph.
Proof. Let < be a linear order on M(G), such that each vertex appears in consecutive maximal
cliques. Let k = |M(G)| and C1 < C2 < · · · < Ck be the maximal cliques of G. For each
v ∈ V (G) define av , bv ∈ [k] in such a way that M(v) = {Ci | av ≤ i ≤ bv }.
Consider the following realization f : V (GM ) → R2 with
f (Ci ) = (

i
i
− 1, )
k
k

and

av b v
,
− 1)
k k
for all v ∈ V (G). Clearly all vertices are connected to each other as well as all maximal cliques.
So let v ∈ V (G). Then | akv − ki + 1| = | avk−i + 1| ≤ 1 if and only if av ≤ i. Further | ki − bkv + 1| =
v
| i−b
k + 1| ≤ 1 if and only if i ≤ bv . So there is an edge between v ∈ V (G) and Ci ∈ M if and
only if av ≤ i ≤ bv if and only if v ∈ Ci .
f (v) = (

10

A visualization of the last lemma is given in Figure 4.1.
Corollary 4.3. For each colored interval graph G one can compute in polynomial time some
colored unit square graph H with Aut(G) ∼
= Aut(H).
Proof. This follows directly from Lemma 4.1 and 4.2.
In particular this construction implies that there are twin-free unit square graphs where the
automorphism group contains arbitrarily large symmetric groups which can not be handled by
the group theoretic approach due to Luks. For example consider the following graph Gn,k for
n, k ∈ N. The vertex set V (Gn,k ) = [n]≤k is the set of all words over the alphabet [n] of length at
most k and there is an edge vw ∈ E(Gn,k ) if v is a prefix of w (this is interpreted for an undirected
graph). First, Gn,k is an interval graph. To verify this consider the set [n]k of words of length k
with the natural lexicographic order. Then each vertex v ∈ V (Gn,k ) can be represented by the
interval In,k (v) = {w ∈ [n]k | v is prefix of w}. It is easy to check that two vertices are connected
if and only if the corresponding intervals intersect. The automorphism group of Gn,k is a wreath
product of the automorphism group of Gn,k−1 by a symmetric group on n points.
One of the main contributions of this work is to show that within automorphism groups of
unit square graphs such symmetric groups only appear in a local setting. Here, local refers to
a small area in the realization of a graph G. In the presented example the vertices of each
color class are close together and in particular they induce a clique. The main target for this
section is to present a method how to cope with the local parts of the graph that may admit
large symmetric groups in the automorphism group. For this purpose we have to analyze the
structure of clique-partitions of the vertices.

4.2

Clique-Partitions

Definition 4.4. Let G be a graph and P be a partition of the vertices. We call P a cliquepartition if X is a clique for each X ∈ P.
In the following let G be a unit square graph with realization f : V (G) → R2 . We first define
the graph G∗M = (V (G) ∪ M(G), E(G∗M ), cG∗M ) with
E(G∗M ) = {vC | C ∈ M(G), v ∈ C} ∪ E(G)
and cG∗M = cGM as defined in the previous subsection. Let P be a clique-partition of the vertices,
which is refined by the color refinement algorithm applied to the graph G∗M . More precisely let
P ∗ be the coarsest partition of V (G) ∪ M(G) that is stable with respect to G∗M and refines the
partition P ∪ {M(G)}. The partition P is called clique-stable if P ∗ ∩ 2V (G) = P. In following
we analyze the structure of P ∗ with respect to the realization f . For this purpose let ≃ be the
equivalence relation on V (G) ∪ M(G) that corresponds to P ∗ .
Lemma 4.5. Let C, D be distinct maximal cliques with C ≃ D. Then zf (C)i ∩ zf (D)i = ∅ for
i ∈ [2].
Proof. Without loss of generality assume zf (C)1 ∩ zf (D)1 6= ∅. Let pC ∈ zf (C) and pD ∈ zf (D)
D
C
D
such that pC
1 = p1 . Again without loss of generality assume p2 < p2 . Let v = argminv∈C f (v)2
1
1
C
D
and w ∈ D \ C. Then kp − f (w)k∞ > 2 and kp − f (w)k∞ ≤ 2 . Suppose vw ∈ E(G). Then
1
1
0 < f (w)2 − f (v)2 ≤ 1. Let p = (pC
1 , f (v)2 + 2 ). Then kp − f (w)k∞ ≤ 2 , since p − f (w) =
1
D
(p1 − f (w)1 , f (v)2 − f (w)2 + 2 ). Further p ∈ zf (C) by Lemma 3.9. Thus, C ∪ {w} forms a clique
contradicting the maximality of C. So there is no edge between v and any w ∈ D \ C. But then
v 6≃ w, because ≃ describes a clique-partition, and thus C 6≃ D.
11

w

v

Figure 4.2: Each equivalence class of maximal cliques is diagonally ordered
The last lemma gives us the possibility to order equivalent cliques with respect to some
realization f . Each zf (C)i forms an interval according to Lemma 3.9. So let C ≃ D be two
D
maximal cliques and define zf (C)i ≤ zf (D)i if for some (and thus for all) pC
i ∈ zf (C)i , pi ∈
C
D
zf (C)i it holds pi ≤ pi . For each equivalence class of maximal cliques this defines two linear
orders on the maximal cliques. A central observation is that the two linear orders either coincide
or one is the reverse order of the other.
Lemma 4.6. For each C ∈ M(G)/≃ there is some b ∈ {−1, 1}, such that for every C, D ∈ C:
zf (C)1 ≤ zf (D)1 ⇔ b · zf (C)2 ≤ b · zf (D)2 .

(4.1)

The value b is called the orientation of C with respect to f .
Proof. Suppose not and let C ∈ M(G)/≃ be an equivalence class violating the condition. Let <
be the linear order on C induced by ordering the intervals zf (C)1 for C ∈ C in the natural way
from left to right. Let C1 < C2 < · · · < Cm be the elements of C and define b ∈ {−1, 1}, such
that
b · zf (C1 )2 ≤ b · zf (C2 )2 .
Without loss of generality assume b = 1. Let i ∈ [m] be minimal so that zf (Ci+1 )2  zf (Ci+2 )2 .
Consider the case where zf (Ci )2 ≥ zf (Ci+2 )2 (cf. Figure 4.2). The other case is zf (Ci )2 ≤
zf (Ci+2 )2 ≤ zf (Ci+1 )2 and is analogous by a rotation of 90 degree.
/ Ci+1 there is some w ∈ Ci+1 \ Ci with
Let v = argminv∈Ci f (v)1 . Since Ci ≃ Ci+1 and v ∈
v ≃ w. In particular vw ∈ E(G). Using the same argument there is some u ∈ Ci+2 \ Ci with
u ≃ v and thus, uv, uw ∈ E(G). Additionally considering the positions of the maximal cliques
we get f (v)1 ≤ f (u)1 ≤ f (v)1 + 1.
Claim 1: There is some p ∈ zf (Ci ), such that |p1 − f (u)1 | ≤ 12 .
Choose p = (f (v)1 + 21 , minv′ ∈Ci f (v ′ )2 + 21 ). Then p ∈ zf (Ci ) by Lemma 3.9. Further |p1 −
f (u)1 | = |f (v)1 − f (u)1 + 12 | ≤ 21 .
Claim 2: For every p ∈ zf (Ci ) it holds that |p2 − f (u)2 | ≤ 12 .
Let p ∈ zf (Ci ). Then p2 + 12 ≥ f (u)2 . First show p2 + 21 ≤ f (w)2 . Let p′ = (f (v)1 +
1
1
1
′
′
′
/ Ci
2 , minv ∈Ci f (v )2 + 2 . It is f (v)1 ≤ f (w)1 ≤ f (v)1 + 1 and thus, |p1 − f (w)| ≤ 2 . Since w ∈
1
′
we get |p2 − f (w)| > 2 and the considering positions of the maximal cliques even f (w)2 − p′2 > 21 .
Hence p2 + 21 ≥ f (u)2 by Lemma 3.9. As a consequence we also get f (w)2 ≥ f (u)2 ≥ f (w)2 − 1.
12

w′

v′

w

v

Figure 4.3: Extending the orientation on equivalence classes of cliques to equivalent vertices
So all together − 21 ≤ f (u)2 − 21 −f (u)2 ≤ p2 −f (u)2 ≤ p2 −f (w)2 +1 ≤ f (w)2 − 21 −f (w)2 +1 = 21 .
So there is some p ∈ zf (Ci ) with kp − f (u)k∞ ≤
visualization is also given in Figure 4.2.

1
2.

But this is a contradiction to u ∈
/ Ci . A

Corollary 4.7. Let C ∈ M(G)/≃ and for C, D ∈ C define C <f,C D if zf (C)1 ≤ zf (D)1 . Then
M(v) ∩ C forms an interval with respect to <f,C for each v ∈ V (G).
Proof. Let v ∈ V (G), such that there are distinct C, D ∈ M(v) ∩ C. Without loss of generality
let C <f,C D. Let E ∈ C with C <f,C E <f,C D. Pick points pA ∈ zf (A) for A ∈ {C, D, E}.
1
E
D
E
E
C
Then pC
1 < p1 < p1 . If f (v)1 ≥ p1 then |f (v)1 − p1 | < |f (v)1 − p1 | ≤ 2 . Otherwise
1
E
D
|f (v)1 − p1 | < |f (v)1 − p1 | ≤ 2 .
Now let b ∈ {−1, 1} be the orientation of C. Consider b = 1. The other case is analogous.
1
E
D
E
Then pC
2 < p2 < p2 and using the same argument as before |f (v)2 − p2 | ≤ 2 . So v ∈ E and
thus, M(v) ∩ C forms an interval with respect to <f,C .
Lemma 4.8. Let C ≃ D be two maximal cliques with zf (C)i ≤ zf (D)i for i ∈ [2]. Further let
v ∈ C \ D and w ∈ D \ C with v ≃ w. Then f (v)i < f (w)i for i ∈ [2].
1
Proof. Let pD ∈ zf (D). Further choose i ∈ [2] in such a way that |f (v)i − pD
i | > 2 . Without
1
D
loss of generality assume i = 1. Then f (w)1 > f (v)1 because f (v)1 < p1 − 2 . Let v ′ =
argminv∈C f (v)1 and pC = (f (v ′ ) + 21 , minv∈C f (v)2 + 12 ). Then pC ∈ zf (C) by Lemma 3.9 and
D
′
pC
/ D. Let w′ ∈ D \ C with v ′ ≃ w′ . Then f (v ′ )1 < f (w′ )1 ≤ f (v ′ )1 + 1
1 < p1 which implies v ∈
1
′
′
′ ′
C
′
and thus, |p1 − f (w )1 | ≤ 12 . Hence, f (w′ ) > pC
2 + 2 . Let u ≃ v . Then u v ∈ E(G) and
1
1
′
C
′ ′
′
C
u w ∈ E(G). So f (u )1 ≤ p1 + 2 and f (u )2 ≥ p2 − 2 . Now suppose towards a contradiction
1
C
D
that f (w)2 ≤ f (v)2 . Then |f (w)2 − pC
2 | ≤ 2 because p2 < p2 .

Claim: If wu′ ∈ E(G) then vu′ ∈ E(G).
1
Let wu′ ∈ E(G). If f (u′ )1 ≥ f (v)1 then 0 ≤ f (u′ )1 − f (v)1 ≤ pC
1 + 2 − f (v)1 ≤ 1. Otherwise
′
′
′
f (u )1 < f (v)1 and 0 < f (v)1 − f (u )1 < f (w)1 − f (u )1 ≤ 1. So |f (v)1 − f (u′ )1 | ≤ 1. Similarly
|f (v)2 − f (u′ )2 | ≤ 1 and thus, vu′ ∈ E(G).
1
But wv ′ ∈
/ E(G) because f (w)1 − f (v ′ ) > 1. Otherwise f (w) − pC
1 ≤ 2 and w ∈ C. This is a
contradiction to ≃ being a stable partition. A visualization is also given in Figure 4.3.

13

Corollary 4.9. Let v, w ∈ V (G) with v ≃ w and C ∈ M(G)/≃ , such that M(v)∩C =
6 M(w)∩C.
Further let b ∈ {−1, 1} be the orientation C. Then f (v)i 6= f (w)i for i ∈ [2] and
f (v)1 < f (w)1 ⇔ b · f (v)2 < b · f (w)2 .

(4.2)

Proof. Without loss of generality assume b = 1. Let C(u) = M(u) ∩ C for u ∈ V (G). Since
|C(v)| = |C(w)| there are C ∈ C(v) \ C(w) and D ∈ C(w) \ C(v). Then the statement follows from
Lemma 4.8.
Corollary 4.10. Let C, D ∈ M(G)/≃ . Further let C, C ′ ∈ C with C <f,C C ′ and D, D′ ∈ D, such
that there are vertices v, w ∈ V (G) with v ≃ w and v ∈ (C \C ′ )∩(D \D′ ), w ∈ (C ′ \C)∩(D′ \D).
Then D <f,D D′ .
Proof. Let bC , bD ∈ {−1, 1} be the orientations of C and D respectively. Without loss of generality
assume bC = 1. Then bD = 1 by Corollary 4.9. So D <f,D D′ by Lemma 4.8.
We are now ready to prove the main structural lemma on clique-stable partitions.
Lemma 4.11. Let G be a twin-free unit square graph and let P be a clique-stable partition.
Further let f : V (G) → R2 be a realization. Then the following properties hold:
1. For each X ∈ P there exists b ∈ {−1, 1}, such that
f (v)1 ≤ f (w)1 ⇔ b · f (v)2 ≤ b · f (w)2

(4.3)

for all v, w ∈ X. The value b is called the orientation of X, which is denoted by oriG,f (X)
(the value b is unique unless |X| = 1, in this case we define oriG,f (X) = 1).
2. Let X, Y ∈ P with oriG,f (X) 6= oriG,f (Y ). Then either xy ∈ E(G) for all x ∈ X, y ∈ Y or
there is no x ∈ X, y ∈ Y with xy ∈ E(G).
3. Let X, Y ∈ P with oriG,f (X) = oriG,f (Y ) and suppose k = |{xy ∈ X × Y | xy ∈ E(G)}| ≥
1. Further let X = {x1 , . . . , xs }, such that f (xi )1 ≤ f (xi+1 )1 for all i ∈ [s], and Y =
{y1 , . . . , yt }, such that f (yj )1 ≤ f (yj+1 )1 for all j ∈ [t]. Then
 


j·s
i·t
=
.
(4.4)
xi yj ∈ E(G) ⇔
k
k
Proof. Let X ∈ P and let X = {v1 , . . . , vk } with f (vi )1 ≤ f (vj )1 for all i ≤ j ∈ [k]. Without
loss of generality assume f (v1 )2 ≤ f (v2 )2 . In this case b = 1. Suppose towards a contradiction
that there is some i ∈ [k] with f (vi+1 )2 > f (vi+2 )2 . Choose i ∈ [k] minimal with this property.
Without loss of generality assume that f (vi )2 ≤ f (vi+2 )2 . The other case is analogous. Let P ∗
be a stable partition of the graph G∗M , such that P ∗ ∩ 2V (G) = P. Let C ∈ PN ∩ 2M(G) , such
that M(vi+1 ) ∩ C =
6 M(vi+2 ) ∩ C. Since |M(vi+1 ) ∩ C| = |M(vi+2 ) ∩ C| there are C, C ′ ∈ C with
vi+1 ∈ C \ C ′ and vi+2 ∈ C ′ \ C. Let b be the orientation of C. Then b = −1 by Corollary 4.9.
Furthermore M(vi ) ∩ C = M(vi+1 ) ∩ C and M(vi ) ∩ C = M(vi+2 ) ∩ C by Corollary 4.9. But this
is a contradiction.
So let X, Y ∈ P with oriG,f (X) 6= oriG,f (Y ). Suppose there is some edge between X and
Y . Without loss of generality assume oriG,f (X) = 1. Consider x = argmaxx∈X f (x)1 and
y = argmaxy∈Y f (y)1 .
Case 1: f (x)1 ≤ f (y)1 and f (x)2 ≤ f (y)2 .
Let y ′ ∈ Y . First, there is some x′ ∈ X with x′ y ∈ E(G), because the partition P is stable.
14

Then f (y)1 − 1 ≤ f (x′ )1 ≤ f (x)1 ≤ f (y)1 . Additionally f (y)1 − 1 ≤ f (y ′ )1 ≤ f (y)1 . Hence,
|f (x)1 − f (y ′ )1 | ≤ 1. Furthermore, by stability, there is some x′′ ∈ X with x′′ y ′ ∈ E(G). Then
f (y ′ )2 − 1 ≤ f (x′′ )2 ≤ f (x)2 ≤ f (y)2 ≤ f (y ′ )2 and thus, |f (x)2 − f (y ′ )2 | ≤ 1. So xy ′ ∈ E(G) for
all y ′ ∈ Y . By stability it follows that x′ y ′ ∈ E(G) for all x′ ∈ X, y ′ ∈ Y .
Case 2: f (x)1 ≥ f (y)1 and f (x)2 ≤ f (y)2 .
The proof is analogous to the first case by switching the roles of X and Y .
Case 3: f (x)1 ≤ f (y)1 and f (x)2 ≥ f (y)2 .
Let y ∗ = argminy∈Y f (y)1 and first suppose f (x)2 ≥ f (y ∗ )2 . Let x′ ∈ X. Then, by stability,
there is some y ′ ∈ Y with x′ y ′ ∈ E(G). If f (x′ )1 ≤ f (y ′ )1 then f (y ′ )1 − 1 ≤ f (x′ )1 ≤ f (y ′ )1 and
f (y ′ )1 − 1 ≤ f (y ∗ )1 ≤ f (y ′ )1 . Otherwise f (y ∗ )1 ≤ f (y ′ )1 ≤ f (x′ )1 ≤ f (x)1 ≤ f (y)1 ≤ f (y ∗ )1 + 1.
So in both cases it holds that |f (x′ )1 − f (y ∗ )1 | ≤ 1. Furthermore there is some y ′′ with xy ′′ ∈
E(G). So f (x)2 ≥ f (y ∗ )2 ≥ f (y ′′ )2 ≥ f (x)2 + 1. Additionally f (x)2 ≥ f (x′ )2 ≥ f (x)2 + 1 and
thus, |f (x′ )2 − f (y ∗ )2 | ≤ 1. So y ∗ x′ ∈ E(G) for all x′ ∈ X. By stability it follows again that
x′ y ′ ∈ E(G) for all x′ ∈ X, y ′ ∈ Y .
So consider f (x)2 ≤ f (y ∗ )2 . Then f (y)2 + 1 ≥ f (y ∗ )2 ≥ f (x)2 ≥ f (y)2 . Let y ′ ∈ Y .
Then f (y)2 + 1 ≥ f (y ′ )2 ≥ f (y)2 and consequently, |f (x)2 − f (y ′ )2 | ≤ 1. Furthermore, there
is some x′ ∈ X with x′ y ∈ E(G). Then f (y)1 − 1 ≤ f (x′ )1 ≤ f (x)1 ≤ f (y)1 . Additionally
f (y)1 − 1 ≤ f (y ′ )1 ≤ f (y)1 . Hence, |f (x)1 − f (y ′ )1 | ≤ 1. So xy ′ ∈ E(G) for all y ′ ∈ Y . By
stability it follows once more that x′ y ′ ∈ E(G) for all x′ ∈ X, y ′ ∈ Y .
Case 4: f (x)1 ≥ f (y)1 and f (x)2 ≥ f (y)2 .
The proof is analogous to the third case by switching the roles of X and Y .
It remains to prove the third statement. Let X, Y ∈ P with oriG,f (X) = oriG,f (Y ). Without
loss of generality assume that oriG,f (X) = 1. First, |N (x) ∩ Y | = ks and |N (y) ∩ X| = kt for each
x ∈ X, y ∈ Y , because P is clique-stable. For a vertex x ∈ X let Ix = {j ∈ [t] | xyj ∈ E(G)}.
Claim 1: For each x ∈ X the set Ix is an interval.
Let j1 < j2 < j3 ∈ [t] with j1 , j3 ∈ Ix . If f (yj2 )1 ≤ f (x)1 then f (yj1 )1 ≤ f (yj2 )1 ≤ f (x)1 ≤
f (yj1 )1 +1. Otherwise f (yj3 )1 −1 ≤ f (x)1 ≤ f (yj2 )1 ≤ f (yj3 )1 . In both cases |f (x)−f (yj2 )1 | ≤ 1.
The same argument also works for the second dimension by Lemma 4.11. So j2 ∈ Ix .
For y ∈ Y the set Iy is defined analogously, so Iy = {i ∈ [s] | xi y ∈ E(G)}. Clearly the previous
claim also holds for all y ∈ Y .
Claim 2: Let i < i′ ∈ [s] and j < j ′ ∈ [t], such that there are edges xi yj ′ , xi′ yj ∈ E(G). Then
xi yj , xi′ yj ′ ∈ E(G).
Let r ∈ [2]. If f (xi )r ≤ f (yj )r then f (yj ′ )r − 1 ≤ f (xi )r ≤ f (yj )r ≤ f (yj ′ )r . Otherwise
f (xi′ )r −1 ≤ f (yj )r ≤ f (xi )r ≤ f (xi′ )r . In both cases |f (xi )r −f (yj )r | ≤ 1. Hence, xi yj ∈ E(G).
Analogously it holds that xi′ yj ′ ∈ E(G).
j·s
i·t
k
k
r
r
r
r
For r ∈ [ s·t
k ] let X = {xi | ⌈ k ⌉ = r} and Y = {yj | ⌈ k ⌉ = r}. Then |X | = t and |Y | = s .
s·t
r
r
It suffices to show that for all r ∈ [ k ] it holds that xy ∈ E(G) for all x ∈ X , y ∈ Y . Let
′
r
r ∈ [ s·t
k ] and suppose the statement holds for all r < r. Let i ∈ [s] be minimal with xi ∈ X
r
′
′
and let j ∈ [t] be minimal with yj ∈ Y . We first show that xi yj ∈ E(G) Let i ∈ [s], j ∈ [t] be
such that yj xi′ ∈ E(G) and xi yj ′ ∈ E(G). But then i ≤ i′ since for every i′′ < i the vertex xi′′

15

already has the correct number of neighbors. Analogously it holds that j ≤ j ′ . So xi yj ∈ E(G)
by Claim 2.
Now let P be a canonical, clique-stable partition of the graph G. We define the vertex and
edge-colored graph G[P] = (P, E, cV , cE ) with E = {XY | X 6= Y ∈ P},
cV : P → N : X 7→ |X|
and
cE : E → N : XY 7→ |{xy ∈ X × Y | xy ∈ E(G)}|.
For γ ∈ Aut(G) define the permutation γ P := ϕ(γ) ∈ Sym(P) where ϕ : Aut(G) → Sym(P) is
the natural action of Aut(G) on P. Note that ϕ is well-defined since the partition P is canonical.
Theorem 4.12. Let G be a twin-free unit square graph and let P be a canonical, clique-stable
partition. Further let δ ∈ Aut(G[P]). Then there is some γ ∈ Aut(G) with γ P = δ.
Proof. Let f : V (G) → R2 be a realization of G. For X ∈ P let X = {vX,1 , . . . , vX,|X| }, such
that f (vX,i )1 ≤ f (vX,j )1 for all i ≤ j ∈ [|X|]. Define
γ : V (G) → V (G) : vX,i 7→ vX δ ,i .
First observe that γ is well-defined since P forms a partition and |X| = |X δ | for all X ∈ P.
Furthermore γ is bijective because δ is bijective. Thus, γ ∈ Sym(V (G)) and clearly γ P = δ. So
it remains to prove that γ preserves the edge relation.
Let vw ∈ E(G) and let X, Y ∈ P, such that v ∈ X and w ∈ Y . If X = Y then v γ , wγ ∈ X δ
and thus, v γ wγ ∈ E(G) because X is a clique. So suppose X 6= Y . First consider the case
that oriG,f (X) 6= oriG,f (Y ). Then cE (XY ) = |X| · |Y | by Lemma 4.11. Hence, cE (X δ Y δ ) =
|X| · |Y | = |X δ | · |Y δ | and xy ∈ E(G) for every x ∈ X δ , y ∈ Y δ . In particular v γ wγ ∈ E(G).
So suppose oriG,f (X) = oriG,f (Y ). Without loss of generality assume that oriG,f (X) = 1.
Let k = cE (XY ), s = |X| and t = |Y |. Then k ≥ 1 and suppose k < |X| · |Y | (otherwise
the statement follows with same argument as before). Further let xi = vX,i for i ∈ [s] and
yj = vY,j for j ∈ [t]. Now pick i ∈ [s], j ∈ [t], such that v = xi = vX,i and w = yj = vY,j . Then
⌈ i·skY ⌉ = ⌈ j·skX ⌉ by Lemma 4.11. Further s = |X δ |, t = |Y δ | and k = cE (X δ Y δ ) < |X δ | · |Y δ |.
Hence, oriG,f (X δ ) = oriG,f (Y δ ) by Lemma 4.11. So v γ wγ = vX δ ,i vY δ ,j ∈ E(G) again by Lemma
4.11.
Intuitively, the last theorem states that each automorphism of G[P] naturally extends to an
automorphism of G. In particular, the graph G can be uniquely reconstructed from the graph
G[P]. This is the main result on the local structure of unit square graphs which allows us, for
a canonical, clique-stable partition P, to restrict to the graph G[P]. For the remainder of this
work the goal is to compute a canonical, clique-stable partition P, such that the automorphism
group of G[P] is a Γt -group for some constant t. To achieve this goal we require the graph
G to have some singleton vertex v0 (a vertex with a unique color). More precisely, for such a
graph we construct the desired partition P and a canonical, t-circle-bounded graph H, such that
P ⊆ V (H) and P is invariant under Aut(H). This results in a good supergroup of the group
Aut(G[P]) which can be used by Luks’ algorithm to compute the real automorphism group. To
compute the graph H we devise an algorithm that iteratively extends H taking vertices with
larger and larger distances to v0 into account. While doing so the crucial subproblem is to
compute canonical clique-partitions for neighborhoods of cliques. This problem is addressed in
the next section.

16

5

Neighborhoods

In order to obtain canonical clique-partitions for neighborhoods we essentially proceed in two
steps. First, we use some combinatorial partitioning techniques to obtain some initial coloring of
the vertices. Then, considering each color class separately, the main contribution is to prove that
each color class can either be described by a co-bipartite graph or a proper circular arc graph.
In both cases it is easy to compute a canonical clique-partition.

5.1

Two structure Lemmas

We first require two general graph-theoretic lemmas.
Lemma 5.1. Let G be a graph, such that
1. G[N [v]] is a unit interval graph for each v ∈ V (G),
2. G has no induced subgraph isomorphic to C4 ∪ K1 .
Further let X = {w1 ∈ V (G) | ∃w2 , . . . , w6 : G[w1 , . . . , w6 ] ∼
= C6 }. Then G[X] is co-bipartite.
Proof. Suppose X 6= ∅ and let W = {wi,j | i ∈ [2], j ∈ [3]} ⊆ X, such that G[W ] ∼
= C6 as depicted
in Figure 2.1d. If X = W then G[X] ∼
= C6 which is co-bipartite. So assume W ( X and let
v ∈ X \ W . Then there are i1 , i2 ∈ [2] and j1 , j2 ∈ [3] with j1 6= j2 , such that vwis ,js ∈ E(G) for
s ∈ [2], because of property 2.
Claim: There is some i ∈ [2], such that vwi,j ∈ E(G) for all j ∈ [3].
Suppose this does not hold and consider some vertex wi,j with vwi,j ∈ E(G). Then there is
/ E(G). So vw3−i,j ∈ E(G), because otherwise the graph
some j ′ ∈ [3], such that vwi,j ′ ∈
G[v, wi,j , wi,j ′ , w3−i,j ] would be isomorphic to a claw contradicting property 1. Hence, vwi,j ∈
E(G) if and only if vw3−i,j ∈ E(G) for each j ∈ [3]. But then G[N [v]] contains a cycle of length
4, since there are two distinct j1 , j2 ∈ [3] with vwi,j1 , vwi,j2 ∈ E(G). This is a contradiction to
property 1.
Now let v ′ ∈ X \ W be another vertex, such that v ′ wi,j ∈ E(G) for all j ∈ [3]. Suppose that
vv ′ ∈
/ E(G) and let j ∈ [3]. Then uw3−i,j ∈ E(G) for some u ∈ {v, v ′ }, since otherwise the graph
G[wi,j , v, v ′ , w3−i,j ] would be isomorphic to a claw. So for some u ∈ {v, v ′ } there are distinct
j1 , j2 ∈ [3] with uw3−i,j1 , uw3−i,j2 ∈ E(G). But this again contradicts the fact, that G[N [u]]
does not contain a cycle of length 4.
Now let X1 = {v ∈ X | ∀j ∈ [3] : vw1,j ∈ E(G)} and X2 = X \ X1 . Then X1 is a clique by
the comment below the Claim. For every v ∈ X2 it holds that vw2,j ∈ E(G) for all j ∈ [3] by
the Claim. So X2 is also a clique using again the comment below the Claim.
Lemma 5.2. Let G be a graph, such that
1. G[N [v]] is a unit interval graph for each v ∈ V (G),
2. G has no induced subgraph isomorphic to Cn+4 ∪ K1 for n ≥ 0,
3. there are no v, w ∈ V (G), such that N [v] ( N [w].
Then G has no induced subgraph isomorphic to net.

17

Proof. Assume towards a contradiction that G has an induced subgraph isomorphic to net.
So there are vertices v1 , v2 , v3 , w1 , w2 , w3 ∈ V (G), such that G[v1 , v2 , v3 , w1 , w2 , w3 ] ∼
= net as
depicted in Figure 2.1e. Further let m ∈ N be the maximal number, such that there is an
induced path u1 , . . . , um with u1 = w3 and ui wj , ui vl ∈
/ E(G) for all i ∈ [m], j ∈ [2], l ∈ [3].
Consider some um+1 ∈ V (G), such that um+1 um ∈ E(G) and um+1 um−1 ∈
/ E(G) (if m = 1 then
u0 = v3 ). Note that such a vertex always exists by property 3. Since m was chose to be maximal
there is some vertex v ∈ X := {v1 , v2 , v3 , w1 , w2 , w3 , u1 , . . . , um−1 } with um+1 v ∈ E(G). This
gives a cycle C ⊆ X ∪ {um , um+1 } of length l ≥ 4 and some i ∈ [2], such that uwi ∈
/ E(G) for
all u ∈ C \ {um+1 }. By 2 there is an edge um+1 wi ∈ E(G). But then the induced subgraph
G[um+1 , um , v, wi ] builds a claw contradicting 1.

5.2

Neighborhood graphs

Before considering neighborhoods of cliques we first restrict to neighborhoods of vertices. This
occurs as a subcase when analyzing neighborhood of cliques. Also the structure of neighborhoods
tends to be simpler than for neighborhoods of cliques.
Definition 5.3. A unit square graph is a neighborhood graph if there is a realization f : V (G) →
[−1, 1]2 .
Note that every graph induced on a neighborhood of a vertex is indeed a neighborhood graph
and every neighborhood graph can be turned into the neighborhood of a vertex by adding a
universal vertex located at the origin. In this subsection let G be a neighborhood unit square
graph with realization f : V (G) → [−1, 1]2 . The goal is to prove that, after performing the
k-dimensional Weisfeiler-Leman algorithm for sufficiently large k, each color class of vertices is
co-bipartite or proper circular arc. Building on the characterization of proper circular arc graphs
in terms forbidden induced subgraphs, we have to consider Cn+4 ∪ K1 and S3 ∪ K1 .
Lemma 5.4. Let X = {v ∈ V (G) | ∃ℓ ≥ 4 ∃w1 , . . . , wℓ : vwi ∈
/ E(G) ∧ G[w1 , . . . , wℓ ] ∼
= Cℓ }.
Then X 6= V (G).
Proof. Let v = argminv∈V (G) |f (v)1 |. Suppose towards a contradiction that v ∈ X. Then there
is some ℓ ≥ 4 and w1 , . . . , wℓ ∈ V (G), such that vwi ∈
/ E(G) for all i ∈ [ℓ] and wi wj ∈ E(G)
if and only if i − j ≡ ±1 mod ℓ for all i, j ∈ [ℓ]. Without loss of generality assume that
f (v) ∈ [−1, 0] × [−1, 0]. Let i = argmini∈[ℓ] f (wi )2 . Since G[w1 , . . . , wℓ ] is not a unit interval
graph it holds that f (wi ) ∈ [0, 1] × [−1, 0], by Remark 3.3. Without loss of generality assume
i = 2. Now consider the two neighbors w1 and w3 . Note that w1 w3 ∈
/ E(G) since ℓ ≥ 4. Then
there is some j ∈ {1, 3}, such that f (wj ) ∈ [−1, 0) × [0, 1]. So in particular f (wj )1 < 0. Further
f (wj )1 + 1 ≥ f (w2 )1 and f (v)1 + 1 < f (w2 )1 . Altogether this means that f (v)1 < f (wj )1 < 0
contradicting the definition of v.
Lemma 5.5. Let X = {v ∈ V (G) | ∃w1 , . . . , w6 : vwi ∈
/ E(G) ∧ G[w1 , . . . , w6 ] ∼
= S3 }. Then
X 6= V (G).
Proof. Let v = argminv∈V (G) |f (v)1 |. Suppose towards a contradiction that v ∈ X. Then there
are vertices w1 , . . . , w6 ∈ V (G), such that vwi ∈
/ E(G) for all i ∈ [k] and G[w1 , . . . , w6 ] ∼
= S3
as depicted in Figure 2.1a. Without loss of generality assume that f (v) ∈ [−1, 0] × [−1, 0]. Let
i = argmini∈[k] f (wi )2 . Since G[w1 , . . . , w6 ] is not a unit interval graph it holds that f (wi ) ∈
[0, 1] × [−1, 0], by Remark 3.3.
First suppose that i ∈ {4, 5, 6}. Then there are j1 , j2 ∈ {1, 2, 3} with j1 6= j2 , wi wj1 , wi wj2 ∈
/ E(G). Further f (wjs ) ∈ [−1, 0] × [0, 1] for some s ∈ [2]. But then f (v)1 <
E(G) and wj1 wj2 ∈
f (wjs )1 < 0 contradicting the definition of v.
18

So consider i ∈ {1, 2, 3}. Without loss of generality assume i = 1. Using the same argument
as before f (w4 ), f (w6 ) ∈ [0, 1] × [−1, 1]. Assume f (w6 )1 ≤ f (w4 )1 . First suppose that f (w6 ) ∈
[0, 1] × [0, 1]. It holds that f (w2 ) ∈ [−1, 1] × [0, 1] and f (w2 )1 + 1 ≥ f (w4 )1 . But then kf (w2 ) −
f (w6 )k∞ ≤ 1 contradicting w2 w6 ∈
/ E(G). So f (w6 ) ∈ [0, 1] × [−1, 0]. Using again the same
argument as before f (w3 ), f (w5 ) ∈ [0, 1] × [−1, 1]. More precisely f (w3 ), f (w5 ) ∈ [0, 1] × [0, 1]
since there is no edge to w1 . Since w3 w4 ∈
/ E(G) it holds that f (w4 ) ∈ [0, 1] × [−1, 0]. So
f (w2 ) ∈ [0, 1] × [−1, 1]. But this is now a contradiction to Remark 3.3 since S3 is not a unit
interval graph.
In order to prove the main partitioning result for neighborhood graphs we also require, that
for sufficiently large k the k-dimensional Weisfeiler-Leman algorithm identifies all interval graphs
(cf. [Lau10]).
Corollary 5.6. There is some k ∈ N, such that for each neighborhood unit square graph
the following holds: After performing k-dimensional Weisfeiler-Leman each equivalence class of
vertices induces a graph which is co-bipartite or proper circular arc with at most four connected
components.
Proof. Choose k sufficiently large and let X ⊆ V (G) be an equivalence class. Then G[X] is a
neighborhood unit square graph. By Lemma 3.4 there is some v ∈ X, such that NG[X] [v] induces
a unit interval graph. Since k-dimensional Weisfeiler-Leman identifies all interval graphs this
is true for all v ∈ X. From Lemma 5.4 it follows that there exists a vertex v ∈ X, such that
every induced cycle contains at least one vertex being a neighbor of v. Again by stability of the
set X with respect to k-dimensional Weisfeiler-Leman this is true for all v ∈ X (note that the
maximal length of an induced cycle is at most 8). So there is no induced subgraph isomorphic to
Cn+4 ∪K1 . Combining the same argument with Lemma 5.5 we get that G[X] also has no induced
subgraph isomorphic to S3 ∪ K1 . Since G[X] is regular there are no vertices v, w ∈ X, such that
NG[X] [v] ( NG[X] [w]. So we can apply Lemma 5.2 and obtain that there is no induced subgraph
isomorphic to net. Furthermore G[X] has no induced subgraph isomorphic to T2 by Corollary
3.6. Now suppose there is an induced subgraph isomorphic to C6 . Then, by stability, every vertex
is part of an induced subgraph C6 and thus, G[X] is co-bipartite by Lemma 5.1. Otherwise G[X]
is proper circular arc by Proposition 2.8. The bound on the number of components follows from
the fact that K1,5 is not a unit square graph (cf. Lemma 3.2).
Theorem 5.7. Let G be a neighborhood unit square graph. Then one can compute in polynomial
time a canonical clique-partition P and a canonical colored graph H, such that
1. P = V (H),
2. H is 4-circle-bounded,
3. im(ϕ) ≤ Aut(H) where ϕ : Aut(G) → Sym(P) is the natural action of Aut(G) on P.
Proof. Choose k according to Corollary 5.6 and let X ⊆ V (G) be an equivalence class after
performing k-dimensional Weisfeiler-Leman. Further let c be the color of the equivalence class.
First suppose G[X] is co-bipartite. Let t be the number of non-trivial connected components of
G[X]. Then t ≤ 2 by Corollary 3.6. Let Yj,1 , Yj,2 be the unique bipartition of the j-th connected
component, j ∈ [t]. Further let Y be the set of isolated vertices in G[X] and Y = {Y } if Y 6= ∅ and
Y = ∅ otherwise. Define PX = {Yj,j ′ | j ∈ [t], j ′ ∈ [2]} ∪ Y. Further
 let HX = {PX , E(HX ), cX }
with Y Z ∈ E(HX ) if there are v ∈ Y, w ∈ Z with vw ∈ E G[X] and cX (Y ) = c.
Otherwise G[X] is proper circular arc according to Corollary 5.6. Let X1 , . . . , Xt be the
connected components of G[X]. Then t ≤ 4 by Corollary 5.6. Let i ∈ [t] and let PX,i be the
19

P(0,1)

Y(1,0)

X

P(1,0)

Y(−1,0)

P(−1,0)

Y(0,1)

Y(0,−1)
P(0,−1)

Figure 5.1: Simple clique neighborhood graph with respect to X
partition containing the equivalence classes of the connected twin relation for G[Xi ]. Further
let HX,i
S by Proposition 2.10 where each vertex is colored by c. Define
S be the graph computed
PX = i∈[t] PX,i and HX = i∈[t] HX,i .
S
S
Finally let P = X PX and H = X HX . It can easily be checked that P and H have the
desired properties.

5.3

Clique neighborhoods graphs

Remember, that our goal is to compute a canonical clique-partition of a given unit square graph
with singleton vertex v0 . We first group the vertices according to their distance to v0 . Then, for
the first level of vertices which are all the neighbors of v0 , we use the previous theorem to compute
a canonical clique-partition. For all other levels we want to build up on the partition computed
in the previous level. More precisely, for a given clique in the partition of the previous level we
want to partition its neighbors in the current level. Hence, we need to consider neighborhoods
of cliques.
Let GSbe a colored unit square graph and let X ⊆ V (G) be a clique, such that V (G) =
N [X] = v∈X N [v]. Further suppose there is some color i, such that X = Vi (G), and there is
some k ∈ [|X|], such that |N [v] ∩ X| = k for all v ∈ V (G) \ X. In this case G is called a simple
clique neighborhood graph with respect to X. In this subsection we aim to analyze the structure of
G[V \ X] and to obtain results similar to Theorem 5.7. The most simple case occurs if k = |X|.
Then G is a neighborhood unit square graph and thus, it can be handled by Theorem 5.7.
Suppose k < |X|. Let f : V (G) → R2 be a realization for G. Without loss of generality assume
that f (x) ∈ [− 21 , 21 ]2 for all x ∈ X. Then f (v) ∈ [− 23 , 32 ]2 \ [− 21 , 12 ]2 for all v ∈ V (G) \ X. Let
Q = {(q1 , q2 ) ∈ {−1, 0, 1}2 | |q1 |+|q2 | = 1}. For q ∈ Q let Pq = [− 21 +q1 , 21 +q1 ]×[− 21 +q2 , 21 +q2 ].
Lemma 5.8. For q ∈ Q consider v, w ∈ V (G) with f (v), f (w) ∈ Pq . Then N [v] ∩ X = N [w] ∩ X.
Proof. Without loss of generality consider q = (0, −1) an further assume that f (v)2 ≤ f (w)2 . Let
x ∈ N [v] ∩ X. Then f (v)2 ≤ f (x)2 ≤ f (v)2 + 1. So |f (w)2 − f (x)2 | ≤ 1. Further f (w)1 , f (x)1 ∈
[− 12 , 12 ]. Hence, x ∈ N [w] ∩ X. So N [v] ∩ X ⊆ N [w] ∩ X and |N [v] ∩ X| = |N [w] ∩ X|, which
implies N [v] ∩ X = N [w] ∩ X.

20

For v, w ∈ V (G) \ X define v ∼snh w if N [v] ∩ X = N [w] ∩ X. Let Psnh be the corresponding
partition into equivalence classes. Further for q ∈ Q let Yq ∈ Psnh , such that f (v) ∈ Pq for some
v ∈ Yq . If there is no v ∈ V (G) with f (v) ∈ Pq then we let Yq = ∅.
Lemma 5.9. Let Z ∈ Psnh , such that G[Z] is not a disjoint union of cliques. Then there is some
q ∈ Q, such that Z = Yq .
Proof. Let Z ∈ Psnh , such that Z 6= Yq for all q ∈ Q. Then f (v) ∈
/ Pq for all q ∈ Q, v ∈ Z
by Lemma 5.8. In other words, for each v ∈ Z there is some q v ∈ {−1, 1}2 with f (v) ∈ Pq′v =
S
[− 12 + q1v , 21 + q1v ] × [− 21 + q2v , 21 + q2v ] \ ( q∈Q Pq ). This means vw ∈ E(G) if and only if q v = q w
for all v, w ∈ Z. Hence, G[Z] is a disjoint union of cliques.
∗
∗
Let Psnh
= {Z ∈ Psnh | G[Z] is a disjoint union of cliques}. Further let Pclique
= {Z ⊆
∗
V (G) \ X | ∃Z ′ ∈ Psnh
: Z is a connected component in G[Z ′ ]}. Define the graph Gclique =
∗
(Pclique
, E(Gclique )) with

E(Gclique ) = {Y Z | ∀v ∈ Y, w ∈ Z : vw ∈ E(G)}.
Further let V ∗ =

S

∗
X∈Pclique

X.

Lemma 5.10. If G[V ∗ ] is connected then Gclique is a proper circular arc graph with at most
eight connected components.
Proof.SSuppose G[V ∗ ] is connected.
For q ∈ {−1, 1} let Pq = [− 12 + q1 , 12 + q1 ] × [− 21 + q2 , 21 +
S
∗
q2 ] \ ( q∈Q Pq ). Let V = X∈P ∗ X. Let Vq = {v ∈ V ∗ | f (v) ∈ Pq }. Further let ∼clique be
clique
∗
the equivalence relation that corresponds to Pclique
.
Claim 1: Let t ∈ {−1, 1} and let p, q ∈ {−1, 0, 1}×{t}. Further let u ∈ Vq , w ∈ Vp with u ∼snh w.
Then u ∼snh v for all v ∈ V ∗ with f (v) ∈ [f (u)1 , f (w)1 ] × [ 32 t, 12 t].
Without loss of generality assume t = −1. It holds that N [u] ∩ X = N [w] ∩ X = N [u] ∩ N [w] ∩
X. First consider the case that |f (v)2 | ≤ max{|f (u)2 |, |f (w)2 |}. Let x ∈ N [u] ∩ X. Then
|f (u)1 − f (x)1 | ≤ 1 and |f (w)1 − f (x)1 | ≤ 1, so |f (v)1 − f (x)1 | ≤ 1. Further |f (v)2 − f (x)2 | =
|f (v)2 | − |f (x)2 | ≤ max{|f (u)2 |, |f (w)2 |} − |f (x)2 | = max{|f (u)2 − f (x)2 |, |f (w)2 − f (x)2 |} ≤
1. Hence, x ∈ N [v] ∩ X and N [u] ∩ X = N [v] ∩ X. So consider the other case, namely
|f (v)2 | ≥ max{|f (u)2 |, |f (w)2 |}. Let x ∈ N [v] ∩ X. Then |f (u′ )2 − f (x)2 | = |f (u′ )2 | − |f (x)2 | ≤
|f (v)2 | − |f (x)2 | = |f (v)2 − f (x)2 | ≤ 1 for u′ ∈ {u, w}. Further there exists u′ ∈ {u, w} with
|f (u′ )1 −f (x)1 | ≤ |f (v)1 −f (x)1 | ≤ 1 and thus, x ∈ N [u′ ]∩X. So N [v]∩X = N [u]∩X = N [w]∩X.
Clearly the same statement also holds if the value t would be in the first coordinate. Let
q ∈ {−1, 0, 1}2, q 6= (0, 0). For v, w ∈ Vq define v < w if f (v)1 < f (w)1 . It follows from Lemma
∗
5.9 and Claim 1 that for each Z ∈ Pclique
the set Z ∩ Vq consists of consecutive elements with
respect to <. For q ∈ {−1, 0, 1}, q 6= (0, 0), let
(
∗
{Z ∩ Vq | Z ∈ Pclique
, Z ∩ Vq 6= ∅} if Vq 6= ∅
Vq =
.
{∅}
otherwise
U
Let V = q∈{−1,0,1}2 ,q6=(0,0) Vq . Note that Vq ∈ V for all q ∈ Q by Lemma 5.8. So |Vq | = 1 for all
q ∈ Q. We now define a cycle H on V as follows. Let q ∈ {−1, 1}2 and let Vq = {Zq,1 , . . . , Zq,kq }

21

so that f (v)1 < f (w)1 for all v ∈ Zq,i , w ∈ Zq,j and i < j ∈ [kq ]. Observe that such an ordering
exists by Claim 1. Then let
E(H) = {Zq,i Zq,i+1 | q ∈ {−1, 1}2, i ∈ [kq − 1]}
∪ {V(−1,0) Z(−1,q2 ),1 | q2 ∈ {−1, 1}} ∪ {V(0,q2 ) Z(−1,q2 ),k(−1,q2 ) | q2 ∈ {−1, 1}}
∪ {V(0,q2 ) Z(1,q2 ),1 | q2 ∈ {−1, 1}} ∪ {V(1,0) Z(1,q2 ),k(1,q2 ) | q2 ∈ {−1, 1}}.

Claim 2: Let q ∈ {−1, 1}2, v, w ∈ Vq . If f (v)1 ≤ f (w)1 and q1 q2 f (v)2 ≤ q1 q2 f (w)2 , then
v ∼snh w.
Without loss of generality consider q = (−1, −1). Let v, w ∈ Vq with f (v)i ≤ f (w)i for i ∈ [2].
Let x ∈ N [v] ∩ X. Then f (v)i ≤ f (w)i ≤ f (x)i ≤ f (v)i + 1 and hence, |f (w)i − f (x)i | ≤ 1 for
i ∈ [2]. So x ∈ N [w] ∩ X and thus, N [v] ∩ X = N [w] ∩ X.
This has two consequences. First for each q ∈ {−1, 1}2 the set Vq is equally ordered up to
reflection when we order the elements corresponding to their position in the i-th dimension,
i ∈ [2]. Further this implies that if we had defined H using the second dimension instead of the
first (cf. Claim 1) then the result would have been the same.
Claim 3: Let p 6= q ∈ Q and suppose Yq = Yp 6= ∅. Then Vp+q ⊆ Yq .
First note that p and q can not be opposite of each other since then k = |X|, which was
excluded before. Without loss of generality consider q = (0, −1) and p = (−1, 0). Let u ∈ Vp ,
v ∈ Vq and w ∈ Vp+q . Since u ∼snh v we get N [u] ∩ X = N [v] ∩ X = N [u] ∩ N [v] ∩ X.
First consider the case that f (w)1 ≤ f (u)1 . Let x ∈ N [w] ∩ X. Then |f (u)1 − f (x)1 | ≤ 1
because f (w)1 ≤ f (u)1 ≤ f (x)1 ≤ f (w)1 + 1. Further f (u)2 ∈ [− 12 , 12 ]. So x ∈ N [u] ∩ X and
thus, N [u] ∩ X = N [w] ∩ X. For f (w)2 ≤ f (v)2 the same argument can be used to show that
N [v] ∩ X = N [w] ∩ X. Otherwise f (w)1 ≥ f (u)1 and f (w)2 ≥ f (v)2 . Let x ∈ N [u] ∩ N [v] ∩ X.
Then |f (w)1 −f (x)1 | ≤ 1 because f (u)1 ≤ f (w)1 ≤ f (x)1 ≤ f (u)1 +1. Further |f (w)2 −f (x)2 | ≤ 1
since f (v)2 ≤ f (w)2 ≤ f (x)2 ≤ f (v)2 + 1. So x ∈ N [w] ∩ X and hence, N [w] ∩ X = N [u] ∩ X.
Claim 4: Let p 6= q ∈ Q and suppose Yq = Yp 6= ∅. Further assume that there are v ∈ Vq , w ∈ Vp
with vw ∈ E(G). Then Vp ∪ Vq ∪ Vp+q forms a clique.
First observe that Vq ∪ Vp induces a connected subgraph of G. So Vp ∪ Vq forms a clique due
∗
the definition of Pclique
. Suppose Vp+q 6= ∅. Then Vq ∪ Vp ∪ Vp+q induces a connected subgraph,
since otherwise Vp+q would be disconnected of the rest of the graph. So the statement follows
using Claim 3.
Claim 5: Let p, q ∈ Q with qi 6= pi for i ∈ [2]. Further let v ∈ Vq , w ∈ Vp and u ∈ Vp+q , such
that vw ∈ E(G). Then {u, v, w} forms a clique or u ∼clique v or u ∼clique w.
Without loss of generality assume q = (−1, 0) and p = (0, −1). First consider the case that
f (u)1 ≤ f (v)1 . Let x ∈ N [u] ∩ X. Then f (u)1 ≤ f (v)1 ≤ f (x)1 ≤ f (u)1 + 1 and f (v)2 , f (x)2 ∈
[− 21 , 12 ]. Thus, x ∈ N [v] ∩ X and u ∼snh v. Analogously u ∼snh w if f (u)2 ≤ f (w)2 .
If f (u)1 ≤ f (v)1 and f (u)2 ≤ f (w)2 then {u, v, w} forms a clique by Claim 4. If f (u)1 ≤ f (v)1
and f (u)2 ≥ f (w)2 then u ∼clique v because uv ∈ E(G) and u ∼snh v. Similarly u ∼clique w
if f (u)1 ≥ f (v)1 and f (u)2 ≤ f (w)2 . Otherwise {u, v, w} forms a clique, because vw ∈ E(G),
f (v)1 ≤ f (u)1 ≤ f (w)1 and f (v)2 ≥ f (u)2 ≥ f (w)2 .
∗
Claim 6: For each Z ∈ Pclique
there is VH (Z) ⊆ V, such that H[VH (Z)] is connected and

22

S

Z ′ ∈VH (Z)

= Z.

2
By definition the
S set Z induces a clique, so there is t ∈ [3] and q1 , . . . , qt ∈ {−1, 0, 1} \ {(0, 0)},
such that Z ⊆ i∈[t] Vqi . Further suppose that t is minimal. If t = 1 then Z = Z ∩ Vq1 ∈ Vq ⊆ V.
In this case let VH (Z) = {Z}. So consider t = 2. First suppose there is some i ∈ [2] with
(q1 )i = (q2 )i . Without loss of generality assume i = 2. Let VH (Z) = {Z ∩ Vq1 , Z ∩ Vq2 }. It
follows from Claim 1 that these two elements are neighbors in H. Otherwise q1 , q2 ∈ Q and
Yq1 = Yq2 6= ∅. Further there are v ∈ Vq1 , w ∈ Vq2 with vw ∈ E(G). So Vq1 +q2 = ∅ and
Z = Vq1 ∪ Vq2 . Let VH (Z) = {Vq1 , Vq2 , Vq1 +q2 }, which is connected in H. Finally consider t = 3.
Then, without loss of generality, q1 , q2 ∈ Q and q3 = q1 + q2 . So the statement follows from
Claim 3 and 4 by choosing VH (Z) = {Vq1 , Vq2 , Vq1 +q2 }.

In the following we assume that neither endpoint of H[VH (Z)] is labeled by the empty set.
∗
Claim 7: For eachSZ ∈ Pclique
there is a set E ⊆ V of elements labeled with the empty set, such
′
that the graph H[ Z ′ ∈NG
[Z] VH (Z ) ∪ E] is connected.
clique

We consider two cases. First assume Z ∩ Vq = ∅ for all q ∈ Q. In this case VH (Z) = {Z}. Then
Z ⊆ Vp for some p ∈ {−1, 1}2. Let q1 , q2 ∈ Q with
let H[Rq1 ,q2 ] be the
S q1 + q2 = p. Further
′
V
(Z
)]
is
a
connected subgraph
path from Vq1 to Vq2 that contains Z. Then H[ Z ′ ∈NG
H
clique [Z]
of H[Rq1 ,q2 ] by Claim 1 and 2.
So let q ∈ Q with Z ⊆ Yq . If there are distinct q1 , q2 ∈ Q with Z ∩ Vqi 6= ∅ then it follows
from Claim 3 and 4 that NGclique [Z] = {Z}, so the statement follows from Claim 6. So suppose
there is a unique q ∈ Q with
is some Z ′ ∈ NGclique [Z] and q 6= p ∈ Q with
S Z ∩ Vq 6= ∅. If there
′
′
VH (Z ) or Vp+q = {∅} by Claim 5. So the statement
Z ∩ Vp 6= ∅ then Vp+q ⊆ Z ′ ∈NG
clique [Z]
follows in combination with Claim 1 and 2.
Claim 8: Gclique is a proper circular arc graph.
S
∗
VH (Z ′ ) ∪ Ei ] be defined according to Claim
and let Hi = H[ Z ′ ∈NG
Let Z1 , Z2 ∈ Pclique
clique [Zi ]
7. Consider the situation that H1 is a subgraph of H2 and suppose towards a contradiction that
they do not share an endpoint. Then Z1 ∈ V (H2 ) and let S be the endpoint of H2 , so that Z1 lies
on the path from Z2 to S in H2 . We can assume that S ∈
/ E2 . If Z2 ⊆ Vq for some q ∈ {−1, 1}2
then Z1 ⊆ Vq because Z1 is not an endpoint of H2 . But then S is a neighbor of Z1 by Claim 1
and 2. So there is a unique q ∈ Q, such that Z2 ∩ Vq 6= ∅. Since Z1 is not an endpoint of H2
there is some p ∈ {−1, 1}2 with Z1 ⊆ Vp . But then either S ⊆ Vp or S ⊆ Vq′ with q + q ′ = p. In
the first case Z1 and S are clearly neighbors, in the other case this follows from Claim 5.
So by contradicting each VH (Z) to a single vertex and also contradicting edges incident to a
vertex labeled by the empty set it follows from Claim 6,7 and Proposition 2.9 that Gclique is a
proper circular arc graph.
Claim 9: Gclique has at most eight connected components.
∗
First observe that for each q ∈ Q there is at most one Z ∈ Pclique
, such that Vq ∩ Z 6= ∅, by
Lemma 5.8. But after removing these vertices the remaining vertices induce a graph, which is
the disjoint union of at most 4 cliques.

Lemma 5.11. Gclique has no induced subgraph isomorphic to 3K2 .
Proof. Suppose towards a contradiction that there is an induced subgraph isomorphic to 3K2 .
∗
Let Y1 , Y2 , Y3 , Z1 , Z2 , Z3 ∈ Pclique
, such that the only non-edges in Gclique [Y1 , Y2 , Y3 , Z1 , Z2 , Z3 ]

23

are Yi Zi for i ∈ [3]. This means that for i ∈ [3] there are vi ∈ Yi , wi ∈ Zi with vi wi ∈
/ E(G). But
then G[v1 , v2 , v3 , w1 , w2 , w3 ] ∼
= 3K2 contradicting Corollary 3.6.
Theorem 5.12. Let G be a simple clique neighborhood graph with respect to X ⊆ V (G). Then
one can compute in polynomial time a canonical clique-partition P and a canonical colored graph
H, such that
1. P ⊆ V (H) and P is Aut(H)-invariant,
2. H is 8-circle-bounded,
3. im(ϕ) ≤ Aut(H)|P where ϕ : Aut(G) → Sym(P) is the natural action of Aut(G) on P.
Proof. For all v, w ∈ V (G) \ X it holds that |N [v] ∩ X| = |N [w] ∩ X|. Let k = |N [v] ∩ X| for some
v ∈ V (G). If k = |X| then G is a neighborhood unit square graph and hence, the statement
follows from Theorem 5.7. Otherwise initialize P with the empty set and H with the empty
graph. Let B = {Y ∈ Psnh | G[Y ] is not a disjoint union of cliques}. Then |B| ≤ 4 by Lemma
5.9. Add the elements of B to the vertex set of H and color each Y ∈ B by the color nuc-init.
For each Y ∈ B the graph G[Y ] is a neighborhood unit square graph. Let PY be the partition
and HY = (VY , EY , cY ) be the graph computed by Theorem 5.7. Add each element of PY to
the partition P and add the elements of VY to the vertex set of H. Each v ∈ VY is colored by
(nuc, cY (v)) and connected
to Y . Additionally all edges in EY are added to the graph H.
S
Now let B = Y ∈B Y and B = V (G) \ (X ∪ B). Let Y be the partition into the connected
components of G[B] and add each element of Y to the vertex set H. Furthermore each Y ∈ Y
is colored by cc-par. Note that |Y| ≤ 8. Now consider Y ∈ Y. Then G[Y ∪ X] is a simple
∗
clique neighborhood unit square graph and Pclique
partitions the set Y . Consider the graph
Gclique , which is a proper circular arc graph with at most eight connected components
S according
∗
to Lemma 5.10. Let C ⊆ Pclique
be a connected component of Gclique . Let C = A∈C A and
add C to the vertex set of H, where C is connected to Y and colored by clique-cc.
If Gclique [C] is co-bipartite then Gclique [C] has t ≤ 2 non-trivial connected components by
Lemma 5.11. For i ∈ [t] let Zi,1 , Zi,2 be the unique bipartition of the i-th non-trivial component
S
of Gclique [C]. Further let Z be the set of isolated vertices in Gclique [C]. Let Zi,j = A∈Zi,j A for
S
i ∈ [t], j ∈ [2] and Z = A∈Z A. Add Zi,1 , Zi,2 , i ∈ [t] to the partition P and to the vertex set
of H, where each of those vertices is connected to C and colored by fin-par. Note that G[Zi,j ]
is a clique by the definition of Gclique . If Z 6= ∅ then Z is also added to P and the vertex set of
H, connected to C and colored by fin-par.
So consider the case that Gclique [C] is not co-bipartite. For each v ∈ C let M (v) be the
∗
unique set with M (v) ∈ Pclique
and v ∈ M (v). Let v ∼ w if M (v) and M (w) are connected
twins in Gclique . Let Z be the corresponding partition into equivalence classes. Note that each
Z ∈ Z induces a clique in G by the definition of Gclique . Each element Z ∈ Z is added to P
and to the vertex set of H. Further Z is colored by fin-par and we add edges according to the
cycle obtained from Proposition 2.10. This completes the description of P and H.
Clearly P and H are canonically defined and P ⊆ H. Further P is invariant under Aut(H)
because of the vertex colors. Finally it can easily be verified for each step of the construction
that the graph H is 8-circle-bounded.

6

Global Structure

In this section we are ready construct a canonical, clique-stable partition P together with some
canonical 8-circle-bounded graph H, such that P ⊆ V (H) and P is Aut(H)-invariant. This
24

method is the central part of our algorithm and gives us a good supergroup of the natural action
of the automorphism group on the computed partition. The computed supergroup is then given
to the subroutine that computes setwise stabilizers for groups in Γ8 , to obtain the automorphism
group of G[P]. To achieve this goal we proceed in two steps. First, we compute a clique-partition
P which is only canonical but not necessarily clique-stable, together with a corresponding graph
H. For this part of the algorithm we make use of the partitioning algorithm for neighborhoods
of cliques established in the previous section. Then, in a second step, we refine the computed
partition using the color refinement algorithm while simultaneously updating the graph H.

6.1

Clique-Partition

In this subsection we implement the method which realizes the first part of the described algorithm.
Theorem 6.1. Let G be a connected unit square graph with singleton vertex. Then one can
compute in polynomial time a canonical clique-partition P and a canonical colored graph H,
such that
1. P ⊆ V (H) and P is invariant under Aut(H),
2. H is 8-circle-bounded,
3. im(ϕ) ≤ Aut(H)|P where ϕ : Aut(G) → Sym(P) is the natural action of Aut(G) on P.
Proof. Let v0 ∈ V (G)
S be a singleton vertex. For i ≥ 0 let Yi := {v ∈ V (G) | d(v0 , v) = i}.
Further let Gi := G[ j≤i Yj ]. Then there is some N ≤ n = |V (G)|, such that GN = G. Let
P0 = {{v0 }} and H0 be the graph consisting of only one vertex, namely X0 = {v0 }.
Let i ∈ [N ]. Suppose we have already computed a canonical clique-partition Pi−1 and a
canonical colored graph Hi−1 with the desired properties for the graph Gi−1 . Initialize the graph
Hi with Hi−1 and Pi with Pi−1 . For v ∈ Yi let Ni−1 (v) = {X ∈ Pi−1 | ∃w ∈ X : vw ∈ E(G)}.
Further let v ∼init w if Ni−1 (v) = Ni−1 (w). This gives an initial canonical partition Qi of Yi ,
which is added to the vertex set. Further there is an edge between Z and every X ∈ Ni−1 (v)
for v ∈ Z and each vertex Z ∈ Qi is colored by (i, init). Consider Z ∈ Qi and let Ni−1 (v) =
{X1Z , . . . , XkZZ } for some v ∈ Z. For v, w ∈ Z define v ∼deg w if |N [v] ∩ XiZ | = |N [w] ∩ XiZ | for
all i ∈ [kZ ]. This gives a canonical partition Z of Z. Again, the set Z is added to the vertex
set along with vertices (XiZ , j) for all i ∈ [kZ ], j ∈ [|XiZ |]. The vertices (XiZ , j) are colored by
(i, init, j) and there are edges to Z and XiZ . Each A ∈ Z is colored by (i, deg) and there is an
edge to (XiZ , j) if |N [v] ∩ XiZ | = j for some v ∈ A.
So consider some A ∈ Z. Note that for each i ∈ [kZ ] the graph G[A ∪ XiZ ] is a simple clique
neighborhood graph with respect to XiZ . For each i ∈ [kZ ] we obtain a clique-partition Ai of A
and a graph HA,i = (VA,i , EA,i , cA,i ) from Theorem 5.12. For each i ∈ [kZ ] the set VA,i is added
to the vertex set of Hi . Each v ∈ VA,i is colored with (i, cnp, cA,i (v)) and connected
to A and
T
XiZ . Furthermore the elements of EA,i are added to the edge set. Let PA = i∈[kZ ] Ai . The set
PA is also added to the vertex set. Each B ∈ PA is colored by (i, fin-par) and connected to the
unique A′ ∈ Ai with B ⊆ A′ for every i ∈ [kZ ]. Finally PA is added to the partition Pi . This
completes the description to Hi and Pi .
Clearly Pi and Hi are canonically defined given Pi−1 by Theorem 5.12. Further Pi is a cliquepartition and Pi ⊆ V (Hi ). From the vertex colors it is also imminent that Pi is invariant under
Aut(Hi ). It remains to prove that Hi is 8-circle-bounded. But this can easily be verified for each
layer of the construction. Finally note that 3 follows immediately from the other properties.

25

w1
w8

w7

w2

v8
v7
v6

v1

v5

v2
v3
v4

w3

w4

w6
w5

Figure 6.1: Realization for the graph G8
Corollary 6.2. Let G be a connected unit square graph with singleton vertex. Then one
can compute in polynomial time a canonical clique-partition P, such that im(ϕ) ∈ Γ8 where
ϕ : Aut(G) → Sym(P) is the natural action of Aut(G) on P.
Proof. This follows directly from Theorem 2.5 and 6.1.
Remark 6.3. The constant d = 8 is tight for the previous corollary. In particular the graph G8
with V (G) = {vi | i ∈ [9]} ∪ {wi | i ∈ [8]} and E(G) = {vi vj | i 6= j ∈ [9]} ∪ {vi wi | i ∈ [8]} is
a unit square graph (the vertex v9 may be a singleton vertex). A possible realization of G8 is
depicted in Figure 6.1.

6.2

Refinement

In this subsection we implement the second part of the algorithm, namely we refine the partition
computed in previous section to turn it into a clique-stable partition. This is be done by the
color refinement algorithm. Simultaneously the 8-circle-bounded graph computed in the previous
subsection is extended to obtain structure for the refined partition. The crucial idea for extending the graph H is to use additional layers which model the iterations of the color refinement
algorithm.
Theorem 6.4. Let G be a connected unit square graph with singleton vertex. Then one can
compute in polynomial time a canonical, clique-stable partition P and a canonical colored graph
H, such that
1. P ⊆ V (H) and P is invariant under Aut(H),
2. H is 8-circle-bounded,
3. im(ϕ) ≤ Aut(H)|P where ϕ : Aut(G) → Sym(P) is the natural action of Aut(G) on P.
Proof. Let P be the partition and H = (V (H), E(H), cH ) be the graph constructed by Theorem
6.1. Define P0 = P ∪ {M(G)}. Let ∼0 be the corresponding equivalence relation. For v, w ∈
V (G) ∪ M(G) let v ∼i+1 w if v ∼i w and |NG∗M (v) ∩ X| = |NG∗M (w) ∩ X| for all X ∈ Pi . Further
26

let Pi+1 be the partition into the equivalence classes of ∼i+1 . Observe that Pi is the partition
computed in the i-th round of the color refinement algorithm applied to the graph G∗M if the
initial partition is P0 . Let N ∈ N be minimal, such that PN = PN +1 . Then P ∗ = PN ∩ 2V (G) is
a canonical, clique-stable partition of the vertices. Now define the graph H ∗ with vertex set


[
V (H ∗ ) = V (H) ⊎ 
(Pi × {i}) ∪ (Pi × {i} × {0, . . . , |V (G)|}) ⊎ P ∗
0≤i≤N

as follows. Each vertex v ∈ V (H) is colored the same way as in H, that is cH ∗ (v) = cH (v). A
vertex v ∈ Pi × {i} is colored by cH ∗ (v) = (cs-par, i) and each v ∈ Pi × {i} × {0, . . . , |V (G)|}
is colored by cH ∗ (v) = (cs-par, i, v3 ), where v3 denotes the third component of v. The vertices
v ∈ P ∗ are colored by cH ∗ (v) = fin-cs-par. For the edge set, first each edge of H is also
added to H ∗ and for each X ∈ P there is an edge between X and (X, 0). For i ∈ {0, . . . , N } the
following edges are added to the graph H ∗ . Let X ∈ Pi . Then there are edges between (X, i)
and (X, i, j) for all j ∈ {0, . . . , |V (G)|}. Suppose i ≥ 1. Then there is an edge between (X, i)
and (X ′ , i − 1, j) if |N (v) ∩ X ′ | = j for some and thus for all v ∈ X. Furthermore there is an
edge between (X, i) and (X ′ , i − 1) for the unique X ′ ∈ Pi−1 , such that X ⊆ X ′ . Finally there
are edges between (X, N ) and X for each X ∈ P ∗ . This finishes the description of the graph H ∗ .
Clearly H ∗ and is canonically defined and P ∗ ⊆ V (H ∗ ). Further P ∗ is invariant under
Aut(H ∗ ) because of the vertex colors. It remains to show that the graph H ∗ is 8-circle-bounded.
First H is 8-circle-bounded. The remaining colors are ordered lexicographically, then it follows
directly from the definition of H ∗ that the graph is 8-circle-bounded.
Remark 6.5. Observe, that the presented algorithm is not restricted to unit square graphs. In
fact, whenever one is given a canonical partition and a Γd -group, which builds an upper bound
on the top action, one can efficiently compute a Γd -group, which gives an upper bound on the
top action of the refined partition.

6.3

Global automorphism group

Together with Theorem 4.12 this gives us sufficient structure to compute the natural action of the
automorphism group on the computed partition. This can also be used to solve the isomorphism
problem.
Theorem 6.6. Let G be a connected, twin-free unit square graph with a singleton vertex. Then
one can compute in polynomial time a canonical, clique-stable partition P and a set S ⊆ Sym(P),
such that hSi = im(ϕ) ∈ Γ8 where ϕ : Aut(G) → Sym(P) is the natural action of Aut(G) on P.
Proof. Let P be the canonical, clique-stable partition and H the canonical, 8-circle-bounded
graph obtained from Theorem 6.4. Then Aut(H) can be computed in polynomial time and
Aut(H) ∈ Γ8 by Theorem 2.6 and 2.5. Further P is invariant under Aut(H). Since H is
canonical this implies im(ϕ) ≤ Aut(H)|P ∈ Γ8 . Furthermore im(ϕ) = Aut(G[P]) by Theorem
4.12. A generating set for Aut(G[P]) can be computed in polynomial time using Proposition
2.2.
Theorem 6.7. The Graph Isomorphism Problem for unit square graphs can be solved in polynomial time.
Proof. Let G1 , G2 be two unit square graphs. First, it can be assumed that G1 and G2 are
connected by considering the connected components separately. Furthermore, the graphs can
be assumed to be twin-free using modular decompositions of graphs (cf. [Sch15]). Let c ∈ N
27

be a fresh color (i.e. a color which does not appear in G1 or G2 ). For a graph G and a vertex
v ∈ V (G) we denote by Gv7→c the graph where vertex v is colored by c. Pick v1 ∈ V (G1 ). For
each v2 ∈ V (G2 ) test whether Gv11 7→c ∼
= Gv22 7→c by the following procedure. For i ∈ [2] let Pi
be the partition and Hi be the graph computed by Theorem 6.4 for the graph Gvi i 7→c . Let H
be the disjoint union of H1 and H2 . Note that H1 ∼
= H2 if Gv11 7→c ∼
= Gv22 7→c because the graph
Hi is canonical. Compute a generating set for Aut(H) ∈ Γ8 . This can be done in polynomial
time according to Theorem 2.6. Let G be the disjoint union of Gv11 7→c [P1 ] and Gv22 7→c [P2 ]. Then
Aut(G) ≤ Aut(H)|P1 ∪P2 and hence a generating set for Aut(G) can be computed in polynomial
time using Proposition 2.2 (note that Aut(G) is the set of permutations which stabilize the edge
set). By Theorem 4.12 it holds that Gv11 7→c ∼
= Gv22 7→c if and only if there is an automorphism
v1 7→c
v2 7→c
γ ∈ Aut(G) that maps G1
[P1 ] to G2
[P2 ]. Since G is the disjoint union of of Gv11 7→c [P1 ]
v2 7→c
and G2
[P2 ] and both of these graphs are connected it holds that if such an automorphism
exists then there will also be one present in the generating set of Aut(G). Thus it can be checked
in polynomial time whether Gv11 7→c ∼
= Gv22 7→c .
Remark 6.8. The running time of the presented algorithm is dominated by the running time
for the subroutine computing setwise stabilizers for groups in Γ8 , which in turn depends on the
maximal size of primitive Γ8 -groups.
The latter was analyzed by Babai, Cameron and Pálfy in [BCP82] and proven to be polynomially bounded in the size of the permutation domain. For a complexity analysis of the setwise
stabilizer subroutine we refer to [Luk82, Luk91, BKL83]. Note that the setwise stabilizer subroutine is also used for computing the automorphism group of H and the graph H might be much
larger than the original graph G.
Remark 6.9. The presented algorithm also gives us some insight about the structure of the
automorphism group of a unit square graph in case the graph has a singleton vertex. For the
automorphism group, there is an invariant clique-partition, such that the natural action forms a
Γ8 -group.
An interesting question is whether a similar statement still holds if the given graph does not
have a singleton vertex. We leave this question open.

7

Discussion

We presented a polynomial time algorithm solving the Graph Isomorphism Problem for unit
square graphs. The main idea of the algorithm is to canonically extract a clique-partition and
graph structure that can be described by 8-circle-bounded graphs. This gives an upper bound on
the action of the automorphism group on the canonical partition. Then Luks’ algorithm is used
to precisely determine this action which gives sufficient information to decide whether two given
unit square graphs are isomorphic. So overall the presented algorithm heavily depends on group
theoretic methods. This raises the question whether the problem can also be solved without the
use of such methods. In fact, it might be that the k-dimensional Weisfeiler-Leman algorithm can
identify every unit square graph for sufficiently large k. This is left as an open question.
Furthermore it is an interesting question whether the methods presented in this work can
be adapted to other geometric classes for which the isomorphism problem is still open. At first
glance a natural candidate seems to be the class of unit disk graphs. However, it turns out that
there are some crucial structural differences to unit square graphs. In particular, large symmetric
groups in the automorphism group of a unit disk graph do not necessarily originate from cliques.
In other words, there are unit disk graphs with singleton vertex, such that for each canonical
28

clique-partition the natural action of the automorphism group contains a large symmetric group.
Another candidate is the class of unit grid intersection graphs. Unit grid intersection graphs can
be seen as a bipartite version of unit square graphs. However, in order to apply the methods of
this work, one would require a different notion of locality since vertices being close to each other
in the realization may not be connected in the graph.
Finally we would like to address two natural generalizations of unit square graphs. The first
one concerns the dimension of the realization, that is, what is the complexity of graph isomorphism for graphs with d-dimensional L∞ -realization for any constant number d. Intuitively, it
seems that similar arguments might be applicable to higher dimensions. In particular, for the
neighborhood of a clique the number of independent neighbors is still bounded. The second
extension concerns squares of arbitrary size. This is still a natural restriction for the class of
intersection graphs of rectangles which is GI-complete. The reduction uses complete bipartite
graphs of arbitrary size as induced subgraphs (see [Ueh08]) which can not be modeled as intersection graphs of squares. So it might be possible that isomorphisms test can be efficiently
performed even for square graphs. However, this would require some new ideas since the number
of independent neighbors of a vertex is unbounded.
Acknowledgements I want to thank Martin Grohe and Pascal Schweitzer for several helpful
discussions and comments throughout this work.

References
[Bab14]

László Babai. On the automorphism groups of strongly regular graphs I. In Moni
Naor, editor, Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ,
USA, January 12-14, 2014, pages 359–368. ACM, 2014.

[Bab15]

László Babai. Graph isomorphism in quasipolynomial time. CoRR, abs/1512.03547,
2015.

[BBG13]

Christoph Berkholz, Paul S. Bonsma, and Martin Grohe. Tight lower and upper
bounds for the complexity of canonical colour refinement. In Hans L. Bodlaender
and Giuseppe F. Italiano, editors, Algorithms - ESA 2013 - 21st Annual European
Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, volume 8125
of Lecture Notes in Computer Science, pages 145–156. Springer, 2013.

[BCP82]

László Babai, Peter J. Cameron, and Péter P. Pálfy. On the orders of primitive groups
with restricted nonabelian composition factors. Journal of Algebra, 79(1):161–168,
1982.

[BCS+ 13] László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and John Wilmes. Faster
canonical forms for strongly regular graphs. In 54th Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA,
USA, pages 157–166. IEEE Computer Society, 2013.
[BK98]

Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is np-hard. Comput. Geom., 9(1-2):3–24, 1998.

[BKL83]

László Babai, William M. Kantor, and Eugene M. Luks. Computational complexity
and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages
162–171. IEEE Computer Society, 1983.
29

[Bre96]

Heinz Breu. Algorithmic Aspects of Constrained Unit Disk Graphs. PhD thesis,
University of British Columbia, Vancouver, Canada, 1996.

[CB81]

Charles J. Colbourn and Kellogg S. Booth. Linear time automorphism algorithms for
trees, interval graphs, and planar graphs. SIAM J. Comput., 10(1):203–225, 1981.

[CCJ90]

Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs.
Discrete Mathematics, 86(1-3):165–177, 1990.

[CFI92]

Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the
number of variables for graph identifications. Combinatorica, 12(4):389–410, 1992.

[CLM+ 13] Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum, Francisco J.
Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcfiter. Isomorphism of graph
classes related to the circular-ones property. Discrete Mathematics & Theoretical
Computer Science, 15(1):157–182, 2013.
[FG65]

Delbert R. Fulkerson and Oliver A. Gross. Incidence matrices and interval graphs.
Pacific Journal of Mathematics, 15(3):835–855, 1965.

[FHL80]

Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms
for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 36–41. IEEE Computer
Society, 1980.

[FLS12]

Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January
17-19, 2012, pages 1563–1575. SIAM, 2012.

[Gol04]

Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57). North-Holland Publishing Co., Amsterdam, The Netherlands, 2004.

[HEO05]

Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien. Handbook of Computational
Group Theory. Discrete Mathematics and Its Applications. CRC Press, 2005.

[Hua95]

Jing Huang. On the structure of local tournaments. J. Comb. Theory, Ser. B,
63(2):200–221, 1995.

[KKLV11] Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, and Oleg Verbitsky. Interval
graphs: Canonical representations in logspace. SIAM J. Comput., 40(5):1292–1315,
2011.
[KKV12]

Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. Solving the canonical representation and star system problems for proper circular-arc graphs in logspace. In
Deepak D’Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, IARCS
Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, volume 18
of LIPIcs, pages 387–399. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012.

[KKV13]

Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. Helly circular-arc graph
isomorphism is in logspace. In Krishnendu Chatterjee and Jirí Sgall, editors, Mathematical Foundations of Computer Science 2013 - 38th International Symposium,
30

MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, volume 8087
of Lecture Notes in Computer Science, pages 631–642. Springer, 2013.
[Lau10]

Bastian Laubner. Capturing polynomial time on interval graphs. In Proceedings of
the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 1114 July 2010, Edinburgh, United Kingdom, pages 199–208. IEEE Computer Society,
2010.

[Luk82]

Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci., 25(1):42–65, 1982.

[Luk91]

Eugene M. Luks. Permutation groups and polynomial-time computation. In Larry
Finkelstein and William M. Kantor, editors, Groups And Computation, Proceedings
of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 7-10, 1991,
volume 11 of DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, pages 139–176. DIMACS/AMS, 1991.

[McK81]

Brendan D. McKay. Practical Graph Isomorphism. Congressus Numerantium, 30:45–
87, 1981.

[Mil83]

Gary L. Miller. Isomorphism of graphs which are pairwise k-separable. Information
and Control, 56(1/2):21–33, 1983.

[MN87]

Annabelle McIver and Peter M. Neumann. Enumerating finite groups. The Quarterly
Journal of Mathematics, 38(4):473–488, 1987.

[Rot95]

Joseph J. Rotman. An Introduction to the Theory of Groups. Graduate Texts in
Mathematics. Springer, 1995.

[Sch15]

Pascal Schweitzer. Towards an isomorphism dichotomy for hereditary graph classes.
In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on
Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching,
Germany, volume 30 of LIPIcs, pages 689–702. Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2015.

[Ser03]

Ákos Seress. Permutation Group Algorithms:. Cambridge Tracts in Mathematics.
Cambridge University Press, 2003.

[Tuc74]

Alan Tucker. Structure theorems for some circular-arc graphs. Discrete Math., 7(12):167–195, 1974.

[Ueh08]

Ryuhei Uehara. Simple geometrical intersection graphs. In Shin-Ichi Nakano and
Md. Saidur Rahman, editors, WALCOM: Algorithms and Computation, Second International Workshop, WALCOM 2008, Dhaka, Bangladesh, February 7-8, 2008.,
volume 4921 of Lecture Notes in Computer Science, pages 25–33. Springer, 2008.

[Ueh14]

Ryuhei Uehara. The graph isomorphism problem on geometric graphs. Discrete
Mathematics & Theoretical Computer Science, 16(2):87–96, 2014.

31

