Questions tagged [graph-drawing]
The graph-drawing tag has no usage guidance.
19 questions
2
votes
0
answers
149
views
Drawing rooted binary (search) trees
I am looking for an (elegant, fast, etc.) algorithm to draw a binary tree, where the root is distinguished, as well as the left and right children of each node. A typical example is a binary search ...
- 4,563
9
votes
2
answers
575
views
NP-hardness of a planar SAT variant
Background:
An instance of 3-SAT is called monotone if each clause consists only of positive literals or only of negative literals.
Given an instance $\phi$ of 3-SAT, we consider the bipartite graph $...
- 141
6
votes
0
answers
85
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 ...
- 2,531
9
votes
1
answer
323
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 ...
- 5,285
4
votes
0
answers
77
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 ...
- 834
-3
votes
1
answer
8k
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 ...
- 111
2
votes
2
answers
184
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 ...
- 235
5
votes
1
answer
4k
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 ...
- 1,671
9
votes
1
answer
463
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 ...
- 191
15
votes
1
answer
540
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,631
1
vote
1
answer
961
views
Graph layout algorithm
I have an undirected graph on matris by vertex adjacency relations like that;
...
- 119
17
votes
2
answers
610
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 ...
- 1,337
14
votes
1
answer
308
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 ...
- 143
6
votes
2
answers
593
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
4
answers
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 ...
- 153
5
votes
1
answer
300
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 ...
- 179
5
votes
2
answers
413
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 ...
- 13.3k
20
votes
6
answers
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 /...
23
votes
9
answers
20k
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?
- 333