Train Tracks and Confluent Drawings |
| |
Authors: | Peter Hui Michael J Pelsmajer Marcus Schaefer Daniel Stefankovic |
| |
Affiliation: | (1) Department of Computer Science, DePaul University, Chicago, IL 60604, USA;(2) Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL 60616, USA;(3) Computer Science Department, University of Rochester, Rochester, NY 14627-0226, USA |
| |
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, and we show that this class coincides with the (6,2)-chordal bipartite
graphs. Finally, we define outerconfluent graphs and identify the bipartite permutation graphs as a natural subclass. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|