rust_igraph/algorithms/properties/
is_outerplanar.rs

1//! Outerplanar graph predicate (ALGO-PR-129).
2//!
3//! A graph is outerplanar if it can be embedded in the plane with all
4//! vertices on the outer face. Equivalently, a graph is outerplanar if
5//! and only if it has no `K_4` minor and no `K_{2,3}` minor.
6//!
7//! We check: series-parallel (no `K_4` minor) + no `K_{2,3}` minor.
8//! The `K_{2,3}` check uses a modified SP reduction that tags edges as
9//! *original* or *synthetic* (created by series contraction). Three or
10//! more synthetic parallel edges between the same pair reveal a
11//! `K_{2,3}` minor.
12//!
13//! Every forest and every cycle is outerplanar. Every outerplanar
14//! graph is series-parallel (but not vice versa: `K_{2,3}` is
15//! series-parallel but not outerplanar).
16//!
17//! Directed graphs are treated as undirected.
18
19use crate::algorithms::properties::is_series_parallel::is_series_parallel;
20use crate::core::{Graph, IgraphResult};
21
22/// Check whether a graph is outerplanar.
23///
24/// Uses the characterization: outerplanar iff no `K_4` minor
25/// (series-parallel) and no `K_{2,3}` minor.
26///
27/// Directed graphs are treated as undirected.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, is_outerplanar};
33///
34/// // Cycle C_5: outerplanar
35/// let mut g = Graph::with_vertices(5);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// g.add_edge(2, 3).unwrap();
39/// g.add_edge(3, 4).unwrap();
40/// g.add_edge(4, 0).unwrap();
41/// assert!(is_outerplanar(&g).unwrap());
42///
43/// // K_4: NOT outerplanar (has K_4 minor)
44/// let mut g = Graph::with_vertices(4);
45/// for i in 0..4u32 {
46///     for j in (i+1)..4 {
47///         g.add_edge(i, j).unwrap();
48///     }
49/// }
50/// assert!(!is_outerplanar(&g).unwrap());
51/// ```
52pub fn is_outerplanar(graph: &Graph) -> IgraphResult<bool> {
53    let n = graph.vcount();
54    if n <= 3 {
55        return is_series_parallel(graph);
56    }
57
58    if !is_series_parallel(graph)? {
59        return Ok(false);
60    }
61
62    // Quick global edge bound: outerplanar => edges <= 2n - 3.
63    let e = graph.ecount();
64    let n_usize = n as usize;
65    if e > 2 * n_usize - 3 {
66        return Ok(false);
67    }
68
69    has_no_k23_minor(graph)
70}
71
72/// Detect `K_{2,3}` minor via SP reduction with edge tagging.
73///
74/// Each edge is tagged as *original* (from the input graph) or
75/// *synthetic* (created when a degree-2 vertex is series-contracted).
76/// A synthetic edge represents a path with at least one internal
77/// vertex. If three or more synthetic parallel edges accumulate
78/// between any vertex pair, that certifies a `K_{2,3}` minor: the
79/// two endpoints are the hubs, and one internal vertex from each of
80/// the three paths forms the three branch vertices.
81fn has_no_k23_minor(graph: &Graph) -> IgraphResult<bool> {
82    let n = graph.vcount() as usize;
83
84    // K_{2,3} minor needs >= 5 vertices.
85    if n < 5 {
86        return Ok(true);
87    }
88
89    let mut adj: Vec<Vec<(usize, bool)>> = vec![vec![]; n];
90    for v in 0..graph.vcount() {
91        let nbrs = graph.neighbors(v)?;
92        for &w in &nbrs {
93            let vv = v as usize;
94            let ww = w as usize;
95            if vv < ww {
96                adj[vv].push((ww, false));
97                adj[ww].push((vv, false));
98            }
99        }
100    }
101
102    Ok(!k23_reduce_check(&mut adj, n))
103}
104
105/// Returns `true` if a `K_{2,3}` minor is detected.
106fn k23_reduce_check(adj: &mut [Vec<(usize, bool)>], n: usize) -> bool {
107    loop {
108        // Check for >= 3 synthetic parallel edges between any pair.
109        for edges in adj.iter() {
110            let mut syn_count = std::collections::HashMap::new();
111            for &(w, syn) in edges {
112                if syn {
113                    *syn_count.entry(w).or_insert(0usize) += 1;
114                }
115            }
116            for &count in syn_count.values() {
117                if count >= 3 {
118                    return true;
119                }
120            }
121        }
122
123        let mut changed = false;
124
125        // Peel vertices with <= 1 distinct neighbor.
126        for v in 0..n {
127            if adj[v].is_empty() {
128                continue;
129            }
130            let distinct = distinct_neighbors(&adj[v]);
131            if distinct.len() <= 1 {
132                changed = true;
133                for &w in &distinct {
134                    adj[w].retain(|&(x, _)| x != v);
135                }
136                adj[v].clear();
137            }
138        }
139
140        // Series reduce: vertices with exactly 2 distinct neighbors.
141        for v in 0..n {
142            if adj[v].is_empty() {
143                continue;
144            }
145            let distinct = distinct_neighbors(&adj[v]);
146            if distinct.len() == 2 {
147                let a = distinct[0];
148                let b = distinct[1];
149                changed = true;
150                adj[v].clear();
151                adj[a].retain(|&(x, _)| x != v);
152                adj[b].retain(|&(x, _)| x != v);
153                adj[a].push((b, true));
154                adj[b].push((a, true));
155            }
156        }
157
158        if !changed {
159            break;
160        }
161    }
162
163    false
164}
165
166fn distinct_neighbors(edges: &[(usize, bool)]) -> Vec<usize> {
167    let mut d: Vec<usize> = edges.iter().map(|&(w, _)| w).collect();
168    d.sort_unstable();
169    d.dedup();
170    d
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176
177    #[test]
178    fn empty_graph() {
179        let g = Graph::with_vertices(0);
180        assert!(is_outerplanar(&g).unwrap());
181    }
182
183    #[test]
184    fn single_vertex() {
185        let g = Graph::with_vertices(1);
186        assert!(is_outerplanar(&g).unwrap());
187    }
188
189    #[test]
190    fn single_edge() {
191        let mut g = Graph::with_vertices(2);
192        g.add_edge(0, 1).unwrap();
193        assert!(is_outerplanar(&g).unwrap());
194    }
195
196    #[test]
197    fn triangle() {
198        let mut g = Graph::with_vertices(3);
199        g.add_edge(0, 1).unwrap();
200        g.add_edge(1, 2).unwrap();
201        g.add_edge(2, 0).unwrap();
202        assert!(is_outerplanar(&g).unwrap());
203    }
204
205    #[test]
206    fn path() {
207        let mut g = Graph::with_vertices(5);
208        g.add_edge(0, 1).unwrap();
209        g.add_edge(1, 2).unwrap();
210        g.add_edge(2, 3).unwrap();
211        g.add_edge(3, 4).unwrap();
212        assert!(is_outerplanar(&g).unwrap());
213    }
214
215    #[test]
216    fn cycle_c5() {
217        let mut g = Graph::with_vertices(5);
218        g.add_edge(0, 1).unwrap();
219        g.add_edge(1, 2).unwrap();
220        g.add_edge(2, 3).unwrap();
221        g.add_edge(3, 4).unwrap();
222        g.add_edge(4, 0).unwrap();
223        assert!(is_outerplanar(&g).unwrap());
224    }
225
226    #[test]
227    fn k4_not_outerplanar() {
228        let mut g = Graph::with_vertices(4);
229        for i in 0..4u32 {
230            for j in (i + 1)..4 {
231                g.add_edge(i, j).unwrap();
232            }
233        }
234        assert!(!is_outerplanar(&g).unwrap());
235    }
236
237    #[test]
238    fn k23_not_outerplanar() {
239        // K_{2,3} is series-parallel but NOT outerplanar.
240        let mut g = Graph::with_vertices(5);
241        g.add_edge(0, 2).unwrap();
242        g.add_edge(0, 3).unwrap();
243        g.add_edge(0, 4).unwrap();
244        g.add_edge(1, 2).unwrap();
245        g.add_edge(1, 3).unwrap();
246        g.add_edge(1, 4).unwrap();
247        assert!(!is_outerplanar(&g).unwrap());
248    }
249
250    #[test]
251    fn diamond_outerplanar() {
252        // Diamond: K_4 minus one edge. 4 vertices, 5 edges. Outerplanar.
253        let mut g = Graph::with_vertices(4);
254        g.add_edge(0, 1).unwrap();
255        g.add_edge(0, 2).unwrap();
256        g.add_edge(0, 3).unwrap();
257        g.add_edge(1, 2).unwrap();
258        g.add_edge(1, 3).unwrap();
259        assert!(is_outerplanar(&g).unwrap());
260    }
261
262    #[test]
263    fn star() {
264        let mut g = Graph::with_vertices(5);
265        g.add_edge(0, 1).unwrap();
266        g.add_edge(0, 2).unwrap();
267        g.add_edge(0, 3).unwrap();
268        g.add_edge(0, 4).unwrap();
269        assert!(is_outerplanar(&g).unwrap());
270    }
271
272    #[test]
273    fn tree() {
274        let mut g = Graph::with_vertices(6);
275        g.add_edge(0, 1).unwrap();
276        g.add_edge(1, 2).unwrap();
277        g.add_edge(1, 3).unwrap();
278        g.add_edge(3, 4).unwrap();
279        g.add_edge(3, 5).unwrap();
280        assert!(is_outerplanar(&g).unwrap());
281    }
282
283    #[test]
284    fn edgeless() {
285        let g = Graph::with_vertices(5);
286        assert!(is_outerplanar(&g).unwrap());
287    }
288
289    #[test]
290    fn maximal_outerplanar_5() {
291        // Triangulated pentagon: 7 = 2*5-3 edges.
292        let mut g = Graph::with_vertices(5);
293        g.add_edge(0, 1).unwrap();
294        g.add_edge(1, 2).unwrap();
295        g.add_edge(2, 3).unwrap();
296        g.add_edge(3, 4).unwrap();
297        g.add_edge(4, 0).unwrap();
298        g.add_edge(0, 2).unwrap();
299        g.add_edge(0, 3).unwrap();
300        assert!(is_outerplanar(&g).unwrap());
301    }
302
303    #[test]
304    fn petersen_not_outerplanar() {
305        let mut g = Graph::with_vertices(10);
306        let edges = [
307            (0, 1),
308            (1, 2),
309            (2, 3),
310            (3, 4),
311            (4, 0),
312            (5, 7),
313            (7, 9),
314            (9, 6),
315            (6, 8),
316            (8, 5),
317            (0, 5),
318            (1, 6),
319            (2, 7),
320            (3, 8),
321            (4, 9),
322        ];
323        for (u, v) in edges {
324            g.add_edge(u, v).unwrap();
325        }
326        assert!(!is_outerplanar(&g).unwrap());
327    }
328
329    #[test]
330    fn directed_treated_as_undirected() {
331        let mut g = Graph::new(5, true).unwrap();
332        g.add_edge(0, 1).unwrap();
333        g.add_edge(1, 2).unwrap();
334        g.add_edge(2, 3).unwrap();
335        g.add_edge(3, 4).unwrap();
336        g.add_edge(4, 0).unwrap();
337        assert!(is_outerplanar(&g).unwrap());
338    }
339
340    #[test]
341    fn disconnected_outerplanar() {
342        let mut g = Graph::with_vertices(6);
343        g.add_edge(0, 1).unwrap();
344        g.add_edge(1, 2).unwrap();
345        g.add_edge(2, 0).unwrap();
346        g.add_edge(3, 4).unwrap();
347        g.add_edge(4, 5).unwrap();
348        g.add_edge(5, 3).unwrap();
349        assert!(is_outerplanar(&g).unwrap());
350    }
351
352    #[test]
353    fn subdivided_k23_not_outerplanar() {
354        // K_{2,3} with one edge subdivided: still not outerplanar.
355        // Hubs: 0, 1. Branches: 2, 3, 4. Edge 0-2 subdivided with vertex 5.
356        let mut g = Graph::with_vertices(6);
357        g.add_edge(0, 5).unwrap();
358        g.add_edge(5, 2).unwrap();
359        g.add_edge(0, 3).unwrap();
360        g.add_edge(0, 4).unwrap();
361        g.add_edge(1, 2).unwrap();
362        g.add_edge(1, 3).unwrap();
363        g.add_edge(1, 4).unwrap();
364        assert!(!is_outerplanar(&g).unwrap());
365    }
366
367    #[test]
368    fn three_parallel_paths_with_direct_edge() {
369        // 0-1 direct + 0-2-1 + 0-3-4-1: outerplanar (only 2 K_{2,3} branches).
370        let mut g = Graph::with_vertices(5);
371        g.add_edge(0, 1).unwrap();
372        g.add_edge(0, 2).unwrap();
373        g.add_edge(2, 1).unwrap();
374        g.add_edge(0, 3).unwrap();
375        g.add_edge(3, 4).unwrap();
376        g.add_edge(4, 1).unwrap();
377        assert!(is_outerplanar(&g).unwrap());
378    }
379}
rust_igraph/algorithms/properties/is_outerplanar.rs

rust_igraph/algorithms/properties/
is_outerplanar.rs
