We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

19

The definitive article is a paper by Hlineny and Kratochvil from 2001. In it they show that the problem of recognizing a disk intersection graph (your question) is NP-hard, which suggests that it will be difficult to come up with a clean characterization. They also point out that $K_{3,3}$ cannot be represented as the intersection of disks, answering the ...

15

I don't think any such algorithm is known. The results I know about maximizing the minimum angle in straight line drawings of planar graphs are: Every planar graph has a (possibly nonplanar) drawing in which the minimum angle is inversely proportional to the maximum degree. For the main proof idea and some references, see http://11011110.livejournal.com/...

13

It is possible to construct 3-regular planar graphs with $\Theta(n)$ biconnected components (see e.g. fig.16 of this paper), each of which must contain at least one sharp vertex. On the other hand, if you require higher levels of connectivity, you can avoid having many sharp vertices. In particular, if you have a 3-connected planar graph, it can be drawn (e....

10

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why. (1) Fix a drawing of $K_{3,n}$. Without loss of generality we can assume that no two incident edges cross and that no two edges cross twice, for otherwise we can modify the drawing to eliminate these crossings ...

9

In a paper with McDiarmid we showed that the number of labelled graphs on $n$ vertices that are intersection graphs of disks is $n^{3n} \cdot \Theta(1)^n$ which is far less than $2^{{n\choose 2}}$, the total number of labelled graphs on $n$ vertices, and much more that $n^n \Theta(1)^n$, the number of planar graphs (touching graphs of disks) on $n$ vertices....

7

This question may not have been phrased to make it look research-level, but trying to compute the minimum number of crossings in a layout of a given graph is definitely a research-level problem. One complication is that there is more than one definition of the number of crossings: see Pach, "Which crossing number is it, anyway?", FOCS 1998. If you allow a ...

6

a billion node graphs have probably not been visualized much and are right on the edge of feasibility and an active area of research. the approach would generally have to depend on the unique data characteristics to reveal the features that are relevant/key for that dataset. assuming you mean in 3d. there are at least two roughly independent hard parts of ...

5

As Vinicius Santos has already said, this doesn't make sense without further restrictions (you can make any single edge cross itself as many times as you like). But a well-studied variant of this arises if you only allow each pair of edges to cross at most once, and not at all if they share an endpoint. Then, the graph drawings in which every possible ...

2

Below I show that reordering is not possible in any sense, so a new hardness proof from scratch is needed. It's not even possible to reorder just one side if you don't eliminate redundant cluases. This is because any pair of adjacent (cyclically) variables can be in a clause and that gives you very little freedom, you can only reorder them by a cyclical ...

2

I don't think this value is well defined the way it was posed, since there is always a drawing where an edge cross every other, but if you restrict the problem to linear drawings, then you have the maximum linear crossing number. This page of Douglas West relates this parameter with other parameters involving crossings. I think it can be useful.

1

you seem to want the following a graph layout algorithm. many std algorithms typically use force-based methods where nodes are connected by replusive/attractive "springs" and the equilibrium/low energy state is obtained through some amt of iteration (of the corresponding globally-constructed force-related differential equation). the output of the algorithm ...

1

You might take a look at GePhi.

Only top voted, non community-wiki answers of a minimum length are eligible