# Simultaneous embedding and visualization of graphs

http://hdl.handle.net/10150/290066
Title:
Simultaneous embedding and visualization of graphs
Author:
Erten, Cesim
Issue Date:
2004
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Graph embedding and visualization problems arise in relational information visualization. The two primary goals in graph visualization are drawings that convey the relationships in the underlying data and drawings that are aesthetically pleasing. Often, we have a series of related graphs that we would like to compare. In such cases it is also important to preserve the mental map between the drawings of different graphs so that the relationship between the graphs is clearly visible. For simultaneous drawing of graphs, we first present a linear-time algorithm to simultaneously embed a planar graph and its dual on an integer grid, so that the dual vertices are placed inside their corresponding primal faces and the dual edges cross their primal edges. The area of the display grid is (2n - 2) x (2n - 2) where n is the number of vertices in the graphs. We then present the problem of simultaneous embedding of planar graphs defined on the same set of vertices. In this case we would like to embed the graphs so that the matched vertices of the graphs are placed at the exact same locations and the individual drawings of the graphs are crossing-free. First we consider restricted classes of planar graphs such as paths, cycles, and caterpillars. We provide algorithms to embed two such graphs on small-area grids. We then show that there are some classes of planar graphs for which simultaneous embedding is not possible. We also consider a version of the problem where there is no mapping between the vertices of the graphs and we provide an algorithm to embed a planar graph and an outerplanar graph on an O(n²) x O(n²) grid. We provide heuristic algorithms for simultaneously embedding general graphs and the visualization tecniques we employ to display them. We present three heuristic embedding algorithms and three different visualizations suitable for each of the embedding algorithms. We describe our system that implements these algorithms and techniques. As a technique that helps simultaneous visualization of graphs we describe morphing. We discuss the disadvantages of a commonly used morphing technique, linear morphing, in terms of mental map preservation. Then we provide our algorithm to morph a source planar drawing into a target planar drawing smoothly and without creating any edge-crossings throughout the morph. This technique helps preserve the mental map between the different drawings.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Computer Science.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Degree Grantor:
University of Arizona
Kobourov, Stephen G.

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleSimultaneous embedding and visualization of graphsen_US
dc.creatorErten, Cesimen_US
dc.contributor.authorErten, Cesimen_US
dc.date.issued2004en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractGraph embedding and visualization problems arise in relational information visualization. The two primary goals in graph visualization are drawings that convey the relationships in the underlying data and drawings that are aesthetically pleasing. Often, we have a series of related graphs that we would like to compare. In such cases it is also important to preserve the mental map between the drawings of different graphs so that the relationship between the graphs is clearly visible. For simultaneous drawing of graphs, we first present a linear-time algorithm to simultaneously embed a planar graph and its dual on an integer grid, so that the dual vertices are placed inside their corresponding primal faces and the dual edges cross their primal edges. The area of the display grid is (2n - 2) x (2n - 2) where n is the number of vertices in the graphs. We then present the problem of simultaneous embedding of planar graphs defined on the same set of vertices. In this case we would like to embed the graphs so that the matched vertices of the graphs are placed at the exact same locations and the individual drawings of the graphs are crossing-free. First we consider restricted classes of planar graphs such as paths, cycles, and caterpillars. We provide algorithms to embed two such graphs on small-area grids. We then show that there are some classes of planar graphs for which simultaneous embedding is not possible. We also consider a version of the problem where there is no mapping between the vertices of the graphs and we provide an algorithm to embed a planar graph and an outerplanar graph on an O(n²) x O(n²) grid. We provide heuristic algorithms for simultaneously embedding general graphs and the visualization tecniques we employ to display them. We present three heuristic embedding algorithms and three different visualizations suitable for each of the embedding algorithms. We describe our system that implements these algorithms and techniques. As a technique that helps simultaneous visualization of graphs we describe morphing. We discuss the disadvantages of a commonly used morphing technique, linear morphing, in terms of mental map preservation. Then we provide our algorithm to morph a source planar drawing into a target planar drawing smoothly and without creating any edge-crossings throughout the morph. This technique helps preserve the mental map between the different drawings.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectComputer Science.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US