Best way to visualize scatterplot with thousands of points in a grayscale-friendly way? I have 10,000 data points like shown in this plot: 
It's comparing the running time of some piece of code with the size of the problem it's running on.
(There are 2 important steps in the code; step 1's running time is in blue and step 2's is in green.)
I'm hoping to keep this grayscale-friendly, because I'm hoping to publish this and it may end up being in grayscale.
I'm trying to figure out how to best visualize this data. Currently I'm thinking it may be best to perform kernel density estimation in log-scale and just plot a smooth surface, but I'm not sure... is there a better way to visualize it clearly?
 A: A log-log plot will spread the points out quite a bit.
If your thesis is correct the data should tend to lie close to/parallel to  a 45 degree line through a typical point - say (x-median,y-median). 
Having seen your log-log scale plot in the comments, a greyscale would be a problem because the overlap of the point clouds is so substantial even on the log scale. With color you can use transparency but that's difficult on greyscale.     
So for that issue, consider a pair of graphs, each with a LOESS curve (as well as the suggested reference line), and each also with the LOESS curve from the other plot as a dashed curve for ready comparison. 
A: The run time as a function of the size is usually polynomial (when you're lucky) or exponential. Hence, I'd first try to figure which is the case. 


*

*For the former try log transform both time and size, then scatter.

*for the latter try log transform only time


If neither of these scatter plots show a linear pattern, then we need to think of something else, otherwise, you're good.
If you know theoretical run time function such as $O(n\ln n)$, then you can use this for transformation too. The point is to get to some kind of a linear function, as they tend to be easier to present and consume.
Also, you could bucket your data into bins. for instance, say you're run time $t$ is $t=10s^3$, where $s$ is the size of the problem, then $\ln t=\ln 10+3\ln s$. This would be handled by log-log transform. Next, you break the log of size $\ln s$ into buckets. Then for each bucket you put a candle stick. This will create the candle stick chart like shown below. It'll show the dispersion of log run times for each bucket.

