Facet Detection and Visualizing Local Structure in Graphs

D. Vrajitoru (USA)


graph visualization, facet detection, traveling salesman


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 particu lar vertex of the graph. For this purpose, we reduce the problem to an instance of the Traveling Salesman in an in duced 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.

Important Links:

Go Back