Constrained Graph Drawing

Cite This

Files in this item

Checksum: MD5:077d8728906d707c417f68b569241488

PAMPEL, Barbara, 2012. Constrained Graph Drawing [Dissertation]. Konstanz: University of Konstanz

@phdthesis{Pampel2012Const-19396, title={Constrained Graph Drawing}, year={2012}, author={Pampel, Barbara}, address={Konstanz}, school={Universität Konstanz} }

Our world is full of networks. The linking relationships might be quite abstract, such as friendship or metabolic processes or even more concrete, like roads or railways, but are still hard to overlook. One way to deal with such a network, is to mathematically model it as a graph with vertices representing the entities and edges the relationships. Graphs are widely used to visualize relational data. The area that deals with the theory and algorithmic questions of graph visualization is conventionally called graph drawing.<br /><br />The usefulness of a drawing depends on aesthetic criteria as well as on the amount of information contained in the data which can be revealed by the drawing. Especially relevant for the readability is the minimization of edge crossings, which is why many methods yield intersection-free drawings if the input graph is planar. Yet the respective importance of the different criteria depends on the application. An aesthetically good drawing might not display relevant information or might even be misleading. A good vertex distribution for example can be helpful to overview a data set, but the relative closeness of objects might be interpreted as the strength of their relationship. Likewise, further information can be assigned not only to the elements, vertices and edges, but can also be displayed through their absolute and relative positions. Various criteria can be described by formal constraints. With the help of such geometric constraints, the graphs can meet the different requirements of concrete applications. In this thesis, various types of fundamental constraints on relevant classes of graphs are studied. For some problems efficient drawing algorithms could be developed, others were proven to be NP-hard, that is current state of research suggests that an efficient solution does not exist. Pampel, Barbara eng Pampel, Barbara 2012 2012-07-16T07:52:02Z terms-of-use Constrained Graph Drawing 2012-07-16T07:52:02Z

Downloads since Oct 1, 2014 (Information about access statistics)

diss_pampel.pdf 1584

This item appears in the following Collection(s)

Search KOPS


My Account