Quotation Leydold, Josef. 2011. Convex Cycle Bases. 7th Slovenian International Conference on Graph Theory, Bled, Slowenien, 20.06.-24.06..




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.


Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
Type of publication Paper presented at an academic conference or symposium
Language English
Title Convex Cycle Bases
Event 7th Slovenian International Conference on Graph Theory
Year 2011
Date 20.06.-24.06.
Country Slovenia
Location Bled


Leydold, Josef (Details)
Institute for Statistics and Mathematics IN (Details)
Google Scholar: Search