NP-completeness of st-orientations for plane graphs

DOI10.1016/j.tcs.2009.11.006zbMath1213.05058OpenAlexW2047890727MaRDI QIDQ2268858

Huaming Zhang, Sadish Sadasivam

Publication date: 9 March 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.11.006

zbMATH Keywords

NP-completeplane graph\(st\)-orientation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Complexity of the multi-service center problem ⋮ Compact visibility representation of 4-connected plane graphs ⋮ Complexity of the multi-service center problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for four-partitioning four-connected planar graphs
• Algorithms for computing a parameterized \(st\)-orientation
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Computing an st-numbering
• Algorithms for area-efficient orthogonal drawing
• On Finding the Rectangular Duals of Planar Triangular Graphs
• Directional Routing via Generalized st-Numberings
• Graph Drawing

This page was built for publication: NP-completeness of st-orientations for plane graphs