We establish a Hanani--Tutte style characterization for hierarchical partial planarity and initiate the study of partitioned partial planarity.

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 propose an algorithm for c-planarity testing which is correct and efficient, but not, in general, complete, i.e., there are input instances on which the algorithm declines to give an answer. At the core of this algorithm is an algebraic criterion based on work by the third author [20] with the following properties: (1) The criterion is a necessary condition for c-planarity, (2) for special graph classes, including c-connected graphs, the condition is also sufficient, and (3) the criterion can be tested efficiently in polynomial time. The algebraic criterion is not sufficient in general; however, we can extend it to a (still efficient) algorithm that verifies the answer of the criterion by building a c-planar embedding of the input graph. Our practical experiments show that this algorithm works well in practice. This is the first time that all instances from state-of-the-art benchmark sets for testing c-planarity are solved correctly. The algorithm is conceptually very simple and easy to implement.

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$.

We investigate a new type of graph inequality (in the tradition of Cvetkovic and Simic [Contributions to Graph Theory and Its Applications, Technische Hochschule Ilmenau, Ilmenau, Germany, 1977, pp. 40--56] and Capobianco [Ann. New York Acad. Sci., 319 (1979), pp. 114--118]) which is based on the subgraph relation and which allows as terms fixed graphs, graph variables with specified vertices, and the operation of identifying vertices. We present a simple graph inequality that does not have a solution and show that the solvability of inequalities with only one graph variable and one specified vertex can be decided (in nondeterministic exponential time). The solvability of graph inequalities over directed graphs, however, turns out to be undecidable.

A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. We show that string graphs can be recognized in NP. The recognition problem was not known to be decidable until very recently, when two independent papers established exponential upper bounds on the number of intersections needed to realize a string graph [18, 20]. These results implied that the recognition problem lies in NEXP. In the present paper we improve this by showing that the recognition problem for string graphs is in NP, and therefore NP-complete, since Kratochvíl [12] showed that the recognition problem is NP-hard. The result has consequences for the computational complexity of problems in graph drawing, and topological inference.

We show that string graphs can be recognized in nondeterministic exponential time by giving an exponential upper bound on the number of intersections for a drawing realizing the string graph in the plane. This upper bound confirms a conjecture by Kratochv\'{\i}l and Matou\v{s}ek~\cite{KM91} and settles the long-standing open problem of the decidability of string graph recognition (Sinden~\cite{S66}, Graham~\cite{G76}). Finally we show how to apply the result to solve another old open problem: deciding the existence of Euler diagrams, a central problem of topological inference (Grigni, Papadias, Papadimitriou~\cite{GPP95}).

N. Littlestone (1998) introduced the optimal mistake-bound learning model to learning theory. In this model the difficulty of learning a concept from a concept class is measured by the K-dimension of the concept class, which is a purely combinatorial notion. This is similar to the situation in PAC-learning, where the difficulty of learning can be measured by the Vapnik-Cervonenkis dimension. We show that determining the K-dimension of a concept class is a PSPACE-complete problem where the concept class is given as a circuit. This also implies that any optimal learner (making the least number of mistakes) that works on all concept classes over finite universes has to be PSPACE-hard.

Summary form only given, as follows. In the Ramsey theory of graphs F/spl rarr/(G, H) means that for every way of coloring the edges of F red and blue F will contain either a red G or a blue H as a subgraph. The problem ARROWING of deciding whether F/spl rarr/(G, H) lies in /spl Pi//sub 2//sup P/=coNP/sup NP/ and it was shown to be coNP-hard by S.A. Burr (1990). We prove that ARROWING is actually /spl Pi//sub 2//sup P/-complete, simultaneously settling a conjecture of Burr and providing a natural example of a problem complete for a higher level of the polynomial hierarchy. We also consider several specific variants of ARROWING, where G and H are restricted to particular families of graphs. We have a general completeness result for this case under the assumption that certain graphs are constructible in polynomial time. Furthermore we show that STRONG ARROWING, the version of ARROWING for induced subgraphs, is /spl Pi//sub 2//sup P/-complete.

In the Ramsey theory ofgraphs F + (G, H) means that for every way of coloring the edges of F red and blue F will contain either a red G or a blue H.The problem ARROWING of deciding whether F + (G, H) lies in II; = coNPNP and it was shown to be coNP hard by Burr [5].We prove that ARROWING is actually II;-complete, simultaneously settling a conjecture of Burr and providing a natural example of a problem complete for a higher level of the polynomial hierarchy.We also show that STRONG ARROWING, the version for induced subgraphs, is rI;-complete.

Assuming that the polynomial hierarchy (PH) does not collapse, we show the existence of ascending sequences of ptime Turing degrees of length /spl omega//sub 1//sup CK/ all of which are in PSPACE and uniformly hard for PH, such that successors are NP-jumps of their predecessors. This is analogous to the hyperarithmetic hierarchy which is defined similarly but with the (recursive) Turing degrees. The lack of uniform least upper bounds for ascending sequences of ptime degrees causes (the limit levels of) our hyper-polynomial hierarchy to be inherently non-canonical. This problem is investigated in depth, and various possible structures for hyper-polynomial hierarchies are explicated, as are properties of the NP-jump operator on the languages which are in PSPACE but not in PH.

Linial et al. (1988) raised the question of how difficult the computation of the Vapnik-Cervonenkis dimension of a concept class over a finite universe is. Papadimitriou and Yannakakis (1993) obtained a first answer using matrix representations of concept classes. However, this approach does not capture classes having exponential size, like monomials, which are encountered in learning theory. We choose a more natural representation, which leads us to redefine the VC DIMENSION problem. We establish that VC DIMENSION is /spl Sigma//sub 3//sup p/-complete, thereby giving a rare natural example of a /spl Sigma//sub 3//sup p/-complete problem.