Show simple item record

dc.contributor.advisorTuran, Gyorgyen_US
dc.contributor.authorStasi, Despinaen_US
dc.date.accessioned2012-12-13T21:34:42Z
dc.date.available2012-12-13T21:34:42Z
dc.date.created2012-08en_US
dc.date.issued2012-12-13
dc.date.submitted2012-08en_US
dc.identifier.urihttp://hdl.handle.net/10027/9492
dc.description.abstractWe 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.isoenen_US
dc.rightsCopyright 2012 Despina Stasien
dc.subjectHydra formulasen_US
dc.subjecthydra numberen_US
dc.subjectHanani-Tutte Theoremen_US
dc.subjectHorn formulasen_US
dc.subjectpropagation connectivity.en_US
dc.titleCombinatorial Problems in Graph Drawing and Knowledge Representationen_US
thesis.degree.departmentMathematics, Statistics and Computer Scienceen_US
thesis.degree.disciplineMathematicsen_US
thesis.degree.grantorUniversity of Illinois at Chicagoen_US
thesis.degree.levelDoctoralen_US
thesis.degree.namePhD, Doctor of Philosophyen_US
dc.type.genrethesisen_US
dc.contributor.committeeMemberSloan, Robert H.en_US
dc.contributor.committeeMemberFriedland, Shmuelen_US
dc.contributor.committeeMemberMubayi, Dhruven_US
dc.contributor.committeeMemberSchaefer, Marcusen_US
dc.type.materialtexten_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record