Questions tagged [graph-drawing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
0answers
68 views

Fáry-Like Theorems for nonplanar graphs

Let $cr(G)$ be the crossing number of a graph $G$, i.e. the minimum possible number of edge crossings over all valid drawings of $G$ in the plane. In general the edges of $G$ may be represented as ...
8
votes
1answer
235 views

Pathwidth of planarized drawing of $K_{3,n}$

The pathwidth of the complete bipartite graph $K_{3,n}$ with partite sets of size $3$ and $n$ is at most $3$. I am interested in planarizing this graph by the following process: Draw it in the plane ...
4
votes
0answers
68 views

On simultaneous embeddings with different vertex sets

The topic of simultaneous embeddings of planar graphs is a common sight in the recent graph drawing literature. A recent survey of the topic is given by Bläsius, Kobourov and Ritter. I am interested ...
-3
votes
1answer
6k views

Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
2
votes
2answers
161 views

Maximum Crossing number of topological graph

The crossing number of a graph $G$ is defined as the least number of crossings introduced when $G$ is drawn as a topological graph in the plane. Is there anything known about the maximum number of ...
6
votes
1answer
3k views

An algorithm to efficiently draw a extremely large graph in real time

Are there any algorithms to draw a billion node graph or to aggregate the information? The idea would be to allow for it to be parallelized using map reduce so it could be done in realtime I was ...
9
votes
1answer
358 views

Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?

I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different ...
15
votes
1answer
457 views

Drawing graphs with few “sharp” vertices?

For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other ...
1
vote
1answer
922 views

Graph layout algorithm

I have an undirected graph on matris by vertex adjacency relations like that; ...
16
votes
2answers
504 views

Representing non-planar graphs with overlapping circles

We know that we can represent any planar graph by a set of circles in the plane, known as a coin graph. Each circle represents a vertex and there is an edge between two vertices if and only if the ...
13
votes
1answer
258 views

Graph embedding which maximizes minimum angle

Given a planar graph, one can embed it in linear time crossing free into an $n \times n$ grid. I am interested whether any efficient algorithms are known to straight line embed a planar graph ...
6
votes
2answers
567 views

Incremental drawing of large graphs

I have the following problem: I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs ...
5
votes
4answers
1k views

Genetic Algorithm to Draw a Graph? Position assignment problem

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large). I have a directed ...
5
votes
1answer
288 views

Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?

Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps? For rectangular maps, for example, I intend maps that are made from overlapping ...
5
votes
2answers
334 views

Construction of graph embeddings with non-intersecting edges

I have a bipartite graph whose genus $g$ I know. I have a genus $g$ real surface(a $g$-holed donut). I want to construct a graph embedding on the surface so that I have no intersecting edges. Has this ...
20
votes
6answers
3k views

Network / Social network analysis visualization tools?

I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network /...
21
votes
9answers
12k views

What is the recommended software for drawing data structures such as graphs and trees?

When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?