Universität zu Köln

An Integer Programming Approach to Exact and Fuzzy Symmetry Detection

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

[img]
Preview
PDF
Download (786Kb) | Preview

    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 abstract:
    AbstractLanguage
    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:
    CreatorsEmail
    Buchheim, Christophbuchheim@informatik.uni-koeln.de
    URN: urn:nbn:de:hbz:38-9183
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    Symmetrie , ganzzahlige ProgrammierungGerman
    Symmetry , Integer ProgrammingEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: 2003
    Date Type: Completion
    Date of oral exam: 02 June 2003
    Full Text Status: Public
    Date Deposited: 06 Aug 2003 11:33:17
    Referee
    NameAcademic Title
    Jünger, MichaelProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/918

    Actions (login required)

    View Item