Algorithms for computing a parameterized \(st\)-orientation

DOI10.1016/j.tcs.2008.08.012zbMath1169.68039OpenAlexW2070005123MaRDI QIDQ959815

Charalampos Papamanthou, Ioannis. G. Tollis

Publication date: 12 December 2008

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

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

zbMATH Keywords

planar graphsgraph algorithmslongest path\(st\)-numberings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Overloaded Orthogonal Drawings ⋮ \(st\)-orientations with few transitive edges ⋮ $st$-Orientations with Few Transitive Edges ⋮ Compact visibility representation of 4-connected plane graphs ⋮ Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ NP-completeness of st-orientations for plane graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for four-partitioning four-connected planar graphs
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• st-ordering the vertices of biconnected graphs
• Computing an st-numbering
• Algorithms for drawing graphs: An annotated bibliography
• Algorithms for area-efficient orthogonal drawing
• Bipolar orientations revisited
• Parameterized st-Orientations of Graphs: Algorithms and Experiments
• Directional Routing via Generalized st-Numberings
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Graph Drawing

This page was built for publication: Algorithms for computing a parameterized \(st\)-orientation