Questions tagged [graph-drawing]
Problems related to graph drawing such as crossing numbers, layout designs, and intersection graphs.
13
questions with no upvoted or accepted answers
7
votes
0
answers
149
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,615
7
votes
0
answers
84
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 ...
- 149k
7
votes
0
answers
336
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, ...
- 1,267
5
votes
0
answers
223
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 ...
- 10.7k
4
votes
0
answers
128
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. ...
- 1,130
3
votes
0
answers
129
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." ...
- 1,615
2
votes
0
answers
83
views
"separators" for nonplanar graphs embedded in the plane
Given a nonplanar graph $G$ drawn in the plane with crossings.
Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an ...
- 181
2
votes
0
answers
62
views
What is the range of connectivity for maximal IC-planar graphs?
A graph is IC-planar if it admits a drawing in the plane with
at most one crossing per edge and such that two pairs of crossing edges
share no common end vertex. A graph $G$ is maximal in a graph ...
- 1,615
2
votes
0
answers
245
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 ...
- 415
1
vote
0
answers
65
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-...
- 1,615
1
vote
0
answers
115
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$-...
- 1,615
0
votes
0
answers
29
views
Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?
Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 3n $ edges.
Call the set of edges corresponding to an edge $uv$...
- 181
0
votes
0
answers
78
views
Is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?
A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.
A minor of graph G is a graph obtained from G by ...
- 1,130