@phdthesis{Matzeder2012, author = {Matzeder, Marco}, title = {Zeichnen von B{\"a}umen auf Gittern}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26923}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Das Zeichnen von Graphen besch{\"a}ftigt sich mit der Frage, wie die durch einen Graphen repr{\"a}sentierten Informationen f{\"u}r einen Betrachter {\"u}bersichtlich und verst{\"a}ndlich dargestellt werden k{\"o}nnen. Die Graphklasse der B{\"a}ume dient insbesondere zur Repr{\"a}sentation von hierarchischen Strukturen. Neben den hierarchisch und radial darstellenden Verfahren werden B{\"a}ume auch auf dem orthogonalen Gitter gezeichnet, in welchem die Knoten auf ganzzahligen Koordinaten liegen und die Kanten entlang der horizontalen und vertikalen Gitterlinien verlaufen. Gew{\"u}nscht wird eine gute Lesbarkeit der Zeichnungen und deren effiziente Berechnung. F{\"u}r die formale Bewertung der Lesbarkeit existieren speziell f{\"u}r das Zeichnen von B{\"a}umen definierte {\"A}sthetikkriterien, wie eine ebenenweise Darstellung, die Ordnungserhaltung und Kriterien zur Darstellung von Subgraphisomorphien und Symmetrien. Die vorliegende Arbeit befasst sich mit einer bislang wenig studierten Erweiterung des orthogonalen Gitters auf das hexagonale und oktagonale Gitter durch das Hinzunehmen von einer bzw. beider diagonalen Gitterrichtungen, und der Problemstellung, wie B{\"a}ume darauf gezeichnet werden. Dadurch k{\"o}nnen auch B{\"a}ume mit einem h{\"o}heren Grad gezeichnet werden als auf dem orthogonalen Gitter. Die Einschr{\"a}nkung, dass nur B{\"a}ume gezeichnet werden k{\"o}nnen, deren Grad kleiner ist als die Anzahl der Gitterrichtungen des verwendeten Gitters, besteht jedoch weiterhin. Als {\"A}sthetikkriterien werden die lokale Uniformit{\"a}t, die die L{\"a}nge der ausgehenden Kanten eines Knotens festlegt, und Pattern, die deren Richtungen festlegen, eingef{\"u}hrt. Gegen{\"u}ber dem bekannten linearen Fl{\"a}chenverbrauch von geradlinigen Zeichnungen von vollst{\"a}ndigen Bin{\"a}rb{\"a}umen auf dem orthogonalen Gitter, werden f{\"u}r Zeichnungen von vollst{\"a}ndigen d-n{\"a}ren B{\"a}umen mit d > 2 nicht-lineare untere Schranken f{\"u}r die ben{\"o}tigte Fl{\"a}che auf dem hexagonalen und dem oktagonalen Gitter gezeigt. Insgesamt werden f{\"u}r vollst{\"a}ndige und beliebige, geordnete und ungeordnete B{\"a}ume obere und untere Fl{\"a}chenschranken f{\"u}r Zeichnungen auf dem hexagonalen und oktagonalen Gitter pr{\"a}sentiert. Dabei zeigt sich, dass bei nicht-ordnungserhaltenden Zeichnungen zwar mehr als lineare, aber deutlich weniger als quadratische Fl{\"a}che ben{\"o}tigt wird. Im Gegensatz dazu gibt es geordnete B{\"a}ume, deren ordnungserhaltende Zeichnungen exponentielle Fl{\"a}che ben{\"o}tigen. Des Weiteren wird die Ermittlung der minimalen Zeichenfl{\"a}che f{\"u}r geordnete d-n{\"a}re B{\"a}ume ebenso als NP-vollst{\"a}ndig bewiesen, wie das Zeichnen von ungeordneten d-n{\"a}ren B{\"a}umen mit einheitlichen Kantenl{\"a}ngen. Schließlich werden zwei Linearzeitalgorithmen vorgestellt, die geordnete d-n{\"a}re B{\"a}ume unter Einhaltung der genannten {\"A}sthetikkriterien zeichnen.}, subject = {Baum }, language = {de} }