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

https://hal.inria.fr/hal-01760640
Contributor : Hal Ifip <>
Submitted on : Friday, April 6, 2018 - 3:07:59 PM
Last modification on : Friday, April 6, 2018 - 3:08:58 PM

File

440117_1_En_2_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

116

Files downloads

87