RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
19 октября 2016 г. 18:10, г. Долгопрудный, г. Москва, Кочновский проезд, д. 3, ФКН, аудитория 505
 


Stability of intersections of graphs in the plane and the van Kampen obstruction

А. Б. Скопенков

Количество просмотров:
Эта страница:61

Аннотация: A map $\varphi:K\to \mathbb R^2$ of a graph $K$ is approximable by embeddings, if for each $\varepsilon>0$ there is an $\varepsilon$-close to $\varphi$ embedding $f:K\to\mathbb R^2$. Analogous notions were studied under the names of cluster planarity and weak simplicity. We present criteria for approximability by embeddings (P. Minc, 1997, M. Skopenkov, 2003) and their algorithmic corollaries. A map $\varphi:K\sqcup L\to \mathbb R^2$ of the disjoint union of graphs $K$ and $L$ is approximable by maps with disjoint images, if for each $\varepsilon>0$ there is an $\varepsilon$-close to $\varphi$ map $f:K\sqcup L\to\mathbb R^2$ such that $f(K)\cap f(L)=\emptyset$. We present open problems on this notion. We introduce the van Kampen (or Hanani-Tutte) obstructions for these properties, as well as their generalizations to higher dimensions and to $r$-tuple intersections. We present the completeness result of this obstruction (D. Repovš and A. Skopenkov, 1998) and its algorithmic corollary.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020