19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Convex Cycle Bases

Presented by Josef LEYDOLD
Type: Oral presentation
Track: Metric Graph Theory


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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

  • Josef LEYDOLD Institute for Statistics and Mathematics, WU Vienna