On Strict (Outer-)Confluent Graphs

Henry Förster, Robert Ganian, Fabian Klute, Martin Nöllenburg

Abstract

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like ($\Delta$-)SOC graphs have bounded cliquewidth.

Introduction

In complex network visualizations, drawing every edge as a straight line often results in unreadable "hairballs" due to excessive overlaps. Confluent drawing addresses this by "bundling" edges: adjacencies are represented by smooth paths through a system of junctions and arcs, similar to a train track map. This paper focuses on strict confluency, a variant where every edge must be represented by a unique smooth path. While this uniqueness makes the graphs more mathematically tractable, it introduces new challenges in characterization and recognition.

A strict confluent drawing showing vertices connected via a system of junctions and smooth arcs.

Structural Relationships and Hierarchy

A primary contribution of this work is placing SC and SOC graphs within the broader hierarchy of geometric graph theory. By tracing "junction trees" in a confluent drawing, the authors demonstrate that strictness allows these drawings to be transformed into intersection models. Specifically, every SC graph is shown to be a string graph (where vertices are curves and edges are intersections), and every SOC graph is an outer-string graph.

Furthermore, the paper establishes that all unit-interval graphs—a fundamental class in graph theory—admit a strict confluent drawing. This is proven through a constructive algorithm that decomposes the graph into cliques and routes arcs through a structured junction system.

The hierarchy of strict confluent (SC) and strict outer-confluent (SOC) graphs relative to other classes like string and unit-interval graphs.

Algorithmic and Game-Theoretic Properties

The authors investigate the structural properties of SOC graphs using the "Cops and Robbers" game. They prove that the cop number of SOC graphs is exactly two, indicating a high degree of "planarity-like" behavior and connectivity. This is a significant refinement compared to the broader class of outer-string graphs, which can have higher cop numbers.

Additionally, the paper explores the algorithmic complexity of these graphs. By focusing on tree-like $\Delta$-SOC graphs—where the bundling structure topologically forms a tree and allows 3-way smooth merges ($\Delta$-junctions)—the authors prove a bounded cliquewidth of at most 16. This result is crucial because it implies that many NP-hard problems can be solved in polynomial time for this specific subclass.

Characterization of Bipartite SOC Graphs

In the bipartite case, the paper provides a definitive characterization: a bipartite graph is strict outer-confluent if and only if it is a "domino-free bipartite permutation graph." This result bridges the gap between visualization techniques and classic forbidden-subgraph theory.

Conclusion and Future Work

While this work significantly advances the understanding of strict confluent graphs, several questions remain. The complexity of the general recognition problem (deciding if an arbitrary graph is SOC) is still unknown. Future research may also explore whether the unit-length restriction for interval graphs can be removed and if the string graph inclusion can be extended to non-strict confluent drawings.

Summary updated

Abstract

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like ($\Delta$-)SOC graphs have bounded cliquewidth.
BibTeX
@inproceedings{forster2019strict,
  author = {Henry Förster and Robert Ganian and Fabian Klute and Martin Nöllenburg},
  title = {{On Strict (Outer-)Confluent Graphs}},
  booktitle = {GD},
  year = {2019},
  doi = {10.1007/978-3-030-35802-0\_12},
}
Figure