Constrained Outer-String Representations

Therese Biedl, Sabine Cornelsen, Jan Kratochvíl, Ignaz RutterGD 2024 · DOI

TL;DR

This paper investigates "constrained outer-string representations" of graphs, where vertex curves must intersect the boundary of a disk in a specific cyclic order. The authors provide characterizations and efficient algorithms for when graphs, chordal graphs, trees, and cycles admit such representations, particularly focusing on outer-1-string representations (where curves intersect at most once). This work contributes to understanding the geometric realizability of graphs under specific ordering constraints.

What Problem Does This Paper Address?

The paper delves into the realm of string representations of graphs, a way to visualize graphs where each vertex is a curve, and edges exist between vertices whose curves intersect. A specific type, outer-string representations, confines these curves within a disk, with at least one endpoint of each curve on the disk's boundary. The challenge arises when we impose an additional constraint: the cyclic order of these boundary endpoints must match a given order of vertices. This "constrained" version is the focus.

Furthermore, the paper considers outer-1-string representations, a stricter form where any two curves intersect at most once. This adds another layer of complexity. The core problem is to determine efficiently whether a given graph, along with a specified cyclic vertex order, can be represented in these constrained ways, and to characterize which graphs and structures (like trees and cycles) admit such representations. This is crucial for understanding the geometric complexity of graphs under ordering constraints, which has implications in areas like computational geometry and graph drawing.

Methods

The paper employs a combination of theoretical characterizations and algorithmic approaches.

  • Characterizations: The authors establish necessary and sufficient conditions for graphs and specific graph classes (chordal graphs, trees, cycles) to admit constrained outer-string and outer-1-string representations. These characterizations often involve identifying forbidden substructures (e.g., interleaved independent edges, complements of cycles).
  • Inductive Proofs: Many proofs rely on induction, breaking down the problem into smaller instances. For instance, when dealing with chordal graphs, they use a strategy of removing simplicial vertices.
  • Algorithmic Approaches: For trees and cycles, the paper develops polynomial-time (and in some cases, linear-time) algorithms. These algorithms often involve a recursive or post-order traversal of the graph, applying reduction rules to simplify the problem or identify obstructions.
  • Obstruction Identification: A key algorithmic technique is the identification of specific "obstructions" – substructures that guarantee a graph cannot be represented in the desired way. The algorithms either find such an obstruction or construct a valid representation.
  • Shape Restrictions: The paper also explores specific curve shapes, like L-shaped and U-shaped polylines, and investigates their realizability under constrained orders.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Complements of Chordal Graphs for General Outer-String: A graph admits a constrained outer-string representation for any cyclic order if and only if its complement is chordal. This is a powerful structural characterization.
  • Forbidden Substructures for Chordal Graphs: For chordal graphs with a fixed cyclic order, the condition for admitting a constrained outer-string representation simplifies to not containing interleaved independent edges.
  • Obstructions for Outer-1-String: The complexity for outer-1-string representations (curves intersect at most once) is significantly higher. For trees, the paper identifies three types of obstructions: pair-obstructions, bridge-obstructions, and path-obstructions. The absence of these is necessary and sufficient.
  • L-shaped vs. U-shaped Representations: While not all trees and cycles admitting constrained outer-1-string representations can be drawn with L-shaped curves, they can always be drawn with U-shaped curves. This highlights how subtle changes in curve shape can affect realizability.
  • Efficient Algorithms: The development of linear-time and quadratic-time algorithms for testing these properties demonstrates that these geometric constraints can be checked efficiently for specific graph classes.

Key Results

  • Theorem 2: A graph admits a constrained outer-string representation for any cyclic ordering of its vertices iff its complement is chordal.
  • Theorem 3: A chordal graph G with a cyclic order of vertices admits a constrained outer-string representation iff no two independent edges are interleaved.
  • Theorem 12: A tree instance (G, U) admits a constrained outer-1-string representation iff it contains no pair-obstruction, bridge-obstruction, and path-obstruction. A linear-time algorithm exists for this.
  • Corollary 20: An ordered graph with n vertices can be tested for a constrained L-shaped outer-1-string representation in O(n²) time.
  • Theorem 21: Characterizes when a simple cycle with a given cyclic order admits a constrained outer-1-string representation, relating it to interleaved independent edges and extended complements of 5-cycles.

Limitations and Future Work

  • General Graphs for Outer-1-String: The paper focuses on trees and cycles for constrained outer-1-string representations. The complexity for general graphs remains an open question.
  • L-shaped Representations for Cycles: While U-shapes suffice for cycles, L-shaped representations are not always possible even when a constrained outer-1-string representation exists. The paper doesn't fully characterize when L-shapes are possible for cycles.
  • Open Questions: The authors explicitly pose several open problems:
  • What is the complexity of testing for outer-1-string, constrained outer-1-string, or constrained outer-string representations for general graphs?
  • Can these problems be solved efficiently for cacti or graphs with constant treewidth?
  • Can it be tested efficiently whether an ordered graph admits a constrained U-shaped outer-1-string representation?
  • A variant where each vertex has a set of allowed anchor points is also proposed for further study.

Summary updated

BibTeX
@inproceedings{biedl2024constrained,
  author = {Therese Biedl and Sabine Cornelsen and Jan Kratochvíl and Ignaz Rutter},
  title = {{Constrained Outer-String Representations}},
  booktitle = {GD},
  year = {2024},
  doi = {10.4230/lipics.gd.2024.10},
}
Figure