Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings

摘要

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:rn1. We provide a characterization under which a triangulated st-digraph G is hamiltonian.rn2. 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 si-digraphs an upward topological 2-page book embedding with minimum number of spine crossings and at most one spine crossing per edge.