Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. 2.5Connectivity: Unique Components, Critical Graphs, and Applications
 Adler, I.: GraphTheoretic Concepts in Computer Science. 46th International Workshop, WG 2020 : Leeds, UK, June 2426, 2020; Revised Selected Papers, Online Cham: Springer Nature, 2020 (Lecture Notes in Computer Science 12301) ISBN: 9783030604394 (Print) ISBN: 9783030604400 (Online) ISBN: 9783030604417 pp.352363 
 International Workshop on GraphTheoretic Concepts in Computer Science (WG) <46, 2020, Online> 

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