Questions tagged [graph-drawing]
Problems related to graph drawing such as crossing numbers, layout designs, and intersection graphs.
8 questions
10
votes
2
answers
724
views
Bounds on chromatic number of $k$-planar graphs
A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.
Planar graphs are ...
- 151k
8
votes
7
answers
2k
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.
...
- 9,720
7
votes
0
answers
155
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,851
7
votes
2
answers
252
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?
- 1,190
6
votes
2
answers
293
views
Is there any maximal 1-planar or 2-planar graph that is not 3-connected
A graph is $k$-planar if it can be drawn in the plane so that each edge is crossed at most $k$ times. A $k$-planar graph $G$ is maximal if $G+uv$ is not $k$-planar for any non-adjacent vertices $u,v\...
- 1,190
4
votes
0
answers
131
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,190
1
vote
1
answer
115
views
Bounds on lengths of boxes in bounded-degree box graphs
$\DeclareMathOperator{\box}{\operatorname{box}}$$\DeclareMathOperator{\cub}{\operatorname{cub}}$
This is a follow up and an extension of another question I asked recently.
A box graph is a graph ...
- 277
1
vote
1
answer
194
views
Bounds on lengths of intervals in bounded-degree interval graphs
A graph is said to be an interval graph if its vertices can be associated with (closed) intervals on the real line $\mathbb R$ and there is an edge between two vertices if and only if the ...
- 277