20.500.12556/RUL-29436 Delne risbe polnih grafov diplomsko delo Partial edge drawings of complete graphs Delna risba grafa je risba, kjer povezave grafa predstavimo z daljicami, pri čemer središčnih polovic daljic ne narišemo. Dodatno zahtevamo, da ni križišč med tako narisanimi povezavami. Trenutno najboljša ocena trdi, da ne obstaja delna risba polnega grafa na 241 ali več točkah. V delu to oceno izboljšamo za faktor več kot dva. Pokažemo, da ni možno narisati delne risbe polnega grafa na 102 ali več točkah. Glavni ideji sta dve. Po eni strani uporabljamo drugačno delitev ravnine, na kateri ležijo točke grafa. Namesto koordinatne delitve uporabljamo območja vzdolž poltrakov iz vnaprej izbranih točk risbe. Dobimo delitev, ki ima podobno geometrijo kot delna risba, vendar pa je odvisna od medsebojne lege vnaprej izbranih robnih točk. Po drugi strani pa celotno risbo grafa analiziramo glede na lokacijo treh, deloma celo štirih, točk risbe in ne le dveh kot v prejšnjih ocenah. Partial edge drawing of a graph is a rectilinear drawing in which a middle portion of an edge is removed from the drawing. In addition, we require that the drawing is without edge crossings. Currently, the best estimate claims that there is no partial edge drawing of the complete graph on 241 or more points. In this work we improve the estimate by a factor of more than two. We show that it is not possible to draw a partial edge drawing of the complete graph on 102 or more points. The main ideas are two. On the one hand, we use a different division of the plane on which the points of the graph are located. Instead of coordinate division of the plane, we use the areas along the rays from pre-selected points of the drawing. On the other hand, we analyze the whole drawing of the graph by the location of three, sometimes even four, points of the drawing and not only two points as in the previous estimates. delne risbe teorija grafov ravninski grafi analitična geometrija računalništvo računalništvo in informatika računalništvo in matematika univerzitetni študij interdisciplinarni študij diplomske naloge partial edge drawings graph theory planar graphs analytic geometry computer science computer and information science computer science and mathematics interdisciplinary studies diploma true false false [M. Lalović] Slovenski jezik Angleški jezik Diplomsko delo/naloga 2014-09-05 14:25:03 2014-09-05 14:25:03 2024-08-12 16:10:42 0000-00-00 00:00:00 2014 0 0 74 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 14701 10785108 63090010-20140828044804-Marko_Lalovic_diploma.pdf 63090010-20140828044804-Marko_Lalovic_diploma.pdf 1 6A9819E8E146A2F0DB79464BC5408DAB f5c2e06f4c6b142affc50b28763c59d76a9c7225e02e9d5b611fb0ebd775e85f 2f35efd8-a1a8-11eb-a523-00155dcfd717 20.500.12556/rul/524c3675-6622-4cbc-9c8f-48c682992587 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=29432 Fakulteta za računalništvo in informatiko 0 0 0