13 votes

Conditions for bipartite graph to be planar with no edges going around the vertices

Your graphs are exactly the graphs of path-width $1$ or, equivalently, the forests each of whose components is a caterpillar. Caterpillars have two relevant characterizations: they're the ...
David Richerby's user avatar
3 votes

A 2D Layout Algorithm for Small, Sparse, and Undirected Graphs with a Specific Edge Length

"Planar Embeddings of Graphs with Specified Edge Lengths" by Cabello, Demaine, and Rote (or one of the references they cite) seems to solve your problem. If you don't care about edges crossing too ...
adrianN's user avatar
  • 5,931
1 vote

Visualising pseudo-tree with two parents per node

In graph theory, a tree is is usually defined as a connected undirected graph with no cycles. One would also call a directed graph a tree if the underlying undirected graph is a tree. The concept of ...
NaturalLogZ's user avatar
1 vote

How to avoid drawing dense maps?

You could smooth the path of the road by fitting a spline to it (or some other curve), with parameters chosen based on the zoom level to ensure that it follows a smooth path on the screen.
D.W.'s user avatar
  • 158k

Only top scored, non community-wiki answers of a minimum length are eligible