Edge-orders
From MaRDI portal
Publication:1741850
Abstract: Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying concept behind all these orders has been shown: they can be described by a graph decomposition into parts that have a prescribed vertex-connectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1,1)-edge-orders of 2-edge-connected graphs as well as (2,1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail. As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from O(n^2) to linear time.
Recommendations
- Edge-orders
- Order filtrations of the edge algebra
- On neighbor component order edge connectivity
- Edge ranking and searching in partial orders
- Parallel ordering using edge contraction
- Bounds for the component order edge connectivity
- Component order edge connectivity -- an introduction
- On \(k\)-edge-ordered graphs
- scientific article; zbMATH DE number 4200269
- Edge routing with ordered bundles
Cites work
- scientific article; zbMATH DE number 1696542 (Why is no real title available?)
- scientific article; zbMATH DE number 1256645 (Why is no real title available?)
- scientific article; zbMATH DE number 1947389 (Why is no real title available?)
- A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
- A Reduction Method for Edge-Connectivity in Graphs
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- A counterexample for the proof of implication conjecture on independent spanning trees
- A linear-time algorithm for a special case of disjoint set union
- A linear-time algorithm for four-partitioning four-connected planar graphs
- A simple test on 2-vertex- and 2-edge-connectivity
- Certifying algorithms
- Chain Decompositions of 4-Connected Graphs
- Computing an st-numbering
- Construction sequences and certifying 3-connectedness
- Dynamic orthogonal segment intersection search
- Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
- Four edge-independent spanning trees
- Mondshein sequences (a.k.a. (2,1)-orders)
- More canonical ordering
- Small-area orthogonal drawings of 3-connected graphs
- The (3,1)-ordering for 4-connected planar triangulations
- The Mondshein Sequence
- The multi-tree approach to reliability in distributed networks
Cited in
(6)
This page was built for publication: Edge-orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741850)
