
Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an
induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is
definable in $k$variable firstorder logic. The recognition problem of $I(F)$,
known as Induced Subgraph Isomorphism (for the pattern graph $F$), is solvable
in time $O(n^{W[F]})$. Motivated by this fact, we are interested in determining
or estimating the value of $W[F]$. Using Olariu's characterization of pawfree
graphs, we show that $I(K_3+e)$ is definable by a firstorder sentence of
quantifier depth 3, where $K_3+e$ denotes the paw graph. This provides an
example of a graph $F$ with $W[F]$ strictly less than the number of vertices in
$F$. On the other hand, we prove that $W[F]=4$ for all $F$ on 4 vertices except
the paw graph and its complement. If $F$ is a graph on $t$ vertices, we prove a
general lower bound $W[F]>(1/2o(1))t$, where the function in the littleo
notation approaches 0 as $t$ inreases. This bound holds true even for a related
parameter $W^*[F]\le W[F]$, which is defined as the minimum $k$ such that
$I(F)$ is definable in the infinitary logic $L^k_{\infty\omega}$. We show that
$W^*[F]$ can be strictly less than $W[F]$. Specifically, $W^*[P_4]=3$ for $P_4$
being the path graph on 4 vertices.
Using the lower bound for $W[F]$, we also obtain a succintness result for
existential monadic secondorder logic: A usage of just one monadic quantifier
sometimes reduces the firstorder quantifier depth at a superrecursive rate.

Let $v(F)$ denote the number of vertices in a fixed connected pattern graph
$F$. We show an infinite family of patterns $F$ such that the existence of a
subgraph isomorphic to $F$ is expressible by a firstorder sentence of
quantifier depth $\frac23\,v(F)+1$, assuming that the host graph is
sufficiently large and connected. On the other hand, this is impossible for any
$F$ with using less than $\frac23\,v(F)2$ firstorder variables.

Let $F$ be a connected graph with $\ell$ vertices. The existence of a
subgraph isomorphic to $F$ can be defined in firstorder logic with quantifier
depth no better than $\ell$, simply because no firstorder formula of smaller
quantifier depth can distinguish between the complete graphs $K_\ell$ and
$K_{\ell1}$. We show that, for some $F$, the existence of an $F$ subgraph in
\emph{sufficiently large} connected graphs is definable with quantifier depth
$\ell3$. On the other hand, this is never possible with quantifier depth
better than $\ell/2$. If we, however, consider definitions over connected
graphs with sufficiently large treewidth, the quantifier depth can for some $F$
be arbitrarily small comparing to $\ell$ but never smaller than the treewidth
of $F$. Moreover, the definitions over highly connected graphs require
quantifier depth strictly more than the density of $F$. Finally, we determine
the exact values of these descriptive complexity parameters for all connected
pattern graphs $F$ on 4 vertices.

It is well known that any graph admits a crossingfree straightline drawing
in $\mathbb{R}^3$ and that any planar graph admits the same even in
$\mathbb{R}^2$. For a graph $G$ and $d \in \{2,3\}$, let $\rho^1_d(G)$ denote
the minimum number of lines in $\mathbb{R}^d$ that together can cover all edges
of a drawing of $G$. For $d=2$, $G$ must be planar. We investigate the
complexity of computing these parameters and obtain the following hardness and
algorithmic results.
 For $d\in\{2,3\}$, we prove that deciding whether $\rho^1_d(G)\le k$ for a
given graph $G$ and integer $k$ is ${\exists\mathbb{R}}$complete.
 Since $\mathrm{NP}\subseteq{\exists\mathbb{R}}$, deciding $\rho^1_d(G)\le
k$ is NPhard for $d\in\{2,3\}$. On the positive side, we show that the problem
is fixedparameter tractable with respect to $k$.
 Since ${\exists\mathbb{R}}\subseteq\mathrm{PSPACE}$, both $\rho^1_2(G)$ and
$\rho^1_3(G)$ are computable in polynomial space. On the negative side, we show
that drawings that are optimal with respect to $\rho^1_2$ or $\rho^1_3$
sometimes require irrational coordinates.
 Let $\rho^2_3(G)$ be the minimum number of planes in $\mathbb{R}^3$ needed
to cover a straightline drawing of a graph $G$. We prove that deciding whether
$\rho^2_3(G)\le k$ is NPhard for any fixed $k \ge 2$. Hence, the problem is
not fixedparameter tractable with respect to $k$ unless
$\mathrm{P}=\mathrm{NP}$.

We investigate the problem of drawing graphs in 2D and 3D such that their
edges (or only their vertices) can be covered by few lines or planes. We insist
on straightline edges and crossingfree drawings. This problem has many
connections to other challenging graphdrawing problems such as smallarea or
smallvolume drawings, layered or track drawings, and drawing graphs with low
visual complexity. While some facts about our problem are implicit in previous
work, this is the first treatment of the problem in its full generality. Our
contribution is as follows.
We show lower and upper bounds for the numbers of lines and planes needed for
covering drawings of graphs in certain graph classes. In some cases our bounds
are asymptotically tight; in some cases we are able to determine exact values.
We relate our parameters to standard combinatorial characteristics of graphs
(such as the chromatic number, treewidth, maximum degree, or arboricity) and to
parameters that have been studied in graph drawing (such as the track number or
the number of segments appearing in a drawing).
We pay special attention to planar graphs. For example, we show that there
are planar graphs that can be drawn in 3space on a lot fewer lines than in the
plane.

The isomorphism problem is known to be efficiently solvable for interval
graphs, while for the larger class of circulararc graphs its complexity status
stays open. We consider the intermediate class of intersection graphs for
families of circular arcs that satisfy the Helly property. We solve the
isomorphism problem for this class in logarithmic space. If an input graph has
a Helly circulararc model, our algorithm constructs it canonically, which
means that the models constructed for isomorphic graphs are equal.

Color refinement is a classical technique used to show that two given graphs
G and H are nonisomorphic; it is very efficient, although it does not succeed
on all graphs. We call a graph G amenable to color refinement if it succeeds in
distinguishing G from any nonisomorphic graph H. Tinhofer (1991) explored a
linear programming approach to Graph Isomorphism and defined compact graphs: A
graph is compact if its fractional automorphisms polytope is integral. Tinhofer
noted that isomorphism testing for compact graphs can be done quite efficiently
by linear programming. However, the problem of characterizing and recognizing
compact graphs in polynomial time remains an open question.
Our results are summarized below:
 We show that amenable graphs are recognizable in time O((n + m)logn), where
n and m denote the number of vertices and the number of edges in the input
graph.
 We show that all amenable graphs are compact.
 We study related combinatorial and algebraic graph properties introduced by
Tinhofer and Godsil. The corresponding classes of graphs form a hierarchy and
we prove that recognizing each of these graph classes is Phard. In particular,
this gives a first complexity lower bound for recognizing compact graphs.

Given a connected graph $G$ and its vertex $x$, let $U_x(G)$ denote the
universal cover of $G$ obtained by unfolding $G$ into a tree starting from $x$.
Let $T=T(n)$ be the minimum number such that, for graphs $G$ and $H$ with at
most $n$ vertices each, the isomorphism of $U_x(G)$ and $U_y(H)$ surely follows
from the isomorphism of these rooted trees truncated at depth $T$. Motivated by
applications in theory of distributed computing, Norris [Discrete Appl. Math.
1995] asks if $T(n)\le n$. We answer this question in the negative by
establishing that $T(n)=(2o(1))n$. Our solution uses basic tools of finite
model theory such as a bisimulation version of the ImmermanLander 2pebble
counting game.
The graphs $G_n$ and $H_n$ we construct to prove the lower bound for $T(n)$
also show some other tight lower bounds. Both having $n$ vertices, $G_n$ and
$H_n$ can be distinguished in 2variable counting logic only with quantifier
depth $(1o(1))n$. It follows that color refinement, the classical procedure
used in isomorphism testing and other areas for computing the coarsest
equitable partition of a graph, needs $(1o(1))n$ rounds to achieve color
stabilization on each of $G_n$ and $H_n$. Somewhat surprisingly, this number of
rounds is not enough for color stabilization on the disjoint union of $G_n$ and
$H_n$, where $(2o(1))n$ rounds are needed.

A graph $G$ is 3colorable if and only if it maps homomorphically to the
complete 3vertex graph $K_3$. The last condition can be checked by a
$k$consistency algorithm where the parameter $k$ has to be chosen large
enough, dependent on $G$. Let $W(G)$ denote the minimum $k$ sufficient for this
purpose. For a non3colorable graph $G$, $W(G)$ is equal to the minimum $k$
such that $G$ can be distinguished from $K_3$ in the $k$variable
existentialpositive firstorder logic. We define the dynamic width of the
3colorability problem as the function $W(n)=\max_G W(G)$, where the maximum is
taken over all non3colorable $G$ with $n$ vertices.
The assumption $\mathrm{NP}\ne\mathrm{P}$ implies that $W(n)$ is unbounded.
Indeed, a lower bound $W(n)=\Omega(\log\log n/\log\log\log n)$ follows
unconditionally from the work of Nesetril and Zhu on bounded treewidth duality.
The Exponential Time Hypothesis implies a much stronger bound
$W(n)=\Omega(n/\log n)$ and indeed we unconditionally prove that
$W(n)=\Omega(n)$. In fact, an even stronger statement is true: A firstorder
sentence distinguishing any 3colorable graph on $n$ vertices from any
non3colorable graph on $n$ vertices must have $\Omega(n)$ variables.
On the other hand, we observe that $W(G)\le 3\,\alpha(G)+1$ and $W(G)\le
n\alpha(G)+1$ for every non3colorable graph $G$ with $n$ vertices, where
$\alpha(G)$ denotes the independence number of $G$. This implies that
$W(n)\le\frac34\,n+1$, improving on the trivial upper bound $W(n)\le n$.
We also show that $W(G)>\frac1{16}\, g(G)$ for every non3colorable graph
$G$, where $g(G)$ denotes the girth of $G$.
Finally, we consider the function $W(n)$ over planar graphs and prove that
$W(n)=\Theta(\sqrt n)$ in the case.

We present a logspace algorithm that constructs a canonical intersection
model for a given proper circulararc graph, where `canonical' means that
models of isomorphic graphs are equal. This implies that the recognition and
the isomorphism problems for this class of graphs are solvable in logspace. For
a broader class of concaveround graphs, that still possess (not necessarily
proper) circulararc models, we show that those can also be constructed
canonically in logspace. As a building block for these results, we show how to
compute canonical models of circulararc hypergraphs in logspace, which are
also known as matrices with the circularones property. Finally, we consider
the search version of the Star System Problem that consists in reconstructing a
graph from its closed neighborhood hypergraph. We solve it in logspace for the
classes of proper circulararc, concaveround, and coconvex graphs.

A circulararc hypergraph $H$ is a hypergraph admitting an arc ordering, that
is, a circular ordering of the vertex set $V(H)$ such that every hyperedge is
an arc of consecutive vertices. An arc ordering is tight if, for any two
hyperedges $A$ and $B$ such that $A$ is a nonempty subset of $B$ and $B$ is not
equal to $V(H)$, the corresponding arcs share a common endpoint. We give
sufficient conditions for $H$ to have, up to reversing, a unique arc ordering
and a unique tight arc ordering. These conditions are stated in terms of
connectedness properties of $H$.
It is known that $G$ is a proper circulararc graph exactly when its closed
neighborhood hypergraph $N[G]$ admits a tight arc ordering. We explore
connectedness properties of $N[G]$ and prove that, if $G$ is a connected,
twinfree, proper circulararc graph with nonbipartite complement, then $N[G]$
has, up to reversing, a unique arc ordering. If the complement of $G$ is
bipartite and connected, then $N[G]$ has, up to reversing, two tight arc
orderings. As a corollary, we notice that in both of the two cases $G$ has an
essentially unique intersection representation. The last result also follows
from the work by Deng, Hell, and Huang based on a theory of local tournaments.

Given two structures $G$ and $H$ distinguishable in $\fo k$ (firstorder
logic with $k$ variables), let $A^k(G,H)$ denote the minimum alternation depth
of a $\fo k$ formula distinguishing $G$ from $H$. Let $A^k(n)$ be the maximum
value of $A^k(G,H)$ over $n$element structures. We prove the strictness of the
quantifier alternation hierarchy of $\fo 2$ in a strong quantitative form,
namely $A^2(n)\ge n/82$, which is tight up to a constant factor. For each
$k\ge2$, it holds that $A^k(n)>\log_{k+1}n2$ even over colored trees, which is
also tight up to a constant factor if $k\ge3$. For $k\ge 3$ the last lower
bound holds also over uncolored trees, while the alternation hierarchy of $\fo
2$ collapses even over all uncolored graphs.
We also show examples of colored graphs $G$ and $H$ on $n$ vertices that can
be distinguished in $\fo 2$ much more succinctly if the alternation number is
increased just by one: while in $\Sigma_{i}$ it is possible to distinguish $G$
from $H$ with bounded quantifier depth, in $\Pi_{i}$ this requires quantifier
depth $\Omega(n^2)$. The quadratic lower bound is best possible here because,
if $G$ and $H$ can be distinguished in $\fo k$ with $i$ quantifier
alternations, this can be done with quantifier depth $n^{2k2}$.

We discuss the definability of finite graphs in firstorder logic with two
relation symbols for adjacency and equality of vertices. The logical depth
$D(G)$ of a graph $G$ is equal to the minimum quantifier depth of a sentence
defining $G$ up to isomorphism. The logical width $W(G)$ is the minimum number
of variables occurring in such a sentence. The logical length $L(G)$ is the
length of a shortest defining sentence. We survey known estimates for these
graph parameters and discuss their relations to other topics (such as the
efficiency of the WeisfeilerLehman algorithm in isomorphism testing, the
evolution of a random graph, quantitative characteristics of the zeroone law,
or the contribution of Frank Ramsey to the research on Hilbert's
Entscheidungsproblem). Also, we trace the behavior of the descriptive
complexity of a graph as the logic becomes more restrictive (for example, only
definitions with a bounded number of variables or quantifier alternations are
allowed) or more expressible (after powering with counting quantifiers).

Establishing arc consistency on two relational structures is one of the most
popular heuristics for the constraint satisfaction problem. We aim at
determining the time complexity of arc consistency testing. The input
structures $G$ and $H$ can be supposed to be connected colored graphs, as the
general problem reduces to this particular case. We first observe the upper
bound $O(e(G)v(H)+v(G)e(H))$, which implies the bound $O(e(G)e(H))$ in terms of
the number of edges and the bound $O((v(G)+v(H))^3)$ in terms of the number of
vertices. We then show that both bounds are tight up to a constant factor as
long as an arc consistency algorithm is based on constraint propagation (like
any algorithm currently known).
Our argument for the lower bounds is based on examples of slow constraint
propagation. We measure the speed of constraint propagation observed on a pair
$G,H$ by the size of a proof, in a natural combinatorial proof system, that
Spoiler wins the existential 2pebble game on $G,H$. The proof size is bounded
from below by the game length $D(G,H)$, and a crucial ingredient of our
analysis is the existence of $G,H$ with $D(G,H)=\Omega(v(G)v(H))$. We find one
such example among old benchmark instances for the arc consistency problem and
also suggest a new, different construction.

We consider straight line drawings of a planar graph $G$ with possible edge
crossings. The \emph{untangling problem} is to eliminate all edge crossings by
moving as few vertices as possible to new positions. Let $fix(G)$ denote the
maximum number of vertices that can be left fixed in the worst case. In the
\emph{allocation problem}, we are given a planar graph $G$ on $n$ vertices
together with an $n$point set $X$ in the plane and have to draw $G$ without
edge crossings so that as many vertices as possible are located in $X$. Let
$fit(G)$ denote the maximum number of points fitting this purpose in the worst
case. As $fix(G)\le fit(G)$, we are interested in upper bounds for the latter
and lower bounds for the former parameter.
For each $\epsilon>0$, we construct an infinite sequence of graphs with
$fit(G)=O(n^{\sigma+\epsilon})$, where $\sigma<0.99$ is a known graphtheoretic
constant, namely the shortness exponent for the class of cubic polyhedral
graphs. To the best of our knowledge, this is the first example of graphs with
$fit(G)=o(n)$. On the other hand, we prove that $fix(G)\ge\sqrt{n/30}$ for all
$G$ with treewidth at most 2. This extends the lower bound obtained by Goaoc
et al. [Discrete and Computational Geometry 42:542569 (2009)] for outerplanar
graphs.
Our upper bound for $fit(G)$ is based on the fact that the constructed graphs
can have only few collinear vertices in any crossingfree drawing. To prove the
lower bound for $fix(G)$, we show that graphs of treewidth 2 admit drawings
that have large sets of collinear vertices with some additional special
properties.

Given a planar graph $G$, we consider drawings of $G$ in the plane where
edges are represented by straight line segments (which possibly intersect).
Such a drawing is specified by an injective embedding $\pi$ of the vertex set
of $G$ into the plane. We prove that a wheel graph $W_n$ admits a drawing $\pi$
such that, if one wants to eliminate edge crossings by shifting vertices to new
positions in the plane, then at most $(2+o(1))\sqrt n$ of all $n$ vertices can
stay fixed. Moreover, such a drawing $\pi$ exists even if it is presupposed
that the vertices occupy any prescribed set of points in the plane. Similar
questions are discussed for other families of planar graphs.

We prove that if one wants to make a plane graph drawing straightline then
in the worst case one has to move almost all vertices.

Let $D$ denote a disk of unit area. We call a subset $A$ of $D$ perfect if it
has measure 1/2 and, with respect to any axial symmetry of $D$, the maximal
symmetric subset of $A$ has measure 1/4. We call a curve $\beta$ in $D$ an
yinyang line if
$\beta$ splits $D$ into two congruent perfect sets,
$\beta$ crosses each concentric circle of $D$ twice,
$\beta$ crosses each radius of $D$ once.
We prove that Fermat's spiral is a unique yinyang line in the class of
smooth curves algebraic in polar coordinates.

We show that the Double Coset Membership problem for permutation groups
possesses perfect zeroknowledge proofs.

We design a perfect zeroknowledge proof system for recognition if two
permutation groups are conjugate.

Being motivated by John Tantalo's Planarity Game, we consider straight line
plane drawings of a planar graph $G$ with edge crossings and wonder how
obfuscated such drawings can be. We define $obf(G)$, the obfuscation complexity
of $G$, to be the maximum number of edge crossings in a drawing of $G$.
Relating $obf(G)$ to the distribution of vertex degrees in $G$, we show an
efficient way of constructing a drawing of $G$ with at least $obf(G)/3$ edge
crossings. We prove bounds $(\delta(G)^2/24o(1))n^2 < \obf G <3 n^2$ for an
$n$vertex planar graph $G$ with minimum vertex degree $\delta(G)\ge 2$.
The shift complexity of $G$, denoted by $shift(G)$, is the minimum number of
vertex shifts sufficient to eliminate all edge crossings in an arbitrarily
obfuscated drawing of $G$ (after shifting a vertex, all incident edges are
supposed to be redrawn correspondingly). If $\delta(G)\ge 3$, then $shift(G)$
is linear in the number of vertices due to the known fact that the matching
number of $G$ is linear. However, in the case $\delta(G)\ge2$ we notice that
$shift(G)$ can be linear even if the matching number is bounded. As for
computational complexity, we show that, given a drawing $D$ of a planar graph,
it is NPhard to find an optimum sequence of shifts making $D$ crossingfree.

A function $f$ of a graph is called a complete graph invariant if the
isomorphism of graphs $G$ and $H$ is equivalent to the equality $f(G)=f(H)$.
If, in addition, $f(G)$ is a graph isomorphic to $G$, then $f$ is called a
canonical form for graphs. Gurevich proves that graphs have a polynomialtime
computable canonical form exactly when they have a polynomialtime computable
complete invariant. We extend this equivalence to the polylogarithmictime
model of parallel computation for classes of graphs with bounded rigidity index
and for classes of graphs with small separators. In particular, our results
apply to three representative classes of graphs embeddable into a fixed
surface, namely, to 5connected graphs, to 3connected graphs admitting a
polyhedral embedding, and 3connected graphs admitting a largeedgewidth
embedding. Another application covers graphs with bounded treewidth. Since in
the latter case an NC completeinvariant algorithm is known, we conclude that
graphs of bounded treewidth have a canonical form (and even a canonical
labeling) computable in NC.

The logical depth of a graph $G$ is the minimum quantifier depth of a first
order sentence defining $G$ up to isomorphism in the language of the adjacency
and the equality relations. We consider the case that $G$ is a dissection of a
convex polygon or, equivalently, a biconnected outerplanar graph. We bound the
logical depth of a such $G$ from above by a function of combinatorial
parameters of the dual tree of $G$.

We prove that every triconnected planar graph is definable by a first order
sentence that uses at most 15 variables and has quantifier depth at most
$11\log_2 n+43$. As a consequence, a canonic form of such graphs is computable
in $AC^1$ by the 14dimensional WeisfeilerLehman algorithm. This provides
another way to show that the planar graph isomorphism is solvable in $AC^1$.

Our starting point is the observation that if graphs in a class C have low
descriptive complexity in first order logic, then the isomorphism problem for C
is solvable by a fast parallel algorithm (essentially, by a simple
combinatorial algorithm known as the multidimensional WeisfeilerLehman
algorithm). Using this approach, we prove that isomorphism of graphs of bounded
treewidth is testable in TC1, answering an open question posed by
Chandrasekharan. Furthermore, we obtain an AC1 algorithm for testing
isomorphism of rotation systems (combinatorial specifications of graph
embeddings). The AC1 upper bound was known before, but the fact that this bound
can be achieved by the simple WeisfeilerLehman algorithm is new. Combined with
other known results, it also yields a new AC1 isomorphism algorithm for planar
graphs.