Embedding Vertices at Points: Few Bends Suffice for Planar GraphsKaufmann, Michael and Wiese, Roland (1999) Embedding Vertices at Points: Few Bends Suffice for Planar Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 1519, 1999 , pp. 165174(Official URL: http://dx.doi.org/10.1007/3540466487_17). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540466487_17
AbstractThe existing literature gives efficient algorithms for mapping trees or less restrictively outerplanar graphs on a given set of points in a plane, so that the edges are drawn planar and as straight lines. We relax the latter requirement and allow very few bends on each edge while considering general plane graphs. Our results show two algorithms for mapping fourconnected plane graphs with at most one bend per edge and for mapping general plane graphs with at most two bends per edge. Furthermore we give a point set, where for arbitrary plane graphs it is NPcomplete to decide whether there is an mapping such that each edge has at most one bend.
Actions (login required)
