Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Given an embedded planar acyclic digraph G, we define the problem of acyclichamiltonian path completion with crossing minimization Acyclic-HPCCM to bethe problem of determining a hamiltonian path completion set of edges suchthat, when these edges are embedded on G, they create the smallest possiblenumber of edge crossings and turn G to a hamiltonian acyclic digraph. Ourresults include: 1. We provide a characterization under which a planarst-digraph G is hamiltonian. 2. For an outerplanar st-digraph G, we define thest-polygon decomposition of G and, based on its properties, we develop alinear-time algorithm that solves the Acyclic-HPCCM problem. 3. For the classof planar st-digraphs, we establish an equivalence between the Acyclic-HPCCMproblem and the problem of determining an upward 2-page topological bookembedding with minimum number of spine crossings. We infer based on thisequivalence for the class of outerplanar st-digraphs an upward topological2-page book embedding with minimum number of spine crossings. To the best ofour knowledge, it is the first time that edge-crossing minimization is studiedin conjunction with the acyclic hamiltonian completion problem and the firsttime that an optimal algorithm with respect to spine crossing minimization ispresented for upward topological book embeddings.



Autor: Tamara Mchedlidze, Antonios Symvonis

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados