Delne risbe polnih grafov

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
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2014
• PID: 20.500.12556/RUL-29436
• Publication date in RUL: 05.09.2014

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