If a graph can be drawn on the torus so that every two independent edges cross an even number of times, then the graph can be embedded on the torus.

We consider the problem of transmitting a message from a sender s to a receiver r through a network in which edges may fail and cannot recover. In the transmission protocols we consider, we require that r may not be “flooded” by infinitely many copies of this message. A routing protocol is k-robust if it ensures that a message sent by s will be received by r when at most k edges fail, unless no $s,r$-path remains. Graphs which have a k-robust protocol for all k were characterized in [F. E. Fich, A. Kündgen, M. J. Pelsmajer, and R. Ramamurthi, SIAM J. Discrete Math., 19 (2005), pp. 815–847]. For any other graph, its robustness is the maximum k for which it has a k-robust protocol. We provide general lower bounds for robustness by improving a natural protocol obtained from Menger's theorem. We determine robustness for several examples, such as complete graphs, grids, and hypercubes.

We show that $\mathrm{cr}(G)\leq({2\,\mathrm{iocr}(G)\atop2})$, settling an open problem of Pach and Tóth [Geombinatorics, 9 (2000), pp. 194–207]. Moreover, $\mathrm{iocr}(G)=\mathrm{cr}(G)$ if $\mathrm{iocr}(G)\leq2$.

If a graph can be drawn in the projective plane so that every two nonadjacent edges cross an even number of times, then the graph can be embedded in the projective plane.

We study extremal questions on induced matchings in several natural graph classes. We argue that these questions should be asked for twinless graphs, that is graphs not containing two vertices with the same neighborhood. We show that planar twinless graphs always contain an induced matching of size at least $n/40$ while there are planar twinless graphs that do not contain an induced matching of size $(n+10)/27$. We derive similar results for outerplanar graphs and graphs of bounded genus. These extremal results can be applied to the area of parameterized computation. For example, we show that the induced matching problem on planar graphs has a kernel of size at most $40k$ that is computable in linear time; this significantly improves the results of Moser and Sikdar (2007). We also show that we can decide in time $O(91^k + n)$ whether a planar graph contains an induced matching of size at least $k$.

End-to-end communication considers the problem of sending messages from a sender s to a receiver r through an asynchronous, unreliable network, such as the Internet. We consider the problem of transmitting a single message from s to r through a network in which edges may fail and cannot recover. We assume that some $sr$-path survives, but we do not know which path it is. We are concerned with protocols that do not store information at intermediate nodes and that ensure that a message sent by s will be recieved by r (no matter which edges fail) without generating an infinite number of messages. We explicitly characterize the family of networks for which there is such a protocol using headerless packets. This characterization is given in terms of forbidden rooted minors, which leads to a linear time recognition algorithm for this family of networks. We obtain a similar characterization for the family of networks in which a message can be broadcast from a single vertex s to all other vertices. Finally, we show that there is a forbidden rooted minor characterization for the more general case when a header (containing routing information) of constant length is attached to the message, and we discuss the algorithmic consequences of this characterization.