FACET DETECTION AND VISUALIZING LOCAL STRUCTURE IN GRAPHS

摘要

In this paper we present an algorithm for facet detection in graphs. We define the facets as simple cycles in the graph minimizing the length. Our algorithm detects the local structure of simple cycles intersecting in a particular vertex of the graph. For this purpose, we reduce the problem to an instance of the Traveling Salesman in an induced co-cyclic graph and use a method inspired from the minimum spanning tree to construct a circuit solution. Our algorithm found a correct solution for most of the cases we tested it on.