DIMACS REU 2018

General Information

Student:Michael Skotnica
Office:CoRE 448
Contact:skotnicam-at-seznam.cz
School:Faculty of Mathematics and Physics, Charles University, Czech Republic
Coworkers: Martin Hora, Vaclav Koncicky, Peter Korcsok, Radim Predstirany, Ondrej Splichal, Aneta Stastna, Jakub Tetek,
Problem(s):k-colored Point-set Embeddability of Graphs

I am a member of the Czech group. Our Rutgers advisor is Periklis Papakonstantinou. As a group, we have several projects. I am mainly working on a problem k-colored Point-set Embeddability of Graphs together with Peter. For a description of our other problems, please see web pages of my Czech colleagues.

Project Description

k-colored Point-set Embeddability of Graphs

We are given a planar graph $G=(V,E)$ and a set of point $S$ on a plane such that $|V| = |S|$. The graph $G$ as well as the set $S$ is colored with $k$ colors such that the multiplicity of each color is the same in $S$ and $G$. The task is to draw the graph $G$ to the plane such that:

  • Each point of $G$ is represented by a point of $S$ with the same color,
  • each edge of $G$ is represented by a piecewise linear arc,
  • the number of bends per each edge is minimal.

Such minimal possible number of bends is called curve complexity of the graph $G$ and the set $S$.

Given a family of planar graphs $\mathcal{G}$ and a number of colors $k$, we want to know the worst-case curve complexity for any graph $G \in \mathcal{G}$ and any point set $S$. Such worst-case curve complexity is called curve complexity of the class $\mathcal{G}$. That is, if the class $\mathcal{G}$ has the curve complexity $c$, then every $G \in \mathcal{G}$ can be embedded to any set $S$ using $c$ bends.

Our main goal is to improve lower (1) and upper (5) bounds of curve complexity of 2-colored point-set embedding of trees or some other classes of graphs, such as outerplanar graphs.

Weekly Log

Week 1:

I learned basic information about REU during the orientation day. Together with my Czech colleagues we have choosen several projects. I have decided to work with Peter on the problem k-colored Point-set Embeddability of Graphs.

During the first week, we read articles about this problem, we learned known results and prepared the presentation.

Week 2:

We were trying to increase the lower bound 1 for trees by finding an example which needs two bends. However, without any success. Martin wrote a computer program for finding such counterexamples for small number of vertices. Then we were trying at least to increase lower bound for outerplanar graphs using Martin's program. Again without any success. I started to conjecture that the curve complexity of outerplanar graphs is 1. However, current upper bound is 5.

We are also trying to generalize a caterpillar graphs construction, which needs 1 bend, for trees.

Week 3:

Generailizing a caterpilar construction for trees does not seems like a good idea. We readed an article [1] and learned a technique of an Augmenting Hamiltonian cycle. We started trying to decrease the upper bound 5 for outerplannar graphs.

Week 4:

We decreased the upper bound for outerplannar graphs from 5 to 4.

Week 5+6:

We were analyzing the algorithm from [1] for finding an embedding for outerplanar graphs and trying to improve it. Unfortunately we found examples of outerplanar graphs for which it does not behave well. We were continuing with finding outerplannar graphs which need 2 bends. However, again with no success.

Week 7:

We started analyzing a behavior of algorithm from [1] for trees. We prepared the final presentation and started to write a report of our work.

References

Presentations

Additional Information