Abstract
Given an embedded planar acyclic digraph G, the acyclic hamiltonian path completion with crossing minimization (Acyclic- HPCCM) problem is to determine 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. In this paper, we present a linear time algorithm which solves the Acyclic-HPCCM problem on any outerplanar st-digraph G. The algorithm is based on properties of the optimal solution and an st-polygon decomposition of G. As a consequence of our result, we can obtain for the class of outerplanar st-digraphs upward topological 2-page book embeddings with minimum number of spine crossings.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61(2-3), 175–198 (1988)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: STOC 1974: Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47–63. ACM Press, New York (1974)
Karejan, Z.A., Mosesjan, K.M.: The hamiltonian completion number of a digraph (in Russian). Akad. Nauk Armyan. SSR Dokl. 70(2-3), 129–132 (1980)
Kelly, D.: Fundamentals of planar ordered sets. Discrete Math 63, 197–216 (1987)
Mchedlidze, T., Symvonis, A.: Crossing-optimal acyclic hp-completion for outerplanar st-digraphs, arXiv:0904.2129, http://arxiv.org/abs/0904.2129
Mchedlidze, T., Symvonis, A.: Optimal acyclic hamiltonian path completion for outerplanar triangulated st-digraphs (with application to upward topological book embeddings), arXiv:0807.2330, http://arxiv.org/abs/0807.2330
Mchedlidze, T., Symvonis, A.: Crossing-optimal acyclic hamiltonian path completion and its application to upward topological book embeddings. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol. 5431, pp. 250–261. Springer, Heidelberg (2009)
Wigderson, A.: The complexity of the hamiltonian circuit problem for maximal planar graphs. Technical Report TR-298, Princeton University, EECS Department (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mchedlidze, T., Symvonis, A. (2009). Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs. In: Ngo, H.Q. (eds) Computing and Combinatorics. COCOON 2009. Lecture Notes in Computer Science, vol 5609. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02882-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-02882-3_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02881-6
Online ISBN: 978-3-642-02882-3
eBook Packages: Computer ScienceComputer Science (R0)