We implement a new algorithm for listing all maximal cliques in sparse graphs
due to Eppstein, L\"offler, and Strash (ISAAC 2010) and analyze its performance
on a large corpus of real-world graphs. Our analysis shows that this algorithm
is the first to offer a practical solution to listing all maximal cliques in
large sparse graphs. All other theoretically-fast algorithms for sparse graphs
have been shown to be significantly slower than the algorithm of Tomita et al.
(Theoretical Computer Science, 2006) in practice. However, the algorithm of
Tomita et al.

We present techniques for maintaining subgraph frequencies in a dynamic
graph, using data structures that are parameterized in terms of h, the h-index
of the graph. Our methods extend previous results of Eppstein and Spiro for
maintaining statistics for undirected subgraphs of size three to directed
subgraphs and to subgraphs of size four. For the directed case, we provide a
data structure to maintain counts for all 3-vertex induced subgraphs in O(h)
amortized time per update. For the undirected case, we maintain the counts of
size-four subgraphs in O(h^2) amortized time per update.

We show that every graph of maximum degree three can be drawn in three
dimensions with at most two bends per edge, and with 120-degree angles between
any two edge segments meeting at a vertex or a bend. We show that every graph
of maximum degree four can be drawn in three dimensions with at most three
bends per edge, and with 109.5-degree angles, i.e., the angular resolution of
the diamond lattice, between any two edge segments meeting at a vertex or bend.

Simple rectilinear polygons (i.e. rectilinear polygons without holes or
cutpoints) can be regarded as finite rectangular cell complexes coordinatized
by two finite dendrons. The intrinsic $l_1$-metric is thus inherited from the
product of the two finite dendrons via an isometric embedding. The rectangular
cell complexes that share this same embedding property are called ramified
rectilinear polygons.

This paper considers pairs of optimization problems that are defined from a
single input and for which it is desired to find a good approximation to either
one of the problems. In many instances, it is possible to efficiently find an
approximation of this type that is better than known inapproximability lower
bounds for either of the two individual optimization problems forming the pair.
In particular, we find either a $(1+\epsilon)$-approximation to $(1,2)$-TSP or
a $1/\epsilon$-approximation to maximum independent set, from a given graph, in
linear time.