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.
20 Juni 2011 → 24 Juni 2011
7th Slovenian International Conference on Graph Theory