# Tagged Questions

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

480 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}{...
843 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 ...
282 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, ...
940 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 ...
786 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. ...
168 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$....
62 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 ...
182 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 ...
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 ...