We show that there exists an adjacency labelling scheme for planar graphs where each
vertex of an n-vertex planar graph G is assigned a (1+ o (1)) log 2 n-bit label and the labels …

Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a
countable planar graph that contains every countable planar graph as a subgraph). J\'anos …

In this article, we show that there exists a graph G with O (n) nodes such that any forest of n
nodes is an induced subgraph of G. Furthermore, for constant arboricity k, the result implies …

We show that for any constant Δ≥ 2, there exists a graph Γ with O (n Δ/2) vertices which
contains every n-vertex graph with maximum degree Δ as an induced subgraph. For odd Δ …

This dissertation introduces the MCSPLIT family of algorithms for two closely-related NP-
hard problems that involve finding a large induced subgraph contained by each of two input …

The Internet is a large geographically dispersed network, and information about its structure
is needed by all its participants. Decentralizing the structural information is a key part in the …

In this paper we look at the problem of adjacency labeling of graphs. Given a family of
undirected graphs the problem is to determine an encoding-decoding scheme for each …

A graph U is an induced universal graph for a family F of graphs if every graph in F is a
vertex-induced subgraph of U. Recently, for the family of all undirected graphs on n vertices …

We study several problems about sublinear algorithms, presented in two parts. Part I:
Property testing and learning. There are two main goals of research in property testing and …

In this paper we look at the problem of adjacency labeling of graphs. Given a family of
undirected graphs the problem is to determine an encoding-decoding scheme for each …