Order-preserving 1-string representations of planar graphs
arXiv:1609.08132
Abstract
This paper considers 1-string representations of planar graphs that are order-preserving in the sense that the order of crossings along the curve representing vertex is the same as the order of edges in the clockwise order around in the planar embedding. We show that this does not exist for all planar graphs (not even for all planar 3-trees), but show existence for some subclasses of planar partial 3-trees. In particular, for outer-planar graphs it can be order-preserving and outer-string in the sense that all ends of strings are on the outside of the representation.
Submitted to SOFSEM 2017