Delne risbe polnih grafov

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2014
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[M. Lalović]
UDK:	004(043.2)
COBISS:	10785108
Št. ogledov:	78
Št. prenosov:	9
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Partial edge drawings of complete graphs
Sekundarni povzetek:	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.
Sekundarne ključne besede:	partial edge drawings;graph theory;planar graphs;analytic geometry;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Komentar na gradivo:	Univerza v Ljubljani, Fak. za računalništvo in informatiko
Strani:	74 str.
ID:	8739343