NP-Completeness of st-Orientations for Plane Graphs

DOI10.1007/978-3-642-03409-1_27MaRDI QIDQ3183620zbMATH OpenOpenAlexFDO

Authors Sadish Sadasivam, Huaming Zhang

Publication date 20 October 2009

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• NP-completeness of st-orientations for plane graphs
• Parameterized st-Orientations of Graphs: Algorithms and Experiments
• Optimal st-Orientations for Plane Triangulations
• Optimal st-orientations for plane triangulations
• Algorithms for computing a parameterized \(st\)-orientation

Cited in

(10)

• Optimal st-orientations for plane triangulations
• Planar orientations with low out-degree and compaction of adjacency matrices
• NP-completeness of st-orientations for plane graphs
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• Parameterized st-Orientations of Graphs: Algorithms and Experiments
• The complexity of two graph orientation problems
• On Minimizing One Dimension of Some Two-Dimensional Geometric Representations of Plane Graphs
• Optimal st-Orientations for Plane Triangulations
• $st$-Orientations with Few Transitive Edges
• Algorithms for computing a parameterized \(st\)-orientation

This page was built for publication: NP-Completeness of st-Orientations for Plane Graphs

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