# Questions tagged [graph-drawing]

The tag has no usage guidance.

17 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
922 views

### Graph layout algorithm

I have an undirected graph on matris by vertex adjacency relations like that; ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...