CODEWITHSUNDEEP
database-designerd
chlong
chlong

Reputation: 445

Database ERD Diagrams and graph planarity

I am wondering, will an ERD diagram always be planar? I have a basic understand of database entity relationships, so currently I have been unable to think of a situation that would make an ERD Diagram non-planar.

Could someone please explain to me whether or not an ERD diagram would always be planar? If not, what situation would make it non-planar? If yes, could someone please provide a small proof of why it would always be planar?

I have searched on the internet and nobody seems to have a concrete answer for this.

Thank you.

Upvotes: 0

Views: 651

Answers (3)

Simon Righarts
Simon Righarts

Reputation: 450

From a graph theory perspective, a complete five-node graph is non-planar. Therefore, the simplest possible ERD that's non-planar is a five-entity ERD where all the entities are related to each other.

Proving whether or not any given graph is non-planar is mathematically fairly easy, but finding the optimal way to draw a graph, planar or non-planar (to minimize the number of edge crossings and, ideally, minimize edge lengths) is hard.

Upvotes: 2

Brett Rossier
Brett Rossier

Reputation: 3482

Not a graphing expert here, but just based on my cursory understanding of planar vs non-planar along with what I've experienced as a DB admin...

No, I do not believe you can assume a database ERD will always be planar. Just thinking of DBs with any amount of complexity, I don't see how you could in all cases make the diagrams planar. Any table that has more than one relationship could seem to create a scenario where lines would intersect in places other than their endpoints in a sufficiently complex ERD :\

Update: I guess if you made copies of tables that had multiple relationships, you could avoid non-planar... but I'm not sure that fits the parameters of a standard ERD.

Upvotes: 1

Jason Huntley
Jason Huntley

Reputation: 3877

Could someone please explain to me whether or not an ERD diagram would always be planar?

I think it's just a matter of generating the graph in a manner which displays the graph in its most simple readable form. Having an algorithm which strives to achieve this planar layout can help organize a complex ERD diagram so it comes closer to achieving this goal. I use Visual Paradigm to generate most my ERD diagrams; I don't think it's always the case the diagrams come out planar but they are pretty close most of the time. The exception usually occurs with one-to-one, many-to-one, and one-to-many class relationships.

If yes, could someone please provide a small proof of why it would always be planar?

If a graph is not planar, we want to draw it with as few crossings as possible, because crossings significantly decrease the readability of a drawing. Since it is very hard to find a drawing of a non planar graph with the minimum number of crossings, we use the following approach to compute a drawing with a small number of crossings. We first delete a small number of edges from the given graph such that the resulting graph is planar. Then we compute a drawing of this planar subgraph without crossings. Finally we reinsert the deleted edges into this drawing in such a way that the number of edge crossings is minimized. Using this approach, the number of crossings of the final drawing depends on the planar subgraph and the drawing of this subgraph.

https://www.ads.tuwien.ac.at/research/graphDrawing.html

Here are some exapmles:

http://www.codeproject.com/Articles/14280/Database-Visualization http://www.ogdf.net/doku.php/tech:howto:plzl

Upvotes: 0

Related Questions