Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
Vol. 15, no. 3, pp. 373-415, 2011. Regular paper.
Abstract 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 a hamiltonian acyclic digraph. Our results include:
Submitted: May 2009.
Reviewed: January 2010.
Revised: April 2010.
Accepted: October 2010.
Final: November 2010.
Published: July 2011.