dc.contributor.advisor Turan, Gyorgy en_US dc.contributor.author Stasi, Despina en_US dc.date.accessioned 2012-12-13T21:34:42Z dc.date.available 2012-12-13T21:34:42Z dc.date.created 2012-08 en_US dc.date.issued 2012-12-13 dc.date.submitted 2012-08 en_US dc.identifier.uri http://hdl.handle.net/10027/9492 dc.description.abstract 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. en_US dc.language.iso en en_US dc.rights Copyright 2012 Despina Stasi en dc.subject Hydra formulas en_US dc.subject hydra number en_US dc.subject Hanani-Tutte Theorem en_US dc.subject Horn formulas en_US dc.subject propagation connectivity. en_US dc.title Combinatorial Problems in Graph Drawing and Knowledge Representation en_US thesis.degree.department Mathematics, Statistics and Computer Science en_US thesis.degree.discipline Mathematics en_US thesis.degree.grantor University of Illinois at Chicago en_US thesis.degree.level Doctoral en_US thesis.degree.name PhD, Doctor of Philosophy en_US dc.type.genre thesis en_US dc.contributor.committeeMember Sloan, Robert H. en_US dc.contributor.committeeMember Friedland, Shmuel en_US dc.contributor.committeeMember Mubayi, Dhruv en_US dc.contributor.committeeMember Schaefer, Marcus en_US dc.type.material text en_US
﻿