Questions tagged [graph-drawing]

Problems related to graph drawing such as crossing numbers, layout designs, and intersection graphs.

Filter by
Sorted by
Tagged with
1
vote
1answer
68 views

Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is the smallest number of “curves”?

Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ ...
8
votes
1answer
167 views

Method to draw 3-connected planar graph on a sphere

The Tutte embedding is a way to create a "nice" drawing of a 3-connected planar graph in the plane, after having chosen an outer face. Is there a similar method to draw such a graph on a sphere? ...
4
votes
2answers
303 views

“Locally Nonplanar” graph

A 2-connected $3$-connected graph $G$ is "Almost Planar" Locally Nonplanar if it has a a $2$-connected spanning subgraph $H$ and an embedding in the plane such that $H$ is planar in this embedding and ...
5
votes
0answers
51 views

Universal point sets for 1-plane graphs

It is a notorious open problem to find a smallest set of $N$ points that permit any $n$-vertex planar graph to be drawn in the plane without crossings, using only those $N$ points as vertices, and ...
3
votes
2answers
103 views

Number Associated with Straight-line Drawings of Hamiltonian Graphs

Is there anything known about the maximum number of simple-polygonal Hamilton cycles that a straight-line drawing of a Hamiltonian graph can have? Put differently, if the vertices of a Hamilton ...
5
votes
2answers
451 views

Another graph characteristic

This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more. Consider a connected directed graph with at least one node with in-degree 0 and one node ...
3
votes
1answer
228 views

Can all crossings in a graph be moved to one point?

Consider a graph $G$ with at least two unavoidable crossings, say, the disjoint union of two copies of $K_5$. Can such a graph always be drawn so that there is only one singular point (where all ...
4
votes
0answers
182 views

Minimal algebraic degree of symmetric unit distance embedding of Heawood graph

I'm looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates ...
4
votes
1answer
235 views

Example to show pairwise crossing number is not equal to crossing number

A common point of two edges in a graph drawing that is not an incident vertex is called a crossing. The crossing number $cr(G)$ is defined to be the minimum number of crossings in any drawing of $G$....
10
votes
3answers
1k views

Is every graph an edge-crossing graph?

Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...
1
vote
1answer
207 views

Counting edges in embeddable CW-complexes in R^3

Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I ...
13
votes
1answer
619 views

Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly $$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{...
6
votes
7answers
1k views

Visualizing polyhedra from their 1-skeletons

Except for a few simple cases (typically pyramids and prisms) I find it hard to visualize a polyhedron from its 1-skeleton embedded in the plane, e.g. the hexahedral graph 5, as can be seen here. ...
2
votes
0answers
226 views

A primal-dual (double) circle packing (coin graph) question

I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem). Q1- But I am not sure whether ...
2
votes
1answer
884 views

Graph drawing: unrooted undirected tree graphs with specified edge lengths.

Has Joseph Felsenstein's equal daylight layout been analyzed by the graph drawing community? The following description is taken from his drawtree documentation: "This iteratively improves an ...
7
votes
0answers
309 views

3-dimensional Cayley graph

I would like to see Cayley graphs drawn in 3-dimensional Euclidean space such that the vertices are represented by points and various shadows display the actions of the generators. For example, ...
7
votes
2answers
1k views

Planar layouts of bipartite graphs

Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar. It would be very convenient if there was a ...