The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that does not contain a fixed graph as a minor has crossing number O(Dn), where G has n vertices and maximum degree D. This dependence on n and D is best possible.

This is joint work with Ken-ichi Kawarabayashi, Bojan Mohar and David R. Wood.

We examine theoretical bounds on the locality of routing. A local routing algorithm A at a network node v receives a packet P and selects one of its neighbours to which to forward P using only local information. Specifically, in addition to knowing the node for which P is destined, algorithm A may also know the node from which P originated, the neighbour from which node v received P, and the graph corresponding to all nodes within k hops of node v. Our objective is to determine which of these parameters are necessary and/or sufficient to permit local routing as k varies, where the network is modelled by an undirected graph. In particular, we establish tight bounds on k for the feasibility of deterministic k-local routing for various combinations of these parameters. Although motivated by applications in networks, our results involve combinatorial and graph-theoretic arguments.

This is joint work with Prosenjit Bose and Paz Carmi.

A standard approach to approximating NP-hard problems is to formulate the problem as a 0/1 integer program and then relax the integrality condition to get a linear program relaxation which can be solved efficiently. In order to remedy the discrepancy between integral and fractional solutions, several procedures were developed in order to obtain tightenings of relaxations in a systematic manner. These are normally referred to as Lift and Project systems and include the Lovász-Schrijver system, Sherali-Adams system, and Lasserre system.

Lift and Project systems have attracted much attention because of both their potential and their limitations. On one hand, some of the systems are at least as strong as many celebrated algorithms (e.g. for Vertex-Cover, Max-Cut, and Sparsest-Cut) or can even yield polynomial-time approximation-schemes on special instances. On the other hand, proving that these systems fail to behave well in the worst case, rules out a very promising family of algorithms for attacking NP-hard problems.

In this talk we will present the Lovász-Schrijver, Sherali-Adams, and Lasserre systems in a unified framework. We will discuss their algorithmic potential and limitations based on recent results. We will also discuss the long and active series of unconditional negative results that aim to match inapproximability lower bounds based on the conjecture that P ¹ NP.

A strong tradition exists of using finite state automata to give finite descriptions of infinite structures. A more recent perspective explores the use of automata as succinct representations of finite objects. In either case, a wide class of queries about objects represented via automata can be decided efficiently. In particular, we will present work on graph questions, including connectivity, and discuss the isomorphism problem.

This is joint work with Khoussainov and Liu, and with Liu.

We study the feasibility and time of communication in random geometric radio networks, where nodes fail randomly with positive correlation. We consider a set of radio stations with the same communication range, distributed in a random uniform way on a unit square region. In order to capture fault dependencies, we introduce the ranged spot model in which damaging events, called spots, occur randomly and independently on the region, causing faults in all nodes located within distance s from them. Node faults within distance 2s become dependent in this model and are positively correlated. We investigate the impact of the spot arrival rate on the feasibility and the time of communication in the fault-free part of the network. We provide an algorithm which broadcasts correctly with probability 1-e in faulty random geometric radio networks of diameter D in time O(D+log1/e).