Image Processing and Analysis with Graphs

1

Graph theory concepts and definitions used in image processing and analysis

Olivier Lézoray

Université de Caen Basse-NormandieGREYC UMR CNRS 60726 Bvd. Maréchal JuinF-14050 CAEN, FRANCE

Email: [e-mail]

Leo Grady

Department of Image Analytics and InformaticsSiemens Corporate Research755 College Rd.Princeton, NJ 08540, USA

Email: [e-mail]

CONTENTS

1.1    Introduction

1.2    Basic Graph Theory

1.3    Graph Representation

1.3.1    Matrix Representations

1.3.2    Adjacency Lists

1.4    Paths, Trees, and Connectivity

1.4.1    Walks and Paths

1.4.2    Connected Graphs

1.4.3    Shortest Paths

1.4.4    Trees and Minimum Spanning Trees

1.4.5    Maximum Flows and Minimum Cuts

1.5    Graph Models in Image Processing and ...