Název: Dotykové grafy kružnic a Möbiovy transformace
Překlad názvu: Circle packing and Möbius transformations
Autoři: Porvichová, Janka ; Zeman, Peter (vedoucí práce) ; Kratochvíl, Jan (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2019
Jazyk: slo
Abstrakt: [eng] [cze]
A graph can be represented by various geometric representations. In this work we focus on the circle packing representation. We state various concepts impor- tant for proving results regarding this kind of representation. We introduce a known proof of existence of a circle packing for planar graphs and a proof of existence of a primal-dual circle packing for 3-connected graphs. Next, we focus on computational complexity of extending the representation for a given partial circle packing. We examine the proof of the theorem stating that deciding whet- her such an extension exists is an NP-hard problem. We introduce our theoretical algorithm for extension construction based on real RAM machine. 1 Graf lze reprezentovat různými geometrickými reprezentacemi. V této práci se věnujeme reprezentaci grafů pomocí circle packingu (dotykových kružnic). Roze- bereme důležité koncepty potřebné pro dokázání klíčových výsledků ohledně této reprezentace. Představíme konkrétní známý důkaz existence circle packingu pro rovinné grafy a existence primal-dual circle packingu pro 3-souvislé grafy. Dále se budeme zabývat složitostí problému rozšíření reprezentace při zadaném čás- tečném circle packingu. Rozebereme důkaz věty, která říká, že rozhodnout, zda lze nalézt takové rozšíření, je NP-těžký problém. Představíme vlastní teoretický algoritmus pro konstrukci rozšíření založený na real RAM stroji. 1
Klíčová slova: circle packing; geometrické reprezentácie grafov; Möbiove transformácie; primal-dual circle packing; zložitosť; circle packing; computational complexity; geometric representation of graphs; Möbius transformations; primal-dual circle packing

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/105369

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-393708


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce