Embeddings of *-graphs into 2-surfaces

This paper considers *-graphs in which all vertices have degree 4 or 6, and studies the question of calculating the genus of orientable 2-surfaces into which such graphs may be embedded. A *-graph is a graph endowed with a formal adjacency structure on the half-edges around each vertex, and an embedding of a *-graph is an embedding under which the formal adjacency relation on half-edges corresponds to the adjacency relation induced by the embedding. *-graphs are a natural generalization of four-valent framed graphs, which are four-valent graphs with an opposite half-edge structure. In [Embeddings of four-valent framed graphs into 2-surfaces, Dokl. Akad. Nauk 424(3) (2009) 308-310], the question of whether a four-valent framed graph admits a Z2-homologically trivial embedding into a given surface was shown to be equivalent to a problem on matrices. We show that a similar result holds for *-graphs in which all vertices have degree 4 or 6. This gives an algorithm in quadratic time to determine whether a *-graph admits an embedding into the plane. © 2013 World Scientific Publishing Company.

Авторы
Friesen T.1 , Manturov V.O. 2
Редакторы
-
Издательство
-
Номер выпуска
12
Язык
Английский
Страницы
-
Статус
Опубликовано
Подразделение
-
Номер
1341005
Том
22
Год
2013
Организации
  • 1 Ohio State University, 154 W 12th Ave., Columbus, OH 43210, United States
  • 2 Peoples' Friendship University of Russia, Ordjonikidze St., 3, Moscow 117198, Russian Federation
Ключевые слова
*-Graph; Embedding; Genus; Graph; Surface
Дата создания
19.10.2018
Дата изменения
19.10.2018
Постоянная ссылка
https://repository.rudn.ru/ru/records/article/record/1997/