
15.3. SOLVING THE LABELING PROBLEM 509
a
d
c
b
Matching graph
Source
Target
Objects to be labeled
Clusters of overlapping labels
Figure 15.19 The fl ow graph . Figure taken from [KT06].
Clearly a maximum flow of graph G
flow
will produce a maximum cardinality labe l as-
signment with re spect to the set of labels encode d in the matching graph. Sophisticated
techniques can solve the maximum flow problem in O(nm log n) time [AMO93], where n is
the number of vertices and m is the number of edges of the flow graph.
This technique is summarized in the algorithm of Figur e 15.20.
Flow-based Algorithm
INPUT: A drawing Γ, a set of graphical features F in Γ to be labeled, ...