Edge-orders

DOI10.1007/S00453-018-0516-4zbMATH Open1423.68356arXiv1607.04431OpenAlexW3037154530MaRDI QIDQ1741850FDOQ1741850

Authors: Lena Schlipf, Jens M. Schmidt 

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1607.04431

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

zbMATH Keywords

linear timecanonical ordering3-edge-connected graphsedge-independent spanning treeedge-orderMondshein sequencenon-separating ear decompositionst-edge-order

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cites Work

• A simple test on 2-vertex- and 2-edge-connectivity
• A linear-time algorithm for a special case of disjoint set union
• A Reduction Method for Edge-Connectivity in Graphs
• Title not available (Why is that?)
• A linear-time algorithm for four-partitioning four-connected planar graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• The multi-tree approach to reliability in distributed networks
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Certifying algorithms
• Computing an st-numbering
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• Construction sequences and certifying 3-connectedness
• Certifying 3-edge-connectivity
• Title not available (Why is that?)
• Chain Decompositions of 4-Connected Graphs
• Title not available (Why is that?)
• The (3,1)-ordering for 4-connected planar triangulations
• The Mondshein Sequence
• Dynamic orthogonal segment intersection search
• More canonical ordering
• Small-area orthogonal drawings of 3-connected graphs
• Mondshein sequences (a.k.a. (2,1)-orders)
• A counterexample for the proof of implication conjecture on independent spanning trees
• Four edge-independent spanning trees

Cited In (6)

• Parallel ordering using edge contraction
• Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions
• Edge-orders
• Mondshein sequences (a.k.a. (2,1)-orders)
• Edges and tableaux
• Title not available (Why is that?)

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)