Given an embedded planar acyclic digraph G, we define the problem of acyclic hamiltonian path completion with crossing minimization (Acyclic-HPCCM) to be the problem of determining a hamiltonian path completion set of edges such that, when these edges are embedded on G, they create the smallest possible number of edge crossings and turn G to an acyclic hamiltonian digraph. Our results include: We provide a characterization under which a triangulated si-digraph G is hamiltonian. For the class of planar si-digraphs, we establish an equivalence between the Acyclic-HPCCM problem and the problem of determining an upward 2-page topological book embedding with minimum number of spine crossings. Based on this equivalence we infer for the class of outerplanar triangulated st-digraphs an upward topological 2-page book embedding with minimum number of spine crossings and at most one spine crossing per edge.
展开▼
