In 1981 two notions of effective presentation of countable connected graphs were formulated by J. C. E. Dekker—namely, edge recognition algorithm graphs and minimal path algorithm graphs. In this paper we show that every planar graph has a minimal path algorithm presentation but that some graphs have no minimal path algorithm presentations. We introduce the notion of a shortest distance algorithm graph, show that it lies strictly between the two notions of Dekker, and show that every graph has a shortest distance algorithm presentation. Finally, in contrast to Dekker's result about minimal path algorithm graphs, we produce a shortest distance algorithm graph which has no spanning tree which is an edge recognition algorithm graph.
