7
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ 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? $\endgroup$
    – Joshua Grochow
    Dec 10, 2019 at 4:02
  • $\begingroup$ 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'$. $\endgroup$
    – Will
    Dec 10, 2019 at 23:51
  • $\begingroup$ I'm a little confused by your example. Are we mixing up rows/columns? $\endgroup$
    – Joshua Grochow
    Dec 11, 2019 at 3:44
  • $\begingroup$ I mixed up the rows and columns. I meant to say that $B'_i$ is the $i$th column of $B'$. $\endgroup$
    – Will
    Dec 11, 2019 at 3:47
  • $\begingroup$ 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... $\endgroup$
    – Joshua Grochow
    Dec 11, 2019 at 5:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.