Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00231 Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs Tamara Mchedlidze and Antonios Symvonis 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:
|
Reviewed: January 2010. Final: November 2010. Published: July 2011. Accepted: October 2010. Submitted: May 2009. Revised: April 2010. Communicated by Sandip Das and Ryuhei Uehara |
Journal of Graph Algorithms and Applications |