Towards Characterizing Strict Outerconfluent Graphs

Abstract

Confluent drawings of graphs are geometric representations in the plane, in which vertices are mapped to points, but edges are not drawn as individually distinguishable geometric objects. Instead, an edge is represented by the presence of a smooth curve between two vertices in a system of arcs and junctions. More formally, a confluent drawing D of a graph G = (V, E) consists of a set of points representing the vertices, a set of junction points, and a set of smooth arcs, such that each arc starts and ends at a vertex point or a junction, no two arcs intersect (except at common endpoints), and all arcs meeting in a junction share the same tangent line in the junction point. There is an edge (u, v) ∈ E if and only if there is a smooth path from u to v in D that does not pass through any other vertex. Confluent drawings were introduced by Dickerson et al. [1], who identified classes of graphs that admit or that do not admit confluent drawings. Later, variations such as strong and tree confluency [6], as well as ∆-confluency [2] were introduced. Confluent drawings have further been used for layered drawings [3] and for drawing Hasse diagrams [5]. The complexity of the recognition problem for graphs that admit a confluent drawing remains open. Eppstein et al. [4] defined strict confluent drawings, in which every edge of the graph must be represented by a unique smooth path. They showed that for general graphs it is NP-complete to decide whether a strict confluent drawing exists. A strict confluent drawing is called strict outerconfluent if all vertices lie on the boundary of a (topological) disk that contains the strict confluent drawing. For a given cyclic vertex order, Eppstein et al. [4] presented a constructive poly-time algorithm for testing the existence of a strict outerconfluent drawing. Without a given vertex order the recognition complexity as well as a characterization of the graphs admitting such drawings remained open. We present first results towards characterizing the strict outerconfluent (SOC) graphs by examining potential sub- and super-classes of SOC graphs.