All Questions
Tagged with topological-graph-theory graph-drawing
7 questions
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
1
vote
0
answers
42
views
What lower bounds are known for pair crossing number and related questions in multigraphs?
So in terms of crossing number https://arxiv.org/pdf/1808.10480 gives a lower bound of $O(e^{2.5}/n^{1.5})$ for multigraphs with no face of length 2 with no node contained inside.
What do we know ...
- 111
1
vote
0
answers
97
views
Problem related to crossing number
Let $G$ be a graph embedded in the plane (with crossings). For $ F \subset E(G) $, denote by $c(F)$ the set of edges of $G$ that cross some edge in $F$.
Denote $\delta(v)$ the set of edges with one ...
- 111
4
votes
1
answer
214
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., ...
- 6,101
4
votes
1
answer
393
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$....
- 32.1k
5
votes
1
answer
479
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 ...
- 32.1k