@phdthesis{Reislhuber2017, author = {Reislhuber, Josef}, title = {Optical Graph Recognition}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5159}, school = {Universit{\"a}t Passau}, pages = {270 Seiten}, year = {2017}, abstract = {Graphs are an important model for the representation of structural information between objects. One identifies objects and nodes as well as a binary relation between objects and edges. Graphs have many uses, e. g., in social sciences, life sciences and engineering. There are two primary representations: abstract and visual. The abstract representation is well suited for processing graphs by computers and is given by an adjacency list, an adjacency matrix or any abstract data structure. A visual representation is used by human users who prefer a picture. Common terms are diagram, scheme, plan, or network. The objective of Graph Drawing is to transform a graph into a visual representation called the drawing of a graph. The goal is a "nice" drawing. In this thesis we introduce Optical Graph Recognition. Optical Graph Recognition (OGR) reverses Graph Drawing and transforms a digital image of a graph into an abstract representation. Our approach consists of four phases: Preprocessing where we determine which pixels of an image are part of the graph, Segmentation where we recognize the nodes, Topology Recognition where we detect the edges and Postprocessing where we enrich the recognized graph with additional information. We apply established digital image processing methods and make use of the special property that the image contains nodes that are connected by edges. We have focused on developing algorithms that need as little parameters as possible or to automatically calibrate the parameters. Most false recognition results are caused by crossing edges as this makes tracing the edges difficult and can lead to other recognition errors. We have evaluated hand-drawn and computer-drawn graphs. Our algorithms have a very high recognition rate for computer-drawn graphs, e. g., from a set of 100000 computer-drawn graphs over 90\% were correctly recognized. Most false recognition results where observed for hand-drawn graphs as they can include drawing errors and inaccuracies. For universal usability we have implemented a prototype called OGRup for mobile devices like smartphones or tablet computers. With our software it is possible to directly take a picture of a graph via a built in camera, recognize the graph, and then use the result for further processing. Furthermore, in order to gain more insight into the way a person draws a graph by hand, we have conducted a field study.}, subject = {Bildverarbeitung}, language = {en} } @phdthesis{Brunner2010, author = {Brunner, Wolfgang}, title = {Cyclic Level Drawings of Directed Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-17962}, school = {Universit{\"a}t Passau}, year = {2010}, abstract = {The Sugiyama framework proposed in the seminal paper of 1981 is one of the most important algorithms in graph drawing and is widely used for visualizing directed graphs. In its common version, it draws graphs hierarchically and, hence, maps the topological direction to a geometric direction. However, such a hierarchical layout is not possible if the graph contains cycles, which have to be destroyed in a preceding step. In certain application and problem settings, e.g., bio sciences or periodic scheduling problems, it is important that the cyclic structure of the input graph is preserved and clearly visible in drawings. Sugiyama et al. also suggested apart from the nowadays standard horizontal algorithm a cyclic version they called recurrent hierarchies. However, this cyclic drawing style has not received much attention since. In this thesis we consider such cyclic drawings and investigate the Sugiyama framework for this new scenario. As our goal is to visualize cycles directly, the first phase of the Sugiyama framework, which is concerned with removing such cycles, can be neglected. The cyclic structure of the graph leads to new problems in the remaining phases, however, for which solutions are proposed in this thesis. The aim is a complete adaption of the Sugiyama framework for cyclic drawings. To complement our adaption of the Sugiyama framework, we also treat the problem of cyclic level planarity and present a linear time cyclic level planarity testing and embedding algorithm for strongly connected graphs.}, subject = {Graphenzeichnen}, language = {en} } @phdthesis{Bachl2003, author = {Bachl, Walter}, title = {Interaktives orthogonales Zeichnen von planaren Graphen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-392}, school = {Universit{\"a}t Passau}, year = {2003}, abstract = {Die Arbeit besch{\"a}ftigt sich mit dem automatischen Zeichnen von Graphen. Hier wird ein interaktiver Ansatz untersucht, bei dem der Graph mit einer Menge von Operationen Schritt f{\"u}r Schritt aufgebaut wird. Der Zielgraph und die Einf{\"u}gereihenfolge sind dabei nicht fest vorgegeben, sondern werden vom Benutzer bestimmt. In der Arbeit wird vor allem ein Szenario f{\"u}r zweifach zusammenh{\"a}ngende Graphen untersucht und ein f{\"u}r diese Zwecke passendes Zeichenmodell entwickelt. Dieser Ansatz wird dann um verschiedene Varianten erweitert. Außerdem wird gezeigt, dass das fl{\"a}chenminimale Zeichnen in dem neu entwickelten Zeichenmodell NP-vollst{\"a}ndig ist.}, subject = {Graphenzeichnen}, language = {de} } @phdthesis{Bachmaier2004, author = {Bachmaier, Christian}, title = {Circle Planarity of Level Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-385}, school = {Universit{\"a}t Passau}, year = {2004}, abstract = {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.}, subject = {Graphentheorie}, language = {en} } @phdthesis{Bachl2001, author = {Bachl, Sabine}, title = {Isomorphe Subgraphen und deren Anwendung beim Zeichnen von Graphen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-149}, school = {Universit{\"a}t Passau}, year = {2001}, abstract = {In der Arbeit wird der Begriff der Isomorphen Subgraphen definiert. Anschließend werden theoretische und praktische Ergebnisse bei der Erkennung Isomorpher Graphen er{\"o}rtert.}, subject = {Isomorpher Teilgraph}, language = {de} } @phdthesis{Raitner2005, author = {Raitner, Marcus}, title = {Efficient visual navigation of hierarchically structured graphs}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-658}, school = {Universit{\"a}t Passau}, year = {2005}, abstract = {Visual navigation of hierarchically structured graphs is a technique for interactively exploring large graphs that possess an additional hierarchical structure. This structure is expressed in form of a recursive clustering of the nodes: in call graphs of telephone networks, for instance, the nodes are identified with phone numbers; they are clustered recursively through the implicit structure of the numbers, e. g., nodes with the same area code belong to a cluster. In order to reduce the complexity and the size of the graph, only those subgraphs that are currently needed are shown in detail, while the others are collapsed, i. e., represented by meta nodes. In such a graph view the subgraphs in the areas of interest are expanded furthest, whereas those on the periphery are abstracted. As the areas of interest change over time, clusters in a view need to be expanded or contracted. First and foremost, there is need for an efficient data structure for this graph view maintenance problem. Depending on the admissible modifications of the graph and its hierarchical clustering, three variants have been discussed in the literature: in the static case, everything is fixed; in the dynamic graph variant, only edges of the graph can be inserted and deleted; finally, in the dynamic graph and tree variant the graph additionally is subject to node insertions and deletions and the clustering may change through splitting and merging of clusters. We introduce a new variant, dynamic leaves, which is based on the dynamic graph variant, but additionally allows insertion and deletion of graph nodes, i. e., leaves of the hierarchy. So far efficient data structures were known only for the static and the dynamic graph variant, i. e., neither the nodes of the graph nor the clustering could be modified. As this is unsatisfactory in an interactive editor for hierarchically structured graphs, we first generalize the approach of Buchsbaum et. al (Proc. 8th ESA, vol. 1879 of LNCS, pp. 120-131, 2000), in which graph view maintenance is formulated as a special case of range searching over tree cross products, to the new dynamic leaves variant. This generalization builds on a novel technique of superimposing a search tree over an ordered list maintenance structure. With an additional factor of roughly O(log n/log log n), this is the first data structure for the problem of graph view maintenance where the node set is dynamic. Visualizing the expanding and contracting appropriately is the second challenge. We propose a local update scheme for the algorithm of Sugiyama and Misue (IEEE Trans. on Systems, Man, and Cybernetics 21 (1991) 876- 892) for drawing compound digraphs. The layered drawings that it produces have many applications ranging from biochemical pathways to UML diagrams. Modifying the intermediate results of every step of the original algorithm locally, the update scheme is more efficient than re-applying the entire algorithm after expansion or contraction. As our experimental results on randomly generated graphs show, the average time for updating the drawing is around 50 \% of the time for redrawing for dense graphs and below 20 \% for sparse graphs. Also, the performance gain is not at the expense of quality as regards the area of the drawing, which increases only insignificantly, and the number of crossings, which is reduced. At the same time, the locality of the updates preserves the user 's mental map of the graph: nodes that are are not affected stay on the same level in the same relative order and expanded edges take the same course as the corresponding contracted edge; furthermore, expansion and contraction are visually inverse. Finally, our new data structure and the update scheme are combined into an interactive editor and viewer for compound (di-)graphs. A flexible and extensible software architecture is introduced that lays the ground for future research. It employs the well-known Model-View-Controller (MVC) paradigm to separate the abstract data from its presentation. As a consequence, the purely combinatorial parts, i. e., the compound (di-)graph and its views, are reusable without the editor front-end. A proof-of-concept implementation based on the proposed architecture shows its feasibility and suitability.}, subject = {Dynamische Datenstruktur}, language = {en} } @phdthesis{Forster2004, author = {Forster, Michael}, title = {Crossings in Clustered Level Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-481}, school = {Universit{\"a}t Passau}, year = {2004}, abstract = {Clustered graphs are an enhanced graph model with a recursive clustering of the vertices according to a given nesting relation. This prime technique for expressing coherence of certain parts of the graph is used in many applications, such as biochemical pathways and UML class diagrams. For directed clustered graphs usually level drawings are used, leading to clustered level graphs. In this thesis we analyze the interrelation of clusters and levels and their influence on edge crossings and cluster/edge crossings.}, subject = {Graphenzeichnen}, language = {en} } @phdthesis{Auer2014, author = {Auer, Christopher}, title = {Planar Graphs and their Duals on Cylinder Surfaces}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27430}, school = {Universit{\"a}t Passau}, year = {2014}, abstract = {In this thesis, we investigates plane drawings of undirected and directed graphs on cylinder surfaces. In the case of undirected graphs, the vertices are positioned on a line that is parallel to the cylinder's axis and the edge curves must not intersect this line. We show that a plane drawing is possible if and only if the graph is a double-ended queue (deque) graph, i. e., the vertices of the graph can be processed according to a linear order and the edges correspond to items in the deque inserted and removed at their end vertices. A surprising consequence resulting from these observations is that the deque characterizes planar graphs with a Hamiltonian path. This result extends the known characterization of planar graphs with a Hamiltonian cycle by two stacks. By these insights, we also obtain a new characterization of queue graphs and their duals. We also consider the complexity of deciding whether a graph is a deque graph and prove that it is NP-complete. By introducing a split operation, we obtain the splittable deque and show that it characterizes planarity. For the proof, we devise an algorithm that uses the splittable deque to test whether a rotation system is planar. In the case of directed graphs, we study upward plane drawings where the edge curves follow the direction of the cylinder's axis (standing upward planarity; SUP) or they wind around the axis (rolling upward planarity; RUP). We characterize RUP graphs by means of their duals and show that RUP and SUP swap their roles when considering a graph and its dual. There is a physical interpretation underlying this characterization: A SUP graph is to its RUP dual graph as electric current passing through a conductor to the magnetic field surrounding the conductor. Whereas testing whether a graph is RUP is NP-hard in general [Bra14], for directed graphs without sources and sink, we develop a linear-time recognition algorithm that is based on our dual graph characterization of RUP graphs.}, subject = {Planarer Graph}, language = {en} } @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} }