Computing an st-numbering
From MaRDI portal
Publication:1231771
DOI10.1016/0304-3975(76)90086-4zbMath0341.68029OpenAlexW2091252880WikidataQ61772236 ScholiaQ61772236MaRDI QIDQ1231771
Shimon Even, Robert Endre Tarjan
Publication date: 1976
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(76)90086-4
Related Items (77)
A linear algorithm for centering a spanning tree of a biconnected graph ⋮ A linear algorithm for embedding planar graphs using PQ-trees ⋮ Optimal In-place Algorithms for Basic Graph Problems ⋮ At most single-bend embeddings of cubic graphs ⋮ A unified approach to visibility representations of planar graphs ⋮ Rectilinear planar layouts and bipolar orientations of planar graphs ⋮ Visibility representations of four-connected plane graphs with near optimal heights ⋮ The complexity of planarity testing ⋮ On Turn-Regular Orthogonal Representations ⋮ Planarity testing in parallel ⋮ AN APPLICATION OF ST-NUMBERING TO SECRET KEY AGREEMENT ⋮ A left-first search algorithm for planar graphs ⋮ Parallel ear decomposition search (EDS) and st-numbering in graphs ⋮ A linear algorithm for the maximal planar subgraph problem ⋮ Planarity Algorithms via PQ-Trees (Extended Abstract) ⋮ Approximation algorithms for the maximum bounded connected bipartition problem ⋮ Graph graphics: Theory and practice ⋮ Drawing graphs on rectangular grids ⋮ The multi-tree approach to reliability in distributed networks ⋮ An efficient parallel algorithm for planarity ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Rubber bands, convex embeddings and graph connectivity ⋮ Drawing planar graphs using the canonical ordering ⋮ On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm ⋮ Algorithms for plane representations of acyclic digraphs ⋮ A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid ⋮ A generalized greedy routing algorithm for 2-connected graphs ⋮ Algorithms for area-efficient orthogonal drawing ⋮ A better heuristic for orthogonal graph drawings ⋮ Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs ⋮ Orthogonal drawing of high degree graphs with small area and few bends ⋮ Overloaded Orthogonal Drawings ⋮ Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario ⋮ Correction to: ``Topology-hiding communication from minimal assumptions ⋮ Good acyclic orientations of 4‐regular 4‐connected graphs ⋮ Planarity for clustered graphs ⋮ \(st\)-orientations with few transitive edges ⋮ $st$-Orientations with Few Transitive Edges ⋮ Rectilinear Planarity of Partial 2-Trees ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ Visibility representations of toroidal and Klein-bottle graphs ⋮ L-visibility drawings of IC-planar graphs ⋮ O(n2) algorithms for graph planarization ⋮ The minimum size of graphs satisfying cut conditions ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Variants of the segment number of a graph ⋮ Enumerating the edge-colourings and total colourings of a regular graph ⋮ st-ordering the vertices of biconnected graphs ⋮ On the thickness of graphs of given degree ⋮ A direct linear-time planarity test for unflippable modules ⋮ Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions ⋮ An efficient distributed algorithm for centering a spanning tree of a biconnected graph ⋮ Edge-orders ⋮ A branch-and-cut approach to the crossing number problem ⋮ Algorithms for computing a parameterized \(st\)-orientation ⋮ A note on rectilinear and polar visibility graphs ⋮ Closed rectangle-of-influence drawings for irreducible triangulations ⋮ NP-completeness of st-orientations for plane graphs ⋮ The two basic linear time Planarity algorithms: Are they the same? ⋮ Balanced vertex-orderings of graphs ⋮ Unnamed Item ⋮ Edge partitions of optimal 2-plane and 3-plane graphs ⋮ Convex drawings of hierarchical planar graphs and clustered planar graphs ⋮ Unnamed Item ⋮ Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms ⋮ Greedy rectilinear drawings ⋮ Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights ⋮ The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing ⋮ A self-stabilizing algorithm for constructing a minimal reachable directed acyclic graph with two senders and two targets ⋮ A diameter-revealing proof of the Bondy-Lovász lemma ⋮ Optimal \(st\)-orientations for plane triangulations ⋮ Almost envy-free allocations with connected bundles ⋮ Bipolar orientations revisited ⋮ On Turn-Regular Orthogonal Representations ⋮ The Price of Connectivity in Fair Division ⋮ Combinatorial approximation algorithms for the maximum bounded connected bipartition problem ⋮ Finding the closed partition of a planar graph
Cites Work
This page was built for publication: Computing an st-numbering
