Convex Cycle Bases

Activity: Talk or presentationScience to science

Description

The set of all Eulerian subgraphs of some undirected graph G together with the geometric difference of edges forms a vector space over GF(2). Its bases have been intensively studied and various kinds like minimal length, fundamental or robust cycle bases have been described and investigated. In this talk we introduce the concept of convex cycle bases that entirely consists of elementary cycles that are (geodetically) convex subgraphs of G, i.e., that contain all shortest path between any two vertex of these cycles. We present a polynomial time algorithm that determines whether such a cycle basis exists and returns one in case of existence. Moreover, we provide examples of graphs with convex cycle basis, including outer planar graphs, partial cubes and median graphs.
Period20 Jun 201124 Jun 2011
Event title7th Slovenian International Conference on Graph Theory
Event typeUnknown
Degree of RecognitionInternational