Elisabeth Gaar mit ÖGOR Diplomarbeitspreis ausgezeichnet

Elisabeth Gaar ist als Dissertantin im Karl-Popper-Kolleg am Institut für Mathematik tätig. Betreut wird sie von Franz Rendl. Zuletzt war Gaar, die das Bachelorstudium Technische Mathematik und das Masterstudium Technische Mathematik: Operations Research und Statistik an der TU Graz absolvierte, als Gastwissenschaftlerin an der University of Waterloo in Kanada.

Das Thema ihrer Masterarbeit beschreibt Elisabeth Gaar folgendermaßen: „In der Mathematik sind Graphen Objekte, die aus Knoten und Kanten bestehen. Knoten kann man sich als Punkte vorstellen und Kanten verbinden diese Punkte miteinander. Wenn zwei Knoten durch eine Kante verbunden sind, so nennt man diese adjazent. Graphen bilden somit eine einfache Möglichkeit, diverse Sachverhalte zu veranschaulichen. Eine alternative Darstellungsmöglichkeit von Graphen bilden Pfaden in einem Gitter. Hier entspricht ein Knoten einem Pfad in einem Gitter und zwei Knoten sind adjazent, wenn die entsprechende Pfade im Gitter mindestens eine Gitterkante gemeinsamen haben. Ein Graph, der so eine Darstellung hat, wird Kanten-Überschneidungsgraph von Pfaden auf einem Gitter (edge intersection graph of paths on a grid, EPG), und diese Darstellung EPG-Repräsentation genannt. Falls in dieser Darstellung jeder Pfad im Gitter nur nach rechts oder nach oben verläuft, so wird die Darstellung monotone EPG-Repräsentation genannt. Falls in der jeweiligen Darstellung jeder Pfad maximal k Knicke hat, so wird der Graph (monoton) k-EPG genannt und das minimale k, für das ein Graph (monoton) k-EPG ist, wird als (monotone) Biegungszahl bezeichnet. Die Darstellung eines Graphen als k-EPG-Repräsentation mit einem möglichst kleinen k ist unter anderem in der Chip-Herstellung von Interesse. Dort steigt mit der Anzahl der Knicke der EPG-Repräsentation sowohl die Kosten für die Herstellung, also auch die benötigte Größe eines Chips. In der Masterarbeit wird für einige Graphenklassen die (monotone) Biegungszahl bestimmt und insbesondere eine (monotone) EPG-Repräsentation mit der kleinstmöglichen Anzahl an Knicken angegeben. Zusätzlich wird die Beziehung zwischen Biegungszahl und monotoner Biegungszahl genauer untersucht.“

Die Österreichische Gesellschaft für Operations Research (ÖGOR) vergibt die ÖGOR Diplomarbeits- und Dissertationspreise für hervorragende Dissertationen bzw. Master- und Diplomarbeiten aus dem Bereich des Operations Research (OR). Es können sowohl theoretische Arbeiten als auch praktische Anwendungen des OR eingereicht werden. 2015 ging der ÖGOR Dissertationspreis auch nach Klagenfurt: Gaars Kollege Philipp Hungerländer wurde im November 2015 für seine Dissertation ausgezeichnet.