Confluent graphs capture the connection properties of
train tracks, offering a very natural
generalization of planar graphs, and---as the example of railroad
maps shows---are an important tool in graph visualization. In this
paper we continue the study of confluent graphs, introducing strongly
confluent graphs and tree-confluent graphs. We show that strongly
confluent graphs can be recognized in \NP\ (the complexity of recognizing
confluent graphs remains open). We also give a natural elimination
ordering characterization of tree-confluent graphs which shows
that they form a subclass of the chordal bipartite graphs, and
can be recognized in polynomial time.
This is joint work with Peter Hui and Daniel Stefankovic. The paper is available online: confluent.ps.