Skip to Main content Skip to Navigation
Conference papers

A Characterization of Horoidal Digraphs

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Friday, April 6, 2018 - 3:07:59 PM
Last modification on : Friday, April 6, 2018 - 3:08:58 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads