# How to draw an orthogonal graph from its edges and vertices data?

I am writing a software and I need to represent an graph in a orthogonal manner from topological data (vector of edges,vertices and their connectivity data)

Graphs consist of a set of vertices and a set of edges, each connecting two vertices.A vertex may have any number of connected edges so it makes the problem a lot more complicated.

I have read some articles and its looks like that the Kandinsky model is the post popular one. However I just don't know the algorithm, any other solution (algorithm) that solve the problem is also very welcome.

The following picture shows a real world example for an electricity network which should be considered as raw data, in order to create a graph from this network, some preliminary tasks must be done.

Input Data: The result I am looking for is something like below, there are some characteristics if you take a look much closer :

The Red Polygon in the middle of the above picture(input data) represents an electricity substation which is a node itself and can be connected to more than 4 edges. There are more red polygons but only one can be fit into the above picture however as you may see, the following picture could cover much more than a red polygon that means it can map a bigger area, so the following picture is much more denser.

In Schematics diagrams, red polygons (Substations) usually maintain their position against each other relatively so if we manage to see beyond the extents of the above map by zooming out for example, we should almost see a triangle that is obviously can be seen at the below while having the left one at the left, the down one at the down ..... (this is not a rule, but I thought it could be a head start for desired algorithm)

Orthogonal Diagram: • Does orthogonal in this context mean using only vertical and horizontal edges? Are you looking for a way to represent more than 4 edges meeting at a single vertex? May 28, 2016 at 14:49
• @trichoplax Exactly, and I do appreciate any help. May 31, 2016 at 12:52
• Is the graph guaranteed to be planar so that, forgetting the orthogonal edges for a moment, the graph can be drawn without edges overlapping?
– user2500
Jun 1, 2016 at 18:36
• General graph layout algorithms are anoying to program and implement. Even just finding proper ones from literature is pain. You should describe a bit more what you expect, draw a picture. Jun 2, 2016 at 7:57
• The vertexes already have a given position in 2D (or on a sphere), so it's more of an edge routing problem? The trivial solution is to route each edge first along the x, then along the y axis (or the other way 'round). If this is right, explaining the problems with this trivial solution might be helpful. I imagine a minimization problem by assigning penalties for the problems...
– user2500
Jun 3, 2016 at 16:54

libCola

cola.js (a.k.a. WebCola) is a JavaScript based rewrite of libcola which works well with D3.js

http://marvl.infotech.monash.edu/webcola/

Gridified Layout example:

http://marvl.infotech.monash.edu/webcola/examples/dotpowergraph.html

OGDF

Open Graph Drawing Framework

Have an orthogonal layout

Orthogonal: Ortholayout with modules for the steps of shape and compaction, ClusterOrthoLayout

http://www.ogdf.net/doku.php/ogdf:features

Check projects that uses OGDF

http://www.ogdf.net/doku.php/project:external

HOLA

Human-like Orthogonal Layout Algorithm

https://vimeo.com/150509722

Kieffer, Steve, Tim Dwyer, Kim Marriott, and Michael Wybrow. "Hola: Human-like orthogonal network layout." Visualization and Computer Graphics, IEEE Transactions on 22, no. 1 (2016): 349-358.

• This sounds promising. Could you edit to add some detail of what this provides? Jul 4, 2016 at 12:24
• It would also be useful to have an overview of how each algorithm works, so that they can be compared without needing to leave the answer. Jul 5, 2016 at 1:21