TL;DR
This paper introduces the concept of "unbent collections" for orthogonal graph drawings, where each edge must be drawn straight in at least one drawing within a collection. The authors establish that any 4-regular planar graph can be represented with at most three such drawings and provide an NP-completeness result for minimizing bends in these collections, along with approximation algorithms.
What Problem Does This Paper Address?
Graph drawing aims to create visualizations that effectively convey graph structure. For orthogonal drawings, key objectives are minimizing edge crossings and bends. These goals often conflict: reducing crossings might introduce more bends, and vice versa. This paper tackles the challenge of representing a graph with multiple orthogonal drawings, where each drawing might optimize for different aspects or ensure certain edges are drawn without bends. Specifically, they focus on "unbent collections," a novel concept where every edge of the original graph must appear as a straight line (no bends) in at least one drawing within the collection. This addresses the need for representations that guarantee certain edges are visualized in their simplest form, potentially improving readability or analysis.
Methods
The authors leverage existing techniques from orthogonal graph drawing, particularly Roberto Tamassia's flow network formulation for bend minimization. They extend this by considering collections of drawings.
- Minimizing Collection Size: They build upon Schnyder's algorithm for planar triangulations and Nash-Williams' theorem on graph arboricity to show that any plane 4-graph can be represented by an unbent collection of size at most 3. They also characterize graphs that can be represented with size 2 collections using a new concept of "balanced 2-edge-coloring."
- Minimizing Bends: For minimizing the total number of bends across all drawings in an unbent collection, they prove NP-hardness by reducing from a specialized SAT problem. They then develop a 3-approximation algorithm based on star arboricity and flow networks.
- Special Case (Triconnected Cubic Graphs): For this specific class of graphs, they devise a linear-time algorithm to compute an optimal unbent collection of size 2, achieving the minimum possible number of bends. This involves a detailed analysis of "demanding cycles" and a sophisticated placement strategy for "dummies" (subdivision vertices) to ensure all cycles are "good" (not bad cycles).
Datasets
Not discussed in the paper. The work is theoretical and algorithmic, focusing on graph properties rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- The Power of Collections: The core idea is that by using multiple drawings, we can achieve properties (like straight edges for all edges) that are impossible in a single drawing. This shifts the focus from optimizing a single drawing to orchestrating a set of drawings.
- Unbent Collections as a Guarantee: The "unbent" property provides a strong guarantee: every edge gets its simplest representation in at least one drawing. This is a novel way to think about graph drawing quality.
- Balanced 2-Edge-Coloring: The introduction of this concept provides a crucial characterization for when an unbent collection of size 2 is possible, linking combinatorial properties of the graph to drawing properties.
- Demanding Cycles and Lower Bounds: The detailed analysis of "demanding cycles" in triconnected cubic graphs is key to deriving tight lower bounds for the unbent bend number, revealing a complex interplay between graph structure and drawing constraints.
- NP-Hardness for Bend Minimization: The proof of NP-hardness for minimizing bends in unbent collections highlights the inherent difficulty of this optimization problem, necessitating approximation algorithms.
Key Results
- Upper Bound on Collection Size: Every plane 4-graph admits an unbent collection of size at most 3, computable in almost-linear time.
- Characterization for Size 2: A plane 4-graph admits an unbent collection of size 2 if and only if it admits a balanced 2-edge-coloring.
- NP-Completeness: Deciding whether a plane 4-graph admits an unbent collection with at most k bends is NP-complete.
- Approximation Algorithm: A 3-approximation algorithm is provided for minimizing the total number of bends in an unbent collection.
- Optimal Solution for Triconnected Cubic Graphs: For plane triconnected cubic graphs, an algorithm computes an optimal unbent collection of size 2 with the minimum number of bends in linear time.
Limitations and Future Work
- General Graphs for Bend Minimization: While an approximation algorithm is given for general 4-graphs, the exact minimum bend problem remains NP-hard.
- Efficiency of Size 2 Characterization: The paper mentions that testing the sufficient condition for size 2 collections (Proposition 4) naively takes exponential time, suggesting a need for more efficient methods.
- Open Questions: The authors pose several open questions:
- Can we efficiently decide, for a given 4-plane graph G, whether un(G) = 2 or un(G) = 3?
- Does every plane 4-graph G admit an unbent collection of size un(G) that minimizes tbn(G)?
- Exploring other graph classes (e.g., non-triconnected cubic graphs, bipartite planar graphs, series-parallel 4-graphs) for unbent collections.
- Investigating variants of unbent collections, such as "mutable" (variable embedding) or "uniform" (fixed but not given) collections.
Summary updated