Working on the design of graph-coloring register allocation algorithms, Todd showed his theoretician colleague Sampath Kannan the graphs in Figure 1(a).
``Do these graphs mean anything to you?'' Todd asked.
``Sure,'' Prof. Kannan replied, ``they're series-parallel graphs.''
This was the beginning of a collaboration which resulted in a paper in the Journal of Algorithms [13].
In a similar episode, Christian showed his theoretician colleague Clark Thomborson the graph-transformation in Figure 1(b).
``Do you know what I am doing here?'' Christian asked.
``Sure,'' Prof. Thomborson soon replied, ``you're shrinking the biconnected components of the underlying (undirected) graph.''
This result became an important part of a joint paper on software watermarking [8].
It's important to note that, while in both these episodes the authors (who consider themselves ``theory-challenged'') had a pretty good grasp of the problem they were working on, they lacked knowledge of the relevant terminology. Hence, standard keyword-based search techniques would not have been of much assistance. In these episodes, the theoretical computer scientist provided the crucial problem classification that allowed the authors to conduct further bibliographical searches themselves.
