Train Tracks and Confluent Drawings
Hui, Peter and Schaefer, Marcus and Stefankovic, Daniel (2004) Train Tracks and Confluent Drawings. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 318-328 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_32).
Full text not available from this repository.
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.
Repository Staff Only: item control page