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 , pp. 318-328(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_32).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_32
Classifications: Z Theory > Z.500 Representations
URI: http://gdea.informatik.uni-koeln.de/id/eprint/598

Actions (login required)

View Item View Item