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

DOI10.1007/978-3-642-00202-1_22MaRDI QIDQ3605502zbMATHOpenAlexFDO

Authors Tamara Mchedlidze, Antonios Symvonis

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

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

Recommendations

• Crossing-optimal acyclic HP-completion for outerplanar \(st\)-digraphs
• Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
• Crossing-free acyclic Hamiltonian path completion for planar \(st\)-digraphs
• Spine Crossing Minimization in Upward Topological Book Embeddings
• Computing Upward Topological Book Embeddings of Upward Planar Digraphs

Cites work

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

Cited in

(8)

• Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
• On 1-bend upward point-set embeddings of \(st\)-digraphs
• Spine Crossing Minimization in Upward Topological Book Embeddings
• Evolutionary operators for the Hamiltonian completion problem
• Recognizing DAGs with page-number 2 is NP-complete
• Crossing-optimal acyclic HP-completion for outerplanar \(st\)-digraphs
• On the upward book thickness problem: combinatorial and complexity results
• Crossing-free acyclic Hamiltonian path completion for planar \(st\)-digraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3605502)