NAC-Colorings¶

NAC-colorings are a concept introduced in [GLS19] and shown to be interesting for deciding the existence and for constructing flexible realizations of graphs.

Definition 44 (NAC-coloring)

Let \(G = (V,E)\) be a graph. A NAC-coloring is a coloring of the edges in two colors, say red and blue, \(\delta \colon E(G) \rightarrow \{\tred, \tblue\}\) such that both colors occur (i.e. \(\delta\) is surjective) and every cycle of the graph is either monochromatic or it contains each color at least twice.

References: [GLS19]

Lemma 5

Let \(G=(V,E)\) be a graph and let \(\delta\colon E \rightarrow \{\tred, \tblue\}\) be a surjective edge coloring. Let \(E_r\) and \(E_b\) be the red and blue edges of \(E\), respectively. Then \(\delta\) is a NAC-coloring if and only if the connected components of the edge-induced subgraphs \(G[E_r]\) and \(G[E_b]\) are indeed vertex-induced subgraphs of G.

References: [GLS19, Thm 2.4]

Theorem 35

A connected graph has a flexible quasi-injective realization in \(\mathbb R^2\) if and only if it has a NAC-coloring.

References: [GLS19, Thm 3.1]

Theorem 36

Let \(G\) be a connected graph. If \(G\) has a stable separating set, than \(G\) has a NAC-coloring.

References: [GLS19, Thm 4.4]

Corollary 3

Let \(G\) be a connected graph with at least 2 edges. If \(G\) has a vertex that is not contained in any triangle subgraph of \(G\), than \(G\) has a NAC-coloring.

References: [GLS19, Cor 4.5]

Theorem 37

A minimally 2-rigid graph with more than one vertex has a NAC-coloring if and only if it is not a 2-tree.

References: [CGH+24, Thm 1.2]

Theorem 38

Let \(G\) be a connected graph with \(n\) vertices. If \(G\) has a flexible realization, then \(|E(G)|\leq \frac{n(n-1)}{2}-(n-2)\).

References: [GLS19, Thm 4.7]

Definition 45 (Cartesian NAC-coloring)

A NAC-coloring of \(G\) is called Cartesian, if no two distinct vertices of \(G\) are connected by both a red and blue path simultaneously.

References: [GL24]

Computations¶

It is shown that the existence problem of a NAC-coloring for a general graph is NP-complete [Gar22, Thm 3.5]. The same is true even for graphs with degree at most 5 [LL24, Thm 2.1]. Nevertheless, for many reasonably small graphs NAC-colorings can be computed.

In the implementation here we use the strategy from [LL24, Sec 3]:

Compute all NAC-mono classes
Decompose the graph into smaller edge-disjoint subgraphs by either
- taking consecutive NAC-mono classes, or by
- heuristically clustering NAC-mono classes which are close to each other [LL24, Alg 1]
Compute all NAC-colorings of these subgraphs
Merge the NAC-colorings of subgraphs to larger graphs until the full graph is obtained by either
- joining the next subgraph step by step, or by
- picking pairs of subgraphs with many common vertices

Definition 46 (NAC-mono class)

Let \(G=(V,E)\) be a graph. An equivalence relation \(\sim\) on \(E\) is called NAC-valid if for every NAC-coloring \(\delta\) of \(G\) we have that \(e_1 \sim e_2 \implies \delta(e_1) = \delta(e_2)\) for all edges \(e_1,e_2\in E\).

An equivalence class of a NAC-valid relation is called a NAC-mono class.

References: [LL24, Def 3.2]

The simplest NAC-mono class is a single edge. Also triangle-connected components form NAC-mono classes.

Definition 47 (triangle-connected component)

Let \(G=(V,E)\) be a graph. Let \(\triangle\) be the smallest equivalence relation on \(E\) such that \(e_1\triangle e_2\) if there is a 3-cycle in \(G\) containing both \(e_1\) and \(e_2\).

Clearly, \(\triangle\) is NAC-valid. The equivalence classes are called triangle-connected components or \(\triangle\)-components.

References: [GLS19, Def 4.1]

In the implementation a slightly more specific relation is used.

Definition 48 (triangle-extended class)

Let \(G=(V,E)\) be a graph. Let \(\hat \triangle\) be the smallest equivalence relation on \(E\) such that

\(e_1 \triangle e_2\) implies \(e_1 \hat \triangle e_2\)
if \(e=\{u,v\}\) and there are edges \(e_1=\{u,w_1\}, e_2=\{v,w_2\}\) with \(e_1\hat\triangle e_2\), then \(e\hat\triangle e_2\)
if \(e_1=\{u,v_1\}, e_2=\{u,v_2\}\) and there are edges \(f_1=\{v_1,w_1\}, f_2=\{v_2,w_2\}\) with \(f_1\hat\triangle f_2\), then \(e_1\hat\triangle e_2\)

Then \(\hat\triangle\) is NAC-valid. The equivalence classes are NAC-mono classes and they are called triangle-extended classes or \(\hat\triangle\)-classes.

References: [LL24]