Best Paper Award for Felix Schröder

The annual international symposium Graph Drawing and Network Visualization focuses on the combinatorial and algorithmic aspects of graph drawing and the design of systems and interfaces for network visualization. At the 32^nd symposium, held from September 18 to 20 in Vienna, Dr. Schröder presented a paper titled “The Density Formula: One Lemma to Bound them All”. For this article, he also received the Best Paper Award.

Dr. Schröder's research concerns with graph theory and combinatorial geometry. In the award-winning paper, he, along with colleagues, presents a new lemma (auxiliary statement) useful for graph drawing in and out of plane. “Our lemma can be used to prove bounds on the so-called density of non-planar graphs. In this context, graphs are networks where some nodes (or vertices) are connected by edges. The number of edges in various graphs is referred to as ‚density.‘ Density is an important topic because if you can prove that there aren't too many edges, the graph is considered sparse, which often means that algorithms can be run efficiently on it,” explains Dr. Schröder.

In the context of graph drawing, the most well-known class is planar graphs. These are graphs where vertices can be drawn as points in two-dimensional space and all edges as line segments between these points such that no two edges intersect— the only common point, they may have, is at the endpoints. However, this is not entirely true for classes beyond planar graphs. “For example, in k-planar graphs, edges may cross, but only a few times (at most k times), while in so-called rectilinear (RAC) graphs, crossings can only occur at right angles. In our article, we proposed and proved a new lemma—derived almost directly from the famous Euler's formula—and used it to provide a uniform proof of many results regarding the density of graph classes close to planar graphs that were already known in the literature. With the help of this lemma, we answered several open questions, such as the density of RAC graphs. Our proof technique is so simple that we were able to include many results in the article, all of which now have simpler proofs than before (if they had any at all),” explains Dr. Schröder.

Dr. Schröder joined the Department of Applied Mathematics last November after defending his doctoral thesis at the Technical University of Berlin. “There are many excellent scientists working at Matfyz, some of whom I had already collaborated with, so I knew that moving to Prague was a good decision,” Dr. Schröder responds when asked why he chose to undertake a fellowship at Charles University in the DiGeo group led by Associate Professor Pavel Valtr. His contract at the faculty ends at the end of the year. “I will apply for a one-month extension; I am not clear about my further plans, but, if possible, I would like to stay close to Berlin, where most of my family and friends live,” the young scientist outlines.