|
|
|
|
|
|
|
|||
| See by year | See by month | Jump to month | |||||||
Péter Hajnal: Saturated simple and 2-simple drawings of graphs |
|
|||
|
|
||||
|
||||
| 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. |
||||
| Location : Riesz terem | ||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013