Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

2.5-Connectivity: Unique Components, Critical Graphs, and Applications

: Heinrich, I.; Heller, T.; Schmidt, E.; Streicher, M.


Adler, I.:
Graph-Theoretic Concepts in Computer Science. 46th International Workshop, WG 2020 : Leeds, UK, June 24-26, 2020; Revised Selected Papers, Online
Cham: Springer Nature, 2020 (Lecture Notes in Computer Science 12301)
ISBN: 978-3-030-60439-4 (Print)
ISBN: 978-3-030-60440-0 (Online)
ISBN: 978-3-030-60441-7
International Workshop on Graph-Theoretic Concepts in Computer Science (WG) <46, 2020, Online>
Conference Paper
Fraunhofer ITWM ()

If a biconnected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every biconnected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a tree-structure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle packings.