Skip to main content
Tony Huynh's user avatar
Tony Huynh's user avatar
Tony Huynh's user avatar
Tony Huynh
  • Member for 15 years
  • Last seen this week
revised
Loading…
revised
Loading…
revised
Loading…
revised
Loading…
Loading…
revised
Book for matroid polytopes
deleted 10 characters in body
Loading…
answered
Loading…
revised
Minimally 2-vertex-connected graphs?
added 101 characters in body
Loading…
revised
Loading…
revised
Loading…
comment
Does every graph admit an embedding such that identically-colored edges do not cross?
Yes, it makes a difference. Geometric thickness is what the OP is asking about, while thickness is a related but different parameter (since the embeddings do not have to be the same).
Loading…
comment
Does every graph admit an embedding such that identically-colored edges do not cross?
I think the minimum number of colours is sometimes called geometric thickness.
comment
Does every graph admit an embedding such that identically-colored edges do not cross?
It is not always possible with two colours since an $n$-vertex planar graph has at most $3n-6$ edges, and the red subgraph and blue subgraph are both planar graphs. So, any $n$-vertex graph with at least $6n-11$ edges is a counterexample.
awarded
comment
Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$
I think it is correct as is. For example every $n$-point $\ell_2$-metric can be embedded in $\ell_2$ with dimension $O(n)$.
revised
Loading…
revised
Loading…
revised
Loading…
Loading…
1
3 4
5
6 7
176