# Questions tagged [graph-drawing]

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

39 questions
Filter by
Sorted by
Tagged with
114 views

### Is there a more intuitive proof that a 1-planar graph with minimum degree 7 contains a $K_4$?

In the following paper, Hudák Dávid, and Tomáš Madaras give the following Theorem 1.1. Hudák, Dávid, and Tomáš Madaras. "On local properties of 1-planar graphs with high minimum degree." ...
916 views

### Can a 3-regular non-1-planar graph be constructed?

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing. I used nauty to generate all 3-regular graphs up to ...
130 views

### Why is the crossing number of Tutte 12-cage 170?

From the Wikipedia entry on Tutte 12-cage , it is stated that the crossing number of Tutte 12-cage is 170, but the cited references do not seem to provide sufficient explanation for this. Exoo, G. &...
1 vote
41 views

### A confusion about the proof of maximal 1-plane graph being $2$-connected

It is well known that every maximal planar graph with at least 4 vertices is 3-connected. But for maximal 1-planar graphs we cannot ensure the high connectivity. (See is-there-any-maximal-1-planar-or-...
543 views

### How to construct a 5-regular 1-planar bipartite graph?

A graph is 1-planar if it can be drawn on the plane such that each edge is crossed at most once. Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov  showed ...
1 vote
73 views

### Does contracting a non-crossing edge of a $k$-plane graph change the $k$-planarity?

A graph is $k$-planar if it can be drawn on the plane such that each edge is crossed at most $k$ times. A graph together with a $k$-planar drawing is a $k$-plane graph. Hence, by definition, $0$-...
156 views

### Find all 2-planar drawings of $K_6$ and $K_7$

A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per edge. It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$. Angelini P., Bekos M. A., ...
347 views

### Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?

A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are ...
185 views

### Is the crossing number of the line graph of $K_5$ determined?

The line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$. $L(G)$ is constructed in the following way: for each edge in $G$, make a vertex ...
126 views

### Which Boolean lattices have a left-to-right symmetric drawing?

This question is inspired by a similar MSE question about partition lattices. Question: Which finite Boolean lattices have a symmetric drawing on the 2D plane? By a symmetric drawing of a lattice, I ...
344 views

### Find all Non-isomorphic good drawings of $K_{3,3}$？

Sometimes I look at all non-isomorphic good drawings of graphs on a plane or sphere. Good drawing means that no edge crosses itself, no two edges cross more than once, and no two edges incident with ...
121 views

### Constructing a 1-planar graph that has no rectilinear drawing

A 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. 1 planar graph I read the ...
1 vote
130 views

### Can Tutte embedding be guaranteed that each face is convex?

In graph drawing and geometric graph theory, a Tutte embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a ...
1 vote
178 views

### Abnormal toroidal drawing of graph

1. Some background knowledge Definition. A torus, informally, is the doughnut-shaped surface that we get by taking a square made out of some arbitrarily-stretchy material and gluing together opposite ...
98 views

### The density of a tripartite 1-planar graph

1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
127 views

### What is the crossing number of dodecahedron with a copy of $K_5$ inside each face

Suppose we are given a regular dodecahedron. Then we add five crossed edges inside each of its faces (actually, inside each face it is a copy of $K_5$). It is clear that this drawing has 60 crossings. ...
254 views

### What is the crossing number of cube with a pair of crossing edges inside each face

Suppose we are given a cube and we add a pair of crossing edges inside each of its faces. It is clear that this drawing has 6 crossings. My question is whether such a graph has crossing number 6? How ...
237 views

### Finding a special plane graph with some requirements on the faces

Is there a plane graph such that (1) the outer face has degree 3, i.e, is a triangle, (2) every inner face has degree 5, and (3) any two degree 5 faces share at most one commong edge.
172 views

### Looking for examples showing that the crossing number may not be realized by the drawings with local crossing number

The crossing number $cr(G)$ of a graph $G$ is the lowest number of edge crossings of a plane drawing of the graph $G$. The local crossing number of a drawing of a graph is the largest number of ...
202 views

### There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?

Is there any characterization on the set of integers $n$ such that there is a 3-connected 5-regular simple $n$-vertex planar graph?
239 views

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. ...
242 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 ...
1k 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 (Wayback Machine): "This ...