Universität zu Köln

Buchheim, Christoph (2003). An Integer Programming Approach to Exact and Fuzzy Symmetry Detection. PhD thesis, Universität zu Köln.

Preview

PDF Dissertation.pdf Download (804kB)

Abstract

The aim of Automatic Graph Drawing is to compute nice and well-readable layouts of diagrams given abstractly as a set of entities and a set of relations between them. For the sake of automation, diagrams are modeled by graphs. Moreover, formal criteria are specified that measure the quality of such layouts. Empirical studies show that one important criterion is the display of symmetry: if they exist, symmetric layouts are preferred. However, it is an NP-hard problem to decide whether and how an abstractly given graph can be drawn in a symmetrical way. We present an approach for detecting symmetries based on integer programming techniques. This approach can be used to find symmetries or different kinds of automorphisms for general graphs. As most practical graphs do not admit any exact symmetry, we also consider an extension for detecting fuzzy symmetries.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Suche nach exakten und unscharfen Symmetrien mit Hilfe ganzzahliger Programmierung German
Translated abstract:	Abstract Language Das Ziel beim Automatischen Zeichnen von Graphen besteht in der Erzeugung von schönen und übersichtlichen Zeichnungen von Diagrammen, die abstrakt als Menge von Objekten und deren Beziehungen untereinander gegeben sind. Zum Zwecke der Automatisierung werden Diagramme als Graphen modelliert. Darüber hinaus werden formale Kriterien festgelegt, mit deren Hilfe die Qualität einer Zeichnung bewertet werden kann. Empirische Studien zeigen, dass ein wichtiges Kriterium in der Darstellung von Symmetrie besteht. Wenn möglich, sollen die Zeichnungen also symmetrisch sein. Es ist jedoch ein NP-schweres Problem, für einen abstrakt gegebenen Graphen zu entscheiden, ob und wie er symmetrisch gezeichnet werden kann. In dieser Arbeit wird ein Ansatz zur Symmetrieerkennung vorgestellt, der auf Techniken der ganzzahligen Programmierung basiert. Mit diesem Ansatz können für einen beliebigen Graphen Symmetrien sowie andere spezielle Automorphismen bestimmt werden. Da die meisten Graphen aus praktischen Anwendungen jedoch keine exakt symmetrische Zeichnung zulassen, wird zusätzlich eine Erweiterung der Suche auf unscharfe Symmetrien betrachtet. German
Creators:	Creators Email ORCID ORCID Put Code Buchheim, Christoph buchheim@informatik.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-9183
Date:	2003
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Symmetrie , ganzzahlige Programmierung German Symmetry , Integer Programming English
Date of oral exam:	2 June 2003
Referee:	Name Academic Title Jünger, Michael Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/918