<p>Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a planar graph can easily be computed by finding an embedding and taking the faces of the graph as the cycle basis.</p>

<p>I am interested in the more general algebraic problem. Let <span class="math-container">$V$</span> be some <span class="math-container">$n$</span>-dimensional vector space over <span class="math-container">$\mathbb{Z}_2$</span> that has a 2-basis. That is, there exists a set of linearly independent vectors <span class="math-container">$\{b_1,\dots,b_n\}$</span> such that the matrix <span class="math-container">$B$</span>, whose columns are these vectors, contains at most 2 non-zero entries in each row. If I am given an arbitrary basis for <span class="math-container">$V$</span> is there an algorithm to find 2-basis?</p>

<p>I'm not concerned with the running time, so I'd still be interested in seeing an inefficient approach. Are there any planarity testing algorithms that solve the algebraic problem? Has this problem been studied in any other contexts?</p>

CC BY-SA 4.0
2019-12-10T04:02:59.730Z
Put $B$ into column echelon form. Reorder the rows (this won't change the answer to the question of existence of a 2-basis) so that it now has the form $B' = \begin{bmatrix} I_n \\ A \end{bmatrix}$ for some matrix $A$. Now, any basis for the same column space is a linear combination of the columns of $B'$. In order to have at most 2 nonzeros per row, by considering just the $I_n$ part this means that each element in the 2-basis is the sum of at most 2 columns of $B'$. You can consider all $n^2$ such linear combinations. Next I'm not sure...maybe something greedy or almost-greedy works?
Joshua Grochow
CC BY-SA 4.0
2019-12-10T23:51:31.447Z
I'm not sure it is true that each element in the 2-basis is the sum of at most two columns of $B'$. Let $B'_i$ be the $i$th row of $B'$ then the matrix $\left[\sum_{i=1}^n B'_i, B'_1, \dots, B'_{n-1} \right]$ may have the 2-basis property (it does in the first $n$ rows), but the first column is the sum of more than two columns of $B'$.
Will
CC BY-SA 4.0
2019-12-11T03:44:00.410Z
I'm a little confused by your example. Are we mixing up rows/columns?
Joshua Grochow
CC BY-SA 4.0
2019-12-11T03:47:55.687Z
I mixed up the rows and columns. I meant to say that $B'_i$ is the $i$th column of $B'$.
Will
CC BY-SA 4.0
2019-12-11T05:33:50.327Z
Ah yes, you're right. What I should've said is that each column $B'_i$ appears in at most 2 basis elements in any 2-basis. So we get a 2-basis from $B'$ as $B' G$ for some $G \in GL(n,\mathbb{F}_2)$ with the property that each column of $G$ contains at most 2 ones. (And we may as well restrict to the case where $G_{ii} = 1$ for all $i$, WLOG.) While any one column of $G$ only has $n$ choices, there are still quite a lot of possibilities for $G$. But this at least brings us back to: each column (now, of $G$) has a small number of choices, maybe we can do something greedy-like...
Joshua Grochow
CC BY-SA 4.0
2019-12-11T19:38:03.853Z
Yes, each column of $B'_i$ appears in at most two elements of any 2-basis. However, doesn't this imply that $G$ must have at most two ones in each row instead of each column? By restricting each column to have at most two non-zero entries we are only considering bases where each element is the linear combination of at most two columns of $B'$.
Will
<graph-theory><graph-algorithms><linear-algebra><planar-graphs>
Algebraic methods for testing planarity
Will
# Algebraic methods for testing planarity

(Asked by: username_0 on 2019-12-09)

Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a planar graph can easily be computed by finding an embedding and taking the faces of the graph as the cycle basis.

I am interested in the more general algebraic problem. Let $V$ be some $n$-dimensional vector space over $\mathbb{Z}\_2$ that has a 2-basis. That is, there exists a set of linearly independent vectors $\{b\_1,\dots,b\_n\}$ such that the matrix $B$, whose columns are these vectors, contains at most 2 non-zero entries in each row. If I am given an arbitrary basis for $V$ is there an algorithm to find 2-basis?

I'm not concerned with the running time, so I'd still be interested in seeing an inefficient approach. Are there any planarity testing algorithms that solve the algebraic problem? Has this problem been studied in any other contexts?

**Tags:** graph-theory, graph-algorithms, linear-algebra, planar-graphs

> **Comments:**
> **username_1**: Put $B$ into column echelon form. Reorder the rows (this won't change the answer to the question of existence of a 2-basis) so that it now has the form $B' = \begin{bmatrix} I_n \\ A \end{bmatrix}$ for some matrix $A$. Now, any basis for the same column space is a linear combination of the columns of $B'$. In order to have at most 2 nonzeros per row, by considering just the $I_n$ part this means that each element in the 2-basis is the sum of at most 2 columns of $B'$. You can consider all $n^2$ such linear combinations. Next I'm not sure...maybe something greedy or almost-greedy works?  
> **username_0**: I'm not sure it is true that each element in the 2-basis is the sum of at most two columns of $B'$. Let $B'_i$ be the $i$th row of $B'$ then the matrix $\left[\sum_{i=1}^n B'_i, B'_1, \dots, B'_{n-1} \right]$ may have the 2-basis property (it does in the first $n$ rows), but the first column is the sum of more than two columns of $B'$.  
> **username_1**: I'm a little confused by your example. Are we mixing up rows/columns?  
> **username_0**: I mixed up the rows and columns. I meant to say that $B'_i$ is the $i$th column of $B'$.  
> **username_1**: Ah yes, you're right. What I should've said is that each column $B'_i$ appears in at most 2 basis elements in any 2-basis. So we get a 2-basis from $B'$ as $B' G$ for some $G \in GL(n,\mathbb{F}_2)$ with the property that each column of $G$ contains at most 2 ones. (And we may as well restrict to the case where $G_{ii} = 1$ for all $i$, WLOG.) While any one column of $G$ only has $n$ choices, there are still quite a lot of possibilities for $G$. But this at least brings us back to: each column (now, of $G$) has a small number of choices, maybe we can do something greedy-like...  
> **username_0**: Yes, each column of $B'_i$ appears in at most two elements of any 2-basis. However, doesn't this imply that $G$ must have at most two ones in each row instead of each column? By restricting each column to have at most two non-zero entries we are only considering bases where each element is the linear combination of at most two columns of $B'$.  

---

## 0 answers

