FG Diskrete Mathematik

7 Items

Recent Submissions
Flip distances between graph orientations

Aichholzer, Oswin ; Cardinal, Jean ; Huynh, Tony ; Knauer, Kolja ; Mütze, Torsten ; Steiner, Raphael ; Vogtenhuber, Birgit (2020-07-27)

Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the mini...

Arrangements of pseudocircles: Triangles and drawings

Felsner, Stefan ; Scheucher, Manfred (2020-01-27)

A pseudocircle is a simple closed curve on the sphere or in the plane. The study of arrangements of pseudocircles was initiated by Grünbaum, who defined them as collections of simple closed curves that pairwise intersect in exactly two crossings. Grünbaum conjectured that the number of triangular cells p_3 in digon-free arrangements of n pairwise intersecting pseudocircles is at least 2n-4. We ...

Points, lines, and circles:

Scheucher, Manfred (2020)

In this dissertation we investigate some problems from the field of combinatorics and computational geometry which involve basic geometric entities (points, lines, and circles). In the first part we look at Erdös-Szekeres type problems: The classical theorem by Erdös and Szekeres from 1935 asserts that, for every natural number 𝑘, every sufficiently large point set in general position contai...

Efficient graph exploration

Hackfeld, Jan (2019)

The thesis “Efficient Graph Exploration” studies the following three closely related problems, where collaborating mobile agents move in a graph and have to jointly perform a certain task. Chapter 2 “Space Efficient Graph Exploration” considers the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pe...

Planar graphs and face areas: Area-Universality

Kleist, Linda (2019)

In this work, we study planar graphs with prescribed face areas. This field is inspired by cartograms. A 'cartogram' is a distorted map where the size of the regions are proportional to some statistical parameter such as the population, the total birth, the gross national product, or some other special property. As a mathematical abstraction we are interested in straight-line drawings of plane...

On the dimension of posets with cover graphs of treewidth 2

Joret, Gwenael ; Micek, Piotr ; Trotter, William T. ; Wang, Ruidong ; Wiechert, Veit (2016-06-01)

In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimen...

An On-line competitive algorithm for coloring bipartite graphs without long induced paths

Micek, Piotr ; Wiechert, Veit (2016)

The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for P9-free bipartite graphs.