Original title: Algoritmus pro dokreslování rovinných nakreslení
Translated title: An algorithm for extending partial planar drawings
Authors: Hora, Martin ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Document type: Bachelor's theses
Year: 2017
Language: cze
Abstract: [cze] [eng]
Tento text se zabývá problémem dokreslování rovinných grafů. Vstupem pro- blému je graf G, jehož podgraf je již nakreslen do roviny. Cílem je pak rozhodnout, zda lze do roviny dokreslit i zbytek grafu G, a získat tak rovinné nakreslení G. Již bylo dokázáno, že lze dokreslitelnost rovinných grafů řešit v lineárním čase. Avšak všechny známé lineární algoritmy jsou poměrně komplikované, a pravděpodobně proto nebyla zveřejněna žádná jejich implementace. V práci představíme nový jednodušší lineární algoritmus řešící dokreslitelnost a dokážeme jeho korektnost. Dále pak k této práci přiložíme implementaci tohoto algoritmu v programovacím jazyce C++. 1 This thesis studies the problem of partially embedded planarity. The input of the problem is a graph G and a planar drawing of a subgraph of G. The goal is to decide whether the drawing of the subgraph can be extended to a planar drawing of the entire graph G. It has already been proved that the partially embedded planarity problem can be solved in linear time. However, all known linear algorithms are relatively complicated. This is probably the reason that no implementation has yet been published. We will introduce a new, simpler linear algorithm that solves the problem and we will prove its correctness. Next, we will enclose an implementation of this algorithm in the C++ programming language. 1
Keywords: algorithm; partially embedded graphs; planarity; algoritmus; rovinnost; částečně vnořené grafy

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/86227

Permalink: http://www.nusl.cz/ntk/nusl-357507


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses