A Characterization of Horoidal Digraphs - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

A Characterization of Horoidal Digraphs

Ardeshir Dolati
  • Function : Author
  • PersonId : 1030363


In this paper we investigate the upward embedding problem on the horizontal torus. The digraphs that admit upward embedding on this surface are called horoidal digraphs. We shall characterize the horoidal digraphs, combinatorially. Then, we construct a new digraph from an arbitrary digraph in such a way that the new digraph has an upward embedding on sphere if and only if it is horoidal. By using these constructed digraphs, we show that the decision problem whether a digraph has an upward embedding on the horizontal torus is NP-Complete.
Fichier principal
Vignette du fichier
440117_1_En_2_Chapter.pdf (293.18 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01760640 , version 1 (06-04-2018)


Attribution - CC BY 4.0



Ardeshir Dolati. A Characterization of Horoidal Digraphs. 2nd International Conference on Topics in Theoretical Computer Science (TTCS), Sep 2017, Tehran, Iran. pp.11-25, ⟨10.1007/978-3-319-68953-1_2⟩. ⟨hal-01760640⟩
31 View
57 Download



Gmail Facebook Twitter LinkedIn More