Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings

DOI10.1007/978-3-642-00202-1_22zbMath1211.05030OpenAlexW1555017787MaRDI QIDQ3605502

Antonios Symvonis, Tamara Mchedlidze

Publication date: 24 February 2009

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_22

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

Evolutionary operators for the Hamiltonian completion problem ⋮ Spine Crossing Minimization in Upward Topological Book Embeddings ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Curve-constrained drawings of planar graphs
• Minimizing setups in ordered sets of fixed width
• Jump number of dags having Dilworth number 2
• Dynamic maintenance of planar digraphs, with applications
• Ordered sets, pagenumbers and planarity
• A unified approach to visibility representations of planar graphs
• Fundamentals of planar ordered sets
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• Embedding planar graphs in four pages
• Algorithms for plane representations of acyclic digraphs
• On minimizing jumps for ordered sets
• Tackling the jump number of interval orders
• Counting linear extensions
• Some simplified NP-complete graph problems
• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
• Optimal Linear Extensions by Interchanging Chains
• Minimizing Setups for Cycle-Free Ordered Sets
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Generating Linear Extensions Fast
• Stack and Queue Layouts of Posets
• Computing Upward Topological Book Embeddings of Upward Planar Digraphs
• Fundamentals of Computation Theory
• The Two-Triangle Case of the Acquaintance Graph

This page was built for publication: Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings