Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00453-006-0165-x | Algorithmica |
Keywords | Field | DocType |
Bipartite Graph,Graph Drawing,Train Track,Trivial Graph,Swap Move | Discrete mathematics,Modular decomposition,Indifference graph,Combinatorics,Computer science,Chordal graph,Graph product,Cograph,Treewidth,Pathwidth,1-planar graph | Journal |
Volume | Issue | ISSN |
47 | 4 | 0178-4617 |
Citations | PageRank | References |
8 | 0.68 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Hui | 1 | 18 | 2.73 |
| Michael J. Pelsmajer | 2 | 189 | 20.19 |
| Marcus Schaefer | 3 | 123 | 12.63 |
| Daniel Stefankovic | 4 | 243 | 28.65 |