Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, November 15, 2012 |
| Time | 11:00 am |
| Concludes | 12:15 pm |
| Location | Gould-Simpson 906 |
| Speaker | Michael A. Bekos |
| Title | Professor |
| Affiliation | University of Tuebingen, Germany |
Smooth Orthogonal Layouts and a Conjecture of Lovasz
Part 1: Orthogonal graph drawing has a long tradition, dating back to VLSI layouts and floor-planning applications. While in traditional orthogonal layouts every edge is made of a sequence of axis-aligned line segments, in smooth orthogonal layouts every edge is made of axis-aligned segments and circular arcs with common tangents. Our goal is to create such layouts with low edge complexity, measured by the number of line and circular arc segments. We show that every biconnected 4-planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity-2 traditional orthogonal layout, we can transform it into a smooth complexity-2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity-2 layout.
Part 2: Lovasz conjectured that every connected 4-regular planar graph G admits a realization as a system of circles, i.e., it can be drawn on the plane utilizing a set of circles, such that the vertices of G correspond to the intersection and touching points of the circles and the edges of G are the arc segments among pairs of intersection and touching points of the circles. If G is 3-connected, we affirmatively answer Lovasz's conjecture. However, for the case of simply connected graphs, we demonstrate infinite classes of simply connected or biconnected 4-regular planar graphs which are not 3-connected and do not admit realizations as system of circles.
Biography
Michael A. Bekos is a postdoctoral researcher at the Algorithmic Research Group at the Department of Informatics of the University of Tuebingen. His primary research interests focus on algorithms and their complexity mostly from the research areas of Graph Drawing, Information Visualization and Map Labeling.