%0 Conference Proceedings
%T A Characterization of Horoidal Digraphs
%+ Shahed University [Téhéran]
%A Dolati, Ardeshir
%Z Part 2: Algorithms and Complexity
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 2nd International Conference on Topics in Theoretical Computer Science (TTCS)
%C Tehran, Iran
%Y Mohammad Reza Mousavi
%Y Jiří Sgall
%I Springer International Publishing
%3 Topics in Theoretical Computer Science
%V LNCS-10608
%P 11-25
%8 2017-09-12
%D 2017
%R 10.1007/978-3-319-68953-1_2
%K Upward embedding
%K Sphericity testing
%K Horizontal torus
%K Computational complexity
%K Horoidal st-graphs
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.8
%2 https://inria.hal.science/hal-01760640/document
%2 https://inria.hal.science/hal-01760640/file/440117_1_En_2_Chapter.pdf
%L hal-01760640
%U https://inria.hal.science/hal-01760640
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-8
%~ IFIP-TTCS
%~ IFIP-LNCS-10608