Optimal Acyclic Hamiltonian Path Completion for Outerplanar Triangulated st-Digraphs (with Application to Upward Topological Book Embeddings)

Details Optimal Acyclic Hamiltonian Path Completion for Outerplanar Triangulated st-Digraphs (with Application to Upward Topological Book Embeddings) Optimal Acyclic Hamiltonian Path Completion for Outerplanar Triangulated st-Digraphs (with Application to Upward Topological Book Embeddings)

2008-07-15

arxiv.org/abs/0807.2330v2

Computer Science

Data Structures and Algorithms

Scientific paper

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 an 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 digraph. Our results include: --We provide a characterization under which a triangulated st-digraph G is hamiltonian. --For an outerplanar triangulated st-digraph G, we define the st-polygon decomposition of G and, based on its properties, we develop a linear-time algorithm that solves the Acyclic-HPCCM problem with at most one crossing per edge of G. --For the class of st-planar 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. We infer (based on this equivalence) 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. To the best of our knowledge, it is the first time that edge-crossing minimization is studied in conjunction with the acyclic hamiltonian completion problem and the first time that an optimal algorithm with respect to spine crossing minimization is presented for upward topological book embeddings.

Affiliated with

Also associated with

No associations

Rating

Optimal Acyclic Hamiltonian Path Completion for Outerplanar Triangulated st-Digraphs (with Application to Upward Topological Book Embeddings) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Acyclic Hamiltonian Path Completion for Outerplanar Triangulated st-Digraphs (with Application to Upward Topological Book Embeddings), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Acyclic Hamiltonian Path Completion for Outerplanar Triangulated st-Digraphs (with Application to Upward Topological Book Embeddings) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-596027