Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs - Mchedlidze, Tamara; Symvonis, Antonios (Journal of Graph Algorithms and Applications, 2011)
Given an embedded planar acyclic digraph G, we define the problemof acyclic hamiltonian path completion with crossingminimization (acyclic-HPCCM) to be the problem of determining ahamiltonian path completion set of edges such that, whenthese edges are embedded on G, they create the smallest possiblenumber of edge crossings and turn G to a hamiltonian acyclicdigraph. Our results include: We provide a characterization under which a planar st-digraph Gis hamiltonian. <!----> For an outerplanar st-digraph G,we define the st-Polygon decomposition of G and, based onits properties, we develop a linear-time algorithm that solves theacyclic-HPCCM problem. <!----> For the class of planar st-digraphs, we establish an equivalencebetween the acyclic-HPCCM problem and the problem of determining anupward 2-page topological book embedding with minimum number ofspine crossings. We obtain (based on this equivalence) for the classof outerplanar st-digraphs, an upward topological 2-page bookembedding with minimum number of spine crossings. <!----> <!----> To the best of our knowledge, it is the first time thatedge-crossing minimization is studied in conjunction with theacyclic hamiltonian completion problem and the first time that anoptimal algorithm with respect to spine crossing minimization ispresented for upward topological book embeddings. <!---->