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
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
