Péter Hajnal: Saturated simple and 2-simple drawings of graphs |
|
|
|
Péntek, 20. Február 2015, 10:00 - 12:00
|
|
Abstract. A drawing of a graph is simple iff any two edge-curves have at most one common point (a common endpoint or a crossover). A drawing is 2-simple iff any two edge-curves have at most two common points. Complete graphs have simple drawings. But non-complete graphs might have simple drawing such that there is no way to add an edge-curve and preserve simplicity (such a drawing is called a saturated drawing).
The main problem: How few edges can we have in a saturated simple drawing of a graph on n vertices? One can propose the same problem for 2-simple drawings. The answer is linear in both cases. I am going to sketch the best constructions so far.
This is a joint work with Alexander Igamberdiev, Gunter Rote and Andre Schulz. |
Hely : Riesz terem |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013