Implementation und Animation des Links-Rechts-Planaritätstests

Lade...
Vorschaubild
Dateien
bachelor_kaiser-d.pdf
bachelor_kaiser-d.pdfGröße: 1.1 MBDownloads: 278
Datum
2009
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Bachelorarbeit
Publikationsstatus
unikn.publication.listelement.citation.prefix.version.undefined
Zusammenfassung

Diese Bachelorarbeit beschäftigt sich mit dem Links-Rechts-Planaritätstest, einem noch relativ unbekannten Algorithmus, welcher in linearer Zeit einen Planaritätstest durchführt und die planare Einbettung des getesteten Graphen bestimmen kann. Dieser Algorithmus läuft sehr schnell und ist im Vergleich zu anderen linearen Planaritätstestalgorithmen leicht verständlich. Vor allem die Einbettung ist sehr einfach und kommt mit den aus dem Test verwendeten Datenstrukturen aus.

Neben einer Einführung, welche die Grundlagen erklärt und der Herleitung des Links-Rechts-Planaritätskriteriums, welchem der Links-Rechts-Planaritäts-test zu Grunde liegt, wird hauptsächlich auf den Algorithmus selbst, eine eigene Implementierung mit C++ unter Verwendung der Algorithmenbibliothek LEDA und auf ein selbst geschriebenes Animationsprogramm eingegangen.

Dieses Animationsprogramm ermöglicht das schrittweise Durchgehen der 2. Phase des Algorithmus, während die einzelnen Schritte visualisiert werden.
Eine Erklärung der Implementierung dieses Programms ist ebenfalls Teil dieser Arbeit. Die Ausführungen zum Planaritätskriterium, zum Algorithmus und die Implementierung des Algorithmus basieren auf [2].

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Planaritätstest
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690KAISER, Daniel, 2009. Implementation und Animation des Links-Rechts-Planaritätstests [Bachelor thesis]
BibTex
@mastersthesis{Kaiser2009Imple-18735,
  year={2009},
  title={Implementation und Animation des Links-Rechts-Planaritätstests},
  author={Kaiser, Daniel}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/18735">
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/18735/2/bachelor_kaiser-d.pdf"/>
    <dc:creator>Kaiser, Daniel</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-03-05T06:43:57Z</dc:date>
    <dcterms:abstract xml:lang="deu">Diese Bachelorarbeit beschäftigt sich mit dem Links-Rechts-Planaritätstest, einem noch relativ unbekannten Algorithmus, welcher in linearer Zeit einen Planaritätstest durchführt und die planare Einbettung des getesteten Graphen bestimmen kann. Dieser Algorithmus läuft sehr schnell und ist im Vergleich zu anderen linearen Planaritätstestalgorithmen leicht verständlich. Vor allem die Einbettung ist sehr einfach und kommt mit den aus dem Test verwendeten Datenstrukturen aus.&lt;br /&gt;&lt;br /&gt;Neben einer Einführung, welche die Grundlagen erklärt und der Herleitung des Links-Rechts-Planaritätskriteriums, welchem der Links-Rechts-Planaritäts-test zu Grunde liegt, wird hauptsächlich auf den Algorithmus selbst, eine eigene Implementierung mit C++ unter Verwendung der Algorithmenbibliothek LEDA und auf ein selbst geschriebenes Animationsprogramm eingegangen.&lt;br /&gt;&lt;br /&gt;Dieses Animationsprogramm ermöglicht das schrittweise Durchgehen der 2. Phase des Algorithmus, während die einzelnen Schritte visualisiert werden.&lt;br /&gt;Eine Erklärung der Implementierung dieses Programms ist ebenfalls Teil dieser Arbeit. Die Ausführungen zum Planaritätskriterium, zum Algorithmus und die Implementierung des Algorithmus basieren auf [2].</dcterms:abstract>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:title>Implementation und Animation des Links-Rechts-Planaritätstests</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/18735/2/bachelor_kaiser-d.pdf"/>
    <dc:contributor>Kaiser, Daniel</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:issued>2009</dcterms:issued>
    <dc:language>deu</dc:language>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/18735"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-03-05T06:43:57Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet