<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>34</id>
    <completedYear>2004</completedYear>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2004-07-15</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>2004-07-09</thesisDateAccepted>
    <title language="eng">Circle Planarity of Level Graphs</title>
    <title language="deu">Kreisplanarität von Level-Graphen</title>
    <abstract language="eng">In this dissertation we generalise the notion of level planar graphs in two directions: track planarity and radial planarity. Our main results are linear time algorithms both for the planarity test and for the computation of an embedding, and thus a drawing. Our algorithms use and generalise PQ-trees, which are a data structure for efficient planarity tests.</abstract>
    <abstract language="deu">In dieser Arbeit wird der Begriff Level-Planarität von Graphen auf zwei Arten erweitert: Spur-Planarität und radiale Level-Planarität. Die Hauptergebnisse sind Linearzeitalgorithmen zum Testen dieser Arten von Planarität und zur Erstellung einer entsprechenden Einbettung und somit einer Zeichnung. Die Algorithmen verwenden und generalisieren PQ-Bäume, eine bei effizienten Planaritätstests verwendete Datenstruktur.</abstract>
    <identifier type="urn">urn:nbn:de:bvb:739-opus-385</identifier>
    <identifier type="opus3-id">38</identifier>
    <licence>Standardbedingung laut Einverständniserklärung</licence>
    <author>Christian Bachmaier</author>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Graphentheorie</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Graphenklasse</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Graphenzeichnen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Graph</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>radial level panarity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>track planarity</value>
    </subject>
    <collection role="ddc" number="004">Datenverarbeitung; Informatik</collection>
    <collection role="open_access" number="">open_access</collection>
    <collection role="institutes" number="">Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik</collection>
    <thesisPublisher>Universität Passau</thesisPublisher>
    <thesisGrantor>Universität Passau</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-uni-passau/files/34/CirclePlanarityOfLevelGraphs.pdf</file>
  </doc>
</export-example>
