Time complexity to know if an edge exists between two vertices of an incidence matrix? I have a directed graph say $G$, having $E$ edges and $V$ vertices, I want to know if between two particular vertices say $u$ and $v$ there exists an edge or not. The graph is represented as an incidence matrix.
I am checking for every edge if it is the one that exists between $u$ and $v$. In the worst case there wont be any edge between the vertices, hence the complexity comes out to be $O(E)$. I have 2 questions. 
Is there a faster way to check?
Is there anyway to make the complexity $O(V)$?
 A: If you are going to check edge existence only few times, why care about the time complexity? If you are going to check it regularly, why don't use some better data structure (adjacency matrix, as already mentioned).
But even with an incidence matrix, you can probably do better then O(E) and still call it an incidence matrix :).
Given an incidence matrix with row for each vertex and column for each edge, most of the elements of the matrix will be zeroes (there will be at most V nonzero elements on each row). That's called sparse matrix and it can be stored in the memory in some space efficient way, which also allows "skipping" long sequences of zeroes in constant time.
For example with simple list of lists representation, you have a list of pairs (columnindex, value) ordered by columnindex for each row, one pair for each nonzero element. In our case, just check rows u and v, whether they have an item with same columnindex. As they are both ordered and both have less then V items, it can be done in O(V).
Of course, it's a trade-off. Some other operations are less efficient if matrix is stored this way.
