Wikipedia states that three different graph implementations are used in practice:

• Adjacency Lists
• Adjacency Matrix
• Incidence Matrix

While I was learning about these structures, an other occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are vertex pairs and the values are the weight of their edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

• Store graph: $O(m)$ space
• Add vertex: $O(1)$ time
• Add edge: $O(1)$ time
• Remove vertex: $O(n)$ time
• Remove edge: $O(1)$ time
• Query edge existence: $O(1)$ time

Since this structure has strictly better time and space complexities than all three options listed, I'm confused as to why this option isn't used in practice.

Wikipedia states that three different graph implementations are used in practice:

• Adjacency Lists
• Adjacency Matrix
• Incidence Matrix

While I was learning about these structures, another option occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are (vertex, vertex) pairs and the values are the weight of the edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

• Store graph: $O(|E|)$ space
• Add vertex: $O(1)$ time
• Add edge: $O(1)$ time
• Remove vertex: $O(|V|)$ time
• Remove edge: $O(1)$ time
• Query edge existence: $O(1)$ time

This structure has strictly better time and space complexities than all three options listed. So why isn't this implementation used in practice?

Wikipedia states that three different graph implementations that are used in practice:

• Adjacency Lists
• Adjacency Matrix
• Incidence Matrix

While I was learning about these structures, another implementation occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are (vertex, vertex) pairs and the values are the cost of their edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

• Store graph: $O(E)$
• Add vertex: $O(1)$
• Add edge: $O(1)$
• Remove vertex: $O(V)$
• Remove edge: $O(1)$
• Query cost between vertices: $O(1)$

Since this implementation has strictly better time and space complexity then all three options listed, I'm confused as to why this option isn't.

Why isn't this implementation used in practice?

Wikipedia states that three different graph implementations are used in practice:

• Adjacency Lists
• Adjacency Matrix
• Incidence Matrix

While I was learning about these structures, an other occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are vertex pairs and the values are the weight of their edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

• Store graph: $O(m)$ space
• Add vertex: $O(1)$ time
• Add edge: $O(1)$ time
• Remove vertex: $O(n)$ time
• Remove edge: $O(1)$ time
• Query edge existence: $O(1)$ time

Since this structure has strictly better time and space complexities than all three options listed, I'm confused as to why this option isn't used in practice.