Graph Reconstruction from Drawings without Crossings

Hamdy Zidan and Gerik Scheuermann

Keywords

Image Segmentation, Mathematical Morphology, Graph Drawing, Graph Reconstruction

Abstract

Graphs are used for many purposes in science, engineering, and business. In some cases, graphs have been drawn by computers but digital data is lost and only the printed drawing is left. An example would be old UML diagrams of a software system. Hence, the user wants to reconstruct the graph from the drawing. This paper deals with a special case where an drawing without crossing edges of such a graph is given. The vertices of the graph are assumed to be larger regions as is typical, e.g., for UML class diagrams. We show how edge detection, morphological operators, and region growing lead to a segmentation of such images that allows to reconstruct the graph fromsuch drawings. The method is tested with some examples.

Important Links:

Go Back