Delne risbe polnih grafov : diplomsko delo

LALOVIĆ, MARKO (author), Fijavž, Gašper (mentor)

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.

• Language: Slovenian
• Keywords: 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
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Publisher: [M. Lalović]
• Year: 2014
• Number of pages: 74 str.
• PID: 20.500.12556/RUL-29436
• COBISS.SI-ID: 10785108
• Publication date in RUL: 05.09.2014

Licences

• License: CC BY-SA 2.5 SI, Creative Commons Attribution-ShareAlike 2.5 Slovenia
• Link: https://creativecommons.org/licenses/by-sa/2.5/si/deed.en
• Description: You are free to reproduce and redistribute the material in any medium or format. You are free to remix, transform, and build upon the material for any purpose, even commercially. You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original. You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

Secondary language

• Language: English
• Title: Partial edge drawings of complete graphs

Abstract

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.

• Keywords: partial edge drawings, graph theory, planar graphs, analytic geometry, computer science, computer and information science, computer science and mathematics, interdisciplinary studies, diploma