FG Diskrete Mathematik

3 Items

Recent Submissions
Planar graphs and face areas: Area-Universality

Kleist, Linda (2018)

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.