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.

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
ID Code:598

Repository Staff Only: item control page

References

Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999.

Matthew T. Dickerson, David Eppstein, Michael T. Goodrich, and Jeremy Yu Meng. Confluent drawings: visualizing non-planar diagrams in a planar way. In Proc. 11th Int. Symp. Graph Drawing (GD 2003), Lecture Notes in Computer Science. Springer-Verlag, 2003.

Davis Eppstein, 2004. personal communication.

Michael R. Garey and David S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312-316, 1983.

M. Golomic and C. F. Goss. Perfect elimination and chordal bipartite graphs. J. Graph Theory, 2:155-163, 1978.

R. C. Penner and J. L. Harer. Combinatorics of train tracks, volume 125 of Annals of mathematics studies. Princeton University Press, 1992.

Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic. Recognizing string graphs in NP. J. Comput. System Sci., 67(2):365-380, 2003. Special issue on STOC2002 (Montreal, QC).