Combinatorial Problems in Graph Drawing and Knowledge Representation

We begin by establishing the strong Hanani-Tutte Theorem on the projective plane. Namely we show that if a graph can be drawn in the projective plane so that every two non-adjacent edges cross an even number of times, then the graph can be embedded in the projective plane. Secondly, we consider the property that in a random definite Horn formula of size-3 clauses over n variables, where every such clause is included with probability p, there is a pair of variables for which forward chaining produces all other variables. We show that with high probability the property does not hold for p<1/(11 n\ln n), and does hold for p>(5\ln\ln n)/(n\ln n). Thirdly, we study two problems in Horn formula minimization. We briefly consider Steiner minimization, a MAX-SNP-hard problem: we update an existing approximation algorithm to show that Steiner minimization can be efficiently approximated within a factor of O(n/log n). Finally we define and study hydra formulas and hydra numbers. The hydra number of a graph G=(V,E) is the minimal number of hyperarcs with body (u,v) and head w, such that, for every pair (u,v), the set of vertices reachable (via forward chaining) in H from {u,v} is the entire vertex set V if (u,v) is in E, and it is {u,v} otherwise. We give various bounds for the hydra number. Most notably, we show that the hydra number of a graph can be upper bounded by the number of edges plus the path cover number of the line graph of a spanning subgraph (sharp for some graphs); we construct graphs with hydra number equal to the number of edges, but having arbitrarily large path cover number; we give a lower bound for the hydra number of trees based on the number of neighbors of leafs (sharp for some families of trees). We also discuss a related optimization problem.